Turing's Proof - Complications

Complications

Turing's proof is complicated by a large number of definitions, and confounded with what Martin Davis called "petty technical details" and "...technical details are incorrect as given" (Davis's commentary in Undecidable, p. 115) . Turing himself published "A correction" in 1937: "The author is indebted to P. Bernays 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" they are adivsed to 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 0s and 1s. 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., 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 mathematicians who had to resort to practical computation..." (Hodges p. 124)