Proof of Impossibility - Will This Computing Machine Lock in A "circle"? Turing's First Proof

Will This Computing Machine Lock in A "circle"? Turing's First Proof

• The Entscheidungsproblem, the decision problem, was first answered by Church in April 1935 and preempted Turing by over a year, as Turing's paper was received for publication in May 1936. (Also received for publication in 1936—in October, later than Turing's—was a short paper by Emil Post that discussed the reduction of an algorithm to a simple machine-like "method" very similar to Turing's computing machine model (see Post-Turing machine for details).

• Turing's proof is made difficult by number of definitions required and its subtle nature. See Turing machine and Turing's proof for details.

• Turing's first proof (of three) follows the schema of Richard's Paradox: Turing's computing machine is an algorithm represented by a string of seven letters in a "computing machine". Its "computation" is to test all computing machines (including itself) for "circles", and form a diagonal number from the computations of the non-circular or "successful" computing machines. It does this, starting in sequence from 1, by converting the numbers (base 8) into strings of seven letters to test. When it arrives at its own number, it creates its own letter-string. It decides it is the letter-string of a successful machine, but when it tries to do this machine's (its own) computation it locks in a circle and can't continue. Thus we have arrived at Richard's paradox. (If you are bewildered see Turing's proof for more).

A number of similar undecidability proofs appeared soon before and after Turing's proof:

1. April 1935: Proof of Alonzo Church (An Unsolvable Problem of Elementary Number Theory). His proof was to "...propose a definition of effective calculability ... and to show, by means of an example, that not every problem of this class is solvable" (Undecidable p. 90))
2. 1946: Post correspondence problem (cf Hopcroft and Ullman p. 193ff, p. 407 for the reference)
3. April 1947: Proof of Emil Post (Recursive Unsolvability of a Problem of Thue) (Undecidable p. 293). This has since become known as "The Word problem of Thue" or "Thue's Word Problem" (Axel Thue proposed this problem in a paper of 1914 (cf References to Post's paper in Undecidable, p. 303).
4. Rice's theorem: a generalized formulation of Turing's second theorem (cf Hopcroft and Ullman p. 185ff)
5. Greibach's theorem: undecidability in language theory (cf Hopcroft and Ullman p. 205ff and reference on p. 401 ibid: Greibach "The undecidability of the ambiguity problem for minimal lineal grammars," Information and Control 6:2, 117-125, also reference on p. 402 ibid: Greibach "A note on undecidable properties of formal languages", Math Systems Theory 2:1, 1-6.)
6. Penrose tiling questions
7. Question of solutions for Diophantine equations and the resultant answer in the MRDP Theorem; see entry below.