Turing's proof is a proof by Alan Turing submitted on 12 November 1936 and first published in 1937 with the title "On Computable Numbers, with an Application to the ". It was the second proof (after Church's theorem) of the negation of Hilbert's ; that is, the conjecture that some purely mathematical yes–no questions can never be answered by computation; more technically, that some decision problems are "undecidable" in the sense that there is no single algorithm that infallibly gives a correct "yes" or "no" answer to each instance of the problem. In Turing's own words: "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 [Principia Mathematica]".
Turing followed this proof with two others. The second and third both rely on the first. All rely on his development of typewriter-like "computing machines" that obey a simple set of rules and his subsequent development of a "universal computing machine".
Summary of the proofs In his proof that the Entscheidungsproblem can have no solution, Turing proceeded from two proofs that were to lead 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 an arbitrary "computing machine" (as represented by an integer 1, 2, 3, . . .) is "circle-free" (i.e. goes on printing its number in binary forever): "...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 [the diagonal number] is computable" The proof does not require much mathematics.
Second proof: This one is perhaps more familiar to readers as Rice's theorem: "We can show further that there can be no machine E which, when supplied with the S.D ["program"] of an arbitrary machine M, will determine whether M ever prints a given symbol (0 say)"
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".
The third proof requires the use of formal logic to prove a first lemma, followed by a brief word-proof of the second:
Finally, in only 64 words and symbols Turing proves by reductio ad absurdum that "the Hilbert Entscheidungsproblem can have no solution".
Summary of the first proof Turing created a thicket of abbreviations. See the glossary at the end of the article for definitions.
Some key clarifications:
Turing spent much of his paper actually "constructing" his machines to convince us of their truth. This was required by his use of the reductio ad absurdum form of proof. We must emphasize the "constructive" nature of this proof. Turing describes what could be a real machine, really buildable. The only questionable element is the existence of machine D, which this proof will eventually show to be impossible.
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 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.
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 to illustrate the first proof 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 5 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 = 13473 and converts "13473" 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 13474 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 [this 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 13474.
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 = 4335...3215, 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 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 4335...3215, again, and K-aka-H must repeat the test. K-aka-H will never 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 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 exists [we can call the process/machine G' for reference] that determines if M prints 1 infinitely 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 The difficulty in the proof is step 1. The reader will be helped by realizing that Turing is not explaining his subtle handiwork. (In a nutshell: he is using certain equivalencies between the “existential-“ and “universal-operators” together with their equivalent expressions written with logical operators.)
Here is an example: Suppose we see before us a parking lot full of hundreds of cars. We decide to go around the entire lot looking for: “Cars with flat (bad) tires”. After an hour or so we have found two “cars with bad tires.” We can now say with certainty that “Some cars have bad tires”. Or we could say: “It’s not true that ‘All the cars have good tires’”. Or: “It is true that: ‘not all the cars have good tires”. Let us go to another lot. Here we discover that “All the cars have good tires.” We might say, “There’s not a single instance of a car having a bad tire.” Thus we see that, if we can say something about each car separately then we can say something about ALL of them collectively.
This is what Turing does: From M he creates a collection of machines {M1, M2, M3, M4, ..., Mn} and about each he writes a sentence: “X prints at least one 0” and allows only two “truth values”, True = blank or False = :0:. One by one he determines the truth value of the sentence for each machine and makes a string of blanks or :0:, or some combination of these. We might get something like this: “M1 prints a 0” = True AND “M2 prints a 0” = True AND “M3 prints a 0” = True AND “M4 prints a 0” = False, ... AND “Mn prints a 0” = False. He gets the string
if there are an infinite number of machines Mn. If on the other hand if every machine had produced a "True" then the expression on the tape would be
Thus Turing has converted statements about each machine considered separately into a single "statement" (string) about all of them. Given the machine (he calls it G) that created this expression, he can test it with his machine E and determine if it ever produces a 0. In our first example above we see that indeed it does, so we know that not all the M's in our sequence print 0s. But the second example shows that, since the string is blanks then every Mn in our sequence has produced a 0.
All that remains for Turing to do is create a process to create the sequence of Mn's from a single M.
Suppose M prints this pattern:
M => ...AB01AB0010AB…