Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!wuarchive!uunet!news.uu.net!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: <3378@ylum.Morgan.COM>
Date: 21 May 91 22:04:29 GMT
References: <1991May13.192530.27792@unx2.ucc.okstate.edu> <3301@ylum.Morgan.COM> <1991May17.183955.8428@unx2.ucc.okstate.edu>
Organization: Morgan Stanley, & Co., Inc. / New York City, NY
Lines: 71

In article <1991May17.183955.8428@unx2.ucc.okstate.edu>
unx20491@unx2.ucc.okstate.edu (Inscrutable Eric) writes:
>In article <3301@ylum.Morgan.COM> sethb@Morgan.COM (Seth Breidbart) writes:
>>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.
>     
>My whole point was that the determination of whether An was or was not
>consistent with T(n+1) looks like Satisfiability to me.

Ah, now I understand the problem.  I believe that the original poster
was talking about a logic system sufficiently powerful to represent
arithmetic.  In that case, both Goedel's Theorem and the
undecidability of the halting problem imply the nonexistence of a
Turing Machine to calculate the sets T(i).

Inscrutable Eric is apparently considering a set of statements in the
predicate calculus.  In that case, not only does such a Turing Machine
exist, but one with a fairly short run-time does.  I'll need to
specify the language in detail:  (context-free specification, 
::= means "rewrites as", upper case letters are non-terminals,
| denotes alternation, c-style comments)

V ::= v | V0 | V1 /* a variable is the letter "v" followed by any
                     string of 0's and 1's */
S ::= V | (S & S) | (~S) | S or S  /* "or" is a single character.
                    A statement is a variable, or a parenthesized
                    expression containing (one or two) statements
                    and a logical function (and, not, or) */

Order the statements first by length, then in lexicographic order.

Now, note that the first appearance of any variable consists of that
variable alone.  Thus, under the interpretation above, all variables
are true.  This enables us to determine the truth of any compound
sentence rather easily, certainly in polynomial time.


>                                                       If he could
>propose a turing machine or some other FSA-like mechanism which would
>determine the consistency of An with T(n) in polynomial time, that
>would be basically the statement of Satisfiability.

No, because a statement is not being checked for self-consistency,
which would be equivalent to satisfiability, but for consistency with
all previously specified sentences.  This trivializes the problem.

Seth