| Turing's Proof |
Website Links For Proof |
Information AboutTuring's Proof |
|
"...what I shall prove is quite different from the well-known results of Gödel ... I shall now show that there is no general method which tells whether a given formula U is provable in '''K''' Mathematica ..." (Undecidable p. 145). Turing preceded this proof with two others. The second and third both rely on the first. All rely on his development of type-writer-like "computing machines" that obey a simple set of rules and his subsequent development of a "universal computing machine". THE FIRST DESCRIPTION OF A MECHANICAL PROCESS-AS-ALGORITHM See Turing Machine , Post-Turing Machine , and Halting Problem for more details.
: (1) Start with V = 0, let K be a constant -- positive but less than 1
: (3) Do (2) until hell freezes over. If we choose k = 0.5, we get the following sequence: : { 0, 0.5, 0.75, 0.875, ...., just a hair less than 1) The lasting legacy of Turing's work was his description of a "method" that was entirely, utterly, completely mechanical-- we just "program it", plug it in and (given we've programmed it well) it cranks out its number. Thus Turing defined a "tool" so precise it has become lingua franca among mathematicians and logicians. But he didn't stop there: he showed how to make write a single "universal" program that can interpret any "program" it finds on its tape (its memory). Some programs put there would be "well formed" -- that is, they will "run". Other programs put there won't be "well formed" -- and they won't "run". But in either case, Turing presented us with an absolute, ''constructive'' description of a mathematical process -- we can "construct" it, truly. from Alonzo Church here, re Turing's demonstration Over the years his proofs have been superceded by easier proofs. here -- e.g. Halting Problem , and Encyclopedia Britannia entry Meta-mathematics RICHARD'S PARADOX In 1905 Jules Richard presented this profound paradox. Alan Turing's first proof constructs this paradox with his so-called computing machine and proves that this machine cannot answer a simple question: will this machine be able to determine if ''any'' computing machine (including itself) will become trapped in an unproductive "infinite loop" (i.e. it fails to continue its computation of the diagonal number). A succinct definition of Richard's Paradox is found in Whitehead and Russell's ''Principia Mathematica'': "Richard's paradox... is as follows. Consider all decimals that can be defined by means of a finite number of words added for emphasis, "words" are symbols ; let E be the class of such decimals. Then E has an infinity of terms; hence its members can be ordered as the 1st, 2nd, 3rd, ... Let N be a number defined as follows & Russell now employ the Cantor diagonal method ; If the nth figure in the nth decimal is p, let the nth figure in N be p+1 (or 0, if p = 9). Then N is different from all the members of E, since, whatever finite value n may have, the nth figure in N is different from the nth figure in the nth of the decimals composing E, and therefore N is different from the nth decimal. Nevertheless we have defined N in a finite number of words this very word-definition just above! and therefore N ought to be a member of E. Thus N both is and is not a member of E" (Principia Mathematica, 2nd edition 1927, p. 61). COMPLICATIONS Turing's proof is complicated by a large number of definitions, and confounded with what for pointing out these errors" (Undecidable, p. 152). Specifically, in its original form the third proof is badly marred by technical errors. And even after Bernays' suggestions and Turing's corrections, errors remained in the description of the Universal Machine . And confusingly, since Turing was unable to correct his original paper, some text within the body harks to Turing's flawed first effort. Bernays' corrections may be found in ''The Undecidable'', pp. 152-154; the original is to be found as: : ''On computable Numbers, with An Application to the Entscheidungsproblem. A Correction''., Proceedings of the London Mathematical Society (2), 43 (1937), 544-546.'' The on-line version of Turing's paper has these corrections in an addendum; however, corrections to the Universal Machine must be found in an analysis provided by Emil Post . At first, the only mathematician to pay close attention to the details of the proof was Post (cf Hodges p. 125)-- mainly because he had arrived simultaneously at a similar reduction of "algorithm" to primitive machine-like actions, so he took a personal interest in the proof . Strangely (perhaps World War II intervened) it took Post some ten years to dissect it in the ''Appendix'' to his paper ''Recursive Unsolvability of a Problem of Thue'', 1947, (reprinted in Undecidable p. 293). ''Before readers tackle "Proof #3" we strongly advise that they place those corrections on their copy of the proof.'' Other problems present themselves: In his ''Appendix'' Post commented indirectly on the paper's difficulty and directly on its "outline nature" (Post in Undecidable p. 299) and "intuitive form" of the proofs (ibid). Post had to infer various points: : "If our critique is correct, a machine is said to be circle-free if it is a Turing computing ... machine which prints an infinite number of 0's and 1's. And the two theorems of Turing's in question are really the following. There is no Turing ... machine which, when supplied with an arbitrary positive integer n, will determine whether n is the D.N of a Turing computing ... machine that is circle-free. {Link without Title} , There is no Turing convention-machine which, when supplied with an arbitrary positive integer n, will determine whether n is the D.N of a Turing computing ... machine that ever prints a given symbol (0 say)" (Post in Undecidable p. 300) Anyone who has ever tried to read the paper will understand Hodges' complaint: : "The paper started attractively, but soon plunged (in typical Turing manner) into a thicket of obscure German Gothic type in order to develop his instruction table for the universal machine. The last people to give it a glance would be the applied mathematians who had to resort to practical computation..." (Hodges p. 124) Proof #1 is wonderful -- although by Reductio Ad Absurdum form of proof --it is constructive and does not require much mathematics. Proof #2, on the other hand, uses and "an infinity of possibles". A bit of discussion of the Logical Quantifier s 'there exists at least one X' and 'for all X' attempts to provide a bit of help. If readers brave Proof #3, they should come equipped with a solid background in (i) logic (ii) the paper of Kurt Gödel ''On Formally Undecidable Propositions of Principia Mathematica and Related Systems'', (reprinted in Undecidable p. 5). For assistance with Gödel's paper they should consult Ernest Nagel and James Newman , ''Godel’s Proof'', New York University Press, 1958. SUMMARY OF THE PROOFS In his proof that the "Entsheidungsproblem" can have no solution, Turing proceeded from two proofs that were to led to his final proof. His first theorem is most relevant to the Halting Problem , the second is more relevant to Rice's Theorem . First proof: that no "computing machine" exists that can decide whether or not a "computing machine" is "circle-free" (i.e. goes on printing its number in binary ad infinitum): "...we have no general process for doing this in a finite number of steps" (p. 132, ibid). Turing's proof, although it seems to use the "diagonal process", in fact shows that his machine (called H) cannot calculate its own number, let alone the entire diagonal number ( Cantor's Diagonal Argument ): "The fallacy in the argument lies in the assumption that B diagonal number is computable" (U p. 132). Second proof: This one is perhaps more familiar to readers: "We can show further that ''there can be no machine E which, when supplied with the S.D {Link without Title} of an aribrary machine M, will determine whether M ever prints a given symbol (0 say)''" (his italics, U p. 134). Third proof: "Corresponding to each computing machine M we construct a formula Un(M) and we show that, if there is a general method for determining whether Un(M) is provable, then there is a general method for determining whether M ever prints 0" (p. 145) This proof requires the use of formal logic to prove a first lemma, (difficult but mercifully short), followed by a brief word-proof of the second: : "Lemma 1: If S1 "0" appears on the tape in some complete configuration of M, then Un(M) is provable" (p. 147) : "Lemma 2: converse If Un(M) is provable then S1 "0" appears on the tape in some complete configuration of M" (p. 148) Finally, in only 64 words and symbols Turing proves by ''reductio ad absurdum'' that "the Hilbert ''Entscheidungsproblem'' can have no solution" (U p. 145). SUMMARY OF THE FIRST PROOF Some key clarifications: : Turing's machine H is attempting to print a diagonal number :: This diagonal number is created when H actually "simulates" each "successful" machine under evaluation and prints the R-th "figure" (1 or 0, binary) of the R-th "successful" machine/
Turing begins the proof with the assertion of the existence of a “decision/determination” machine D. When fed any S.D (string of symbols A, C, D. L, R, N, semicolon “;”) it will determine if this S.D (symbol string) represents a "computing machine" that is either "circular"-- and therefore "un-satisfactory u" -- or "circle-free"-- and therefore "satisfactory s". : Turing has previously demonstrated that all "computing machines''-- machines that compute a number as 1's and 0's forever-- can be written as an S.D on the tape of the “universal machine” U. Most of his work leading up to his first proof is spent demonstrating that the universal machine truly exists, i.e. :: There truly exists a universal machine U :: For each number N, there truly exists a unique S.D, :: Every Turing machine has an S.D :: Every S.D on U’s tape can be “run” by U and will produce the same “output” (figures 1, 0) as the original machine. Turing makes no comment about how machine D goes about its work. For sake of argument, we suppose that D would first look to see if the string of symbols is "well-formed" (i.e. in the form of an algorithm and not just a scramble of symbols), and if not then discard it. Then it would go “circle-hunting”. To do this perhaps it would use “heuristics” (tricks: taught or learned). For purposes of the proof, these details are not important. Turing then describes (rather loosely) the algorithm (method) to be followed by a machine he calls H. Machine H contains within it the decision-machine D (thus D is a “subroutine” of H). Machine H’s algorithm is expressed in H’s table of instructions, or perhaps in H’s Standard Description on tape and united with the universal machine U; Turing does not specify this. : In the course of describing universal machine U, Turing has demonstrated that a machine’s S.D (string of letters similar to a “program”) can be converted to an integer (base 8) and visa versa. Any number N (in base 8) can be converted to an S.D with the following replacements: 1 by A, 2 by C, 3 by D, 4 by L, 5 by R, 6 by N, 7 by semicolon ";". :: As it turns out, machine H's unique number (D.N) is the number "K". We can infer that K is some hugely long number, maybe tens-of-thousands of digits long. But this is not important to what follows. Machine H is responsible for converting ''any'' number N into an equivalent S.D symbol string for sub-machine D to test. (In programming parlance: H passes an arbitrary "S.D” to D, and D returns “satisfactory” or “unsatisfactory”.) Machine H is also responsible for keeping a tally R (“Record”?) of successful numbers (we suppose that the number of "successful S.D's i.e. R is much less than the number of S.D's tested, i.e. N). Finally, H prints on a section of its tape a diagonal number “beta-primed” B’. H creates this B’ by “simulating” (in the computer-sense) the “motions” of each “satisfactory” machine/number; eventually this machine/number under test will arrive at its Rth “figure” (1 or 0), and H will print it. H then is responsible for “cleaning up the mess” left by the simulation, incrementing N and proceeding onward with its tests, ''ad infinitum''. : Note: All these machines that H is hunting for are what Turing called "computing machines". These compute binary-decimal-numbers in an endless stream of what Turing called "figures": only the symbols 1 and 0. An example: Suppose machine H has tested 13472 numbers and produced 5 satisfactory numbers, i.e. H has converted the numbers 1 through 13472 into S.D’s (symbol strings) and passed them to D for test. As a consequence H has tallied 15 satisfactory numbers and run the first one to its 1st “figure”, the second to its 2nd figure, the third to its 3rd figure, the fourth to its 4th figure, and the fifth to its 5th figure. The count now stands at N = 13472, R = 5, and B’ = “.10011” (for example). H cleans up the mess on its tape, and proceeds: H increments N = 13453 and converts "13453" to symbol string ADRLD. If sub-machine D deems ADLRD unsatisfactory, then H leaves the tally-record R at 5. H will increment the number N to 13454 and proceed onward. On the other hand, if D deems ADRLD satisfactory then H will increment R to 6. H will convert N (again) into ADLRD is just an example, ADLRD is probably useless and “run” it using the universal machine U until this machine-under-test (U "running" ADRLD) prints its 6th “figure” i.e. 1 or 0. H will print this 6th number (e.g. “0”) in the “output” region of its tape (e.g. B’ = “.100110”). H cleans up the mess, and then increments the number N to 13454. The whole process unravels when H arrives at its own number K. We will proceed with our example. Suppose the successful-tally/record R stands at 12. H finally arrives at its own number minus 1, i.e. N = K-1 = 4335...3214, and this number is unsuccessful. Then H increments N to produce K = 4355...321'''5''', i.e. its own number. H converts this to “LDDR...DCAR” and passes it to decision-machine D. Decision-machine D must return “satisfactory” (that is: H must ''by definition'' go on and on testing, ''ad infinitum'', because it is "circle-free"). So ... H now increments tally R from 12 to 13 and then re-converts the number-under-test K into its S.D and uses U to simulate it. But this means that H will be simulating its own motions. (What's so wrong with thinking about your own thinking? Marvin Minsky makes the same point...) What is the first thing the simulation will do? This simulation K-aka-H either creates a new N or “resets” the “old” N to 1. This "K-aka-H" either creates a new R or “resets” the “old” R to 0. Old-H “runs” new "K-aka-H" until it arrives at its 12th figure. But it never makes it to the 13th figure; K-aka-H eventually arrives at 4355...3215, again, and ''K-aka-H'' must repeat the test. ''K-aka-H'' will ever reach the 13th figure. The H-machine probably just prints copies of itself ''ad infinitum'' across blank tape. But this contradicts the premise that H is a satisfactory, non-circular computing machine that goes on printing the diagonal numbers's 1’s and 0’s forever. (We also will see the same thing if N is reset to 1 and R is reset to 0). If the reader does not believe this, they can write a "stub" for decision-machine D (stub "D" will return "satisfactory") and then see for themselves what happens at the instant machine H encounters its own number. SUMMARY OF THE SECOND PROOF Less than one page long, the passage from premises to conclusion is obscure. Turing proceeds by ''reductio ad absurdum''. He asserts the existence of a machine E, which when given the S.D (standard description, i.e. "program") of an arbitrary machine M, will determine whether M ever prints a given symbol (0 say). He does not assert that this M is a "computing machine". Given the existence of machine E, Turing proceeds as follows: # If machine E exists then a machine G exists that determines if M prints 0 infinitely often, AND # If E exists then another process exits can call the process/machine G' for reference that determines if M prints 1 infintely often, THEREFORE # When we combine G with G' we have a process that determines if M prints an infinity of figures, AND # IF the process "G with G'" determines M prints an infinity of figures, THEN "G with G'" has determined that M is circle-free, BUT # This process "G with G'" that determine if M is circle-free, by proof 1, cannot exist, THEREFORE # Machine E does not exist. Details of Second Proof | ||
| "Provable" Means, In The Sense Of Gödel | "support" class="copylinks" target="_blank">this! '''FootnoteProvable''' , that (i) the axiom system itself is powerful enough to produce (express) the sentence "This sentence is provable", and (ii) that in any arbitrary "well-formed" proof the symbols lead by axioms, definitions, and substitution to the symbols of the conclusion |
|
|