Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!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: <1991May17.183955.8428@unx2.ucc.okstate.edu> Date: 17 May 91 18:39:55 GMT References: <1991May13.192530.27792@unx2.ucc.okstate.edu> <3301@ylum.Morgan.COM> Organization: Oklahoma State University Computer Center Lines: 73 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@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. [admittedly, proof writing is not an automatable process in the general sense.] > My whole point was that the determination of whether An was or was not consistent with T(n+1) looks like Satisfiability to me. 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. A further note is to observe that the statement An is restricted to be not "independent" (i.e. its truth or falsity must be a determinable state.) of the axiom set T(n) and thus, An could not be a new _axiom_, but would, in fact, be a theorem of the axiom set T(n). Furthermore, since ALL such An would follow this restriction, all An would merely be theorems of the axiom set T. Thus, effectively, this machine's purpose is to generate every well-formed, non-independent sentence of the axiom set(s) T, and then determine whether each such sentence is either provable from the axioms, or never provable from the axioms. If his sentences were randomly generated, the "provability" of each sentence would be equivalent to the halting question: Can you prove that (possibly recursive) application of a finite set of axioms and postulates will generate a pre-determined sentence. Or, effectively, prove that the "proof-generator" will ever halt, producing the list of steps necessary to turn an axiom into the sentence. Since insufficient information about the theorem (An) production mechanism is given, (for example, if each An were generated by the application of any postulate to a previously generated theorem or postulate, then, given that information, consistency would be insured), the undecidability of the aforementioned machine becomes moot. Since there are an infinity of such theorems that can be generated, the machine will never halt. If the machine has no idea :-) how the An was generated, then there is no guarantee that the sentence could ever be generated, and thus the machine might never halt in its attempt to verify the truth or falsity of the given sentence. THESE are the things which keep me awake at night. --------------------------------------------------------------------- "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."