markh@csd4.csd.uwm.edu (Mark William Hopkins) (05/13/91)
In article <11943@uwm.edu> markh@csd4.csd.uwm.edu (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") > >Yet at any point in time it has only "computed" a finite set and can thus be >emulated by a finite machine. So is this machine actually computing or not? > >My answer is yes. It's a non-recursive computer. This machine's construction follows the proof of Goedel's Completeness Theorem and I believe its existence is EQUIVALENT to Ulam's Conjecture (dealing with the existence ultrafilters of infinite lattices), which is slightly weaker than the Axiom of Choice (so I mane it the Ulam Machine, and not the Choice Machine). But here's something more to digest, that illustrates how deep the paradox runs: The Ulam Metatheorem: Every automata theory capable of representing Finite State Automata has a model containing automata more powerful than the Turing Machine.
rockwell@socrates.umd.edu (Raul Rockwell) (05/13/91)
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?
Raul Rockwellunx20491@unx2.ucc.okstate.edu (Inscrutable Eric) (05/14/91)
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
sethb@Morgan.COM (Seth Breidbart) (05/15/91)
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
rockwell@socrates.umd.edu (Raul Rockwell) (05/15/91)
Eric Gindrup: (To answer why I think you're being dense...) He [Mark William Hopkins] 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. Ah, yes, now I _think_ I see the point he was trying to make. To grab a quote from the original article: MWH: Yet at any point in time it has only "computed" a finite set and can thus be emulated by a finite machine. So is this machine actually computing or not? And the answer to that question is: Yes, it's computing, but its computations may take infinite time. The "emulator" is somewhat less well defined (does it also take infinite time where the "ulam machine" would do so?) but it too is computing. If the emulator always takes finite time to produce a result, it would, in finite time, produce an erroneous result (unless it was doing strict construction -- which is a finite computation). Or, maybe I'm still not getting the point. I still don't see the paradox :-( Raul Rockwell
unx20491@unx2.ucc.okstate.edu (Inscrutable Eric) (05/18/91)
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. [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."
sethb@Morgan.COM (Seth Breidbart) (05/22/91)
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