Turing's Proof - Summary of The Proofs

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 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 is computable" (U p. 132). 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 of an arbitrary machine M, will determine whether M ever prints a given symbol (0 say)" (his italics, U p. 134).

Third proof: Readers who brave Proof #3 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 e.g. Ernest Nagel and James R. Newman, Godel’s Proof, New York University Press, 1958.

"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 appears on the tape in some complete configuration of M, then Un(M) is provable" (p. 147)

"Lemma 2: If Un(M) is provable then S1 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).