Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mstan!sethb
From: sethb@Morgan.COM (Seth Breidbart)
Newsgroups: comp.theory
Subject: Re: The Ulam Machine (was: Re: Paradox of the non-recursive computer)
Message-ID: <3301@ylum.Morgan.COM>
Date: 14 May 91 22:35:23 GMT
References: <12089@uwm.edu> <ROCKWELL.91May12152938@socrates.umd.edu> <1991May13.192530.27792@unx2.ucc.okstate.edu>
Organization: Morgan Stanley, & Co., Inc. / New York City, NY
Lines: 28

In article <1991May13.192530.27792@unx2.ucc.okstate.edu>
unx20491@unx2.ucc.okstate.edu (Inscrutable Eric) writes:
|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".
|>
:
|  '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.

Actually, it can be shown that there is _no_ machine that can
enumerate the sets Ti, no matter what time complexity is allowed.

Seth		sethb@fid.morgan.com