Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!ncar!unmvax!uokmax!d.cs.okstate.edu!unx2.ucc.okstate.edu!unx20491
From: unx20491@unx2.ucc.okstate.edu (Inscrutable Eric)
Newsgroups: comp.theory
Subject: Re: The Ulam Machine (was: Re: Paradox of the non-recursive computer)
Message-ID: <1991May13.192530.27792@unx2.ucc.okstate.edu>
Date: 13 May 91 19:25:30 GMT
References: <11943@uwm.edu> <12089@uwm.edu> <ROCKWELL.91May12152938@socrates.umd.edu>
Organization: Oklahoma State University Computer Center
Lines: 49

In article <ROCKWELL.91May12152938@socrates.umd.edu> rockwell@socrates.umd.edu (Raul Rockwell) writes:
>Mark William Hopkins writes:
>   Consider an abstract machine that correctly emulates T0, T1, T2,
>   and so on.  It exists, according to the Axiom of Choice, but is
>   more powerful than a Turing Machine (and thus "non-computeable")
>
>Where he defined T0, T1, ... as:
>   You can enumerate all the statements of a formal logic system, A0,
>   A1, A2, ...  Consider a family of sets T0, T1, T2, ..., built on an
>   axiom base T.  Each set is incremented from the previous in the
>   following way:
>      T(n+1) = T(n) + [An] if statement An is consistent with Tn + axioms T.
>      T(n+1) = T(n) + [not An] if statement An is inconsistent with Tn + T.
>
>
>However, he fails to address the issue of determining "if statement An
>is consistent with Tn + axioms T".
>
>It looks like he is extending a theorem by adding some some compatible
>theorem as an axiom.  Since substitution allows one to trivially
>obtain a compatible theorem, computability is satisfied (as is turing
>computability).
>
>Am I just being dense?

Well, in a sense, yes you are.  But, you raise an interesting question 
concerning the similarity of the statement of this system and that which
"Satisfiability" proposes to cover.  'Twould be interesting to produce a
machine that could produce T(n+1) in polynomial time, that being one of
the more interesting questions in complexity theory, today.
(To answer why I think you're being dense...)
He seems to be producing an arbitrarily random theorem and then
determining whether through (not necessarily) finite application of the
previous theorems, he can arrive at a previous theorem.  He's not using
the preceding set to produce the next theorem, he's using it to test the
next theorem.  Subtle (and not _very_ important) point, but your
statement removes some of the expessibility of his formulation of the
system.

---------------------------------------------------------------------
"I call myself `'d' Kidd,' because no one else will." -- Me.
unx20491@unx2.ucc.okstate.edu (Eric Gindrup)
God created a countable infinity of numbers.  All else is the work of
consistent people.  "Consistency is the hobgoblin of little minds."
-- 
---------------------------------------------------------------------
"I call myself `'d' Kidd,' because no one else will." -- Me.
unx20491@unx2.ucc.okstate.edu (Eric Gindrup)
God created a countable infinity of numbers.  All else is the work of