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:
- 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))
- 1946: Post correspondence problem (cf Hopcroft and Ullman p. 193ff, p. 407 for the reference)
- 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).
- Rice's theorem: a generalized formulation of Turing's second theorem (cf Hopcroft and Ullman p. 185ff)
- 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.)
- Penrose tiling questions
- Question of solutions for Diophantine equations and the resultant answer in the MRDP Theorem; see entry below.
Read more about this topic: Proof Of Impossibility
Famous quotes containing the words machine, lock and/or proof:
“I find it hard to believe that the machine would go into the creative artist’s hand even were that magic hand in true place. It has been too far exploited by industrialism and science at expense to art and true religion.”
—Frank Lloyd Wright (1869–1959)
“Time, which shows so vacant, indivisible, and divine in its coming, is slit and peddled into trifles and tatters. A door is to be painted, a lock to be repaired. I want wood, or oil, or meal, or salt; the house smokes, or I have a headache; then the tax; and an affair to be transacted with a man without heart or brains; and the stinging recollection of an injurious or very awkward word,—these eat up the hours.”
—Ralph Waldo Emerson (1803–1882)
“He who has never failed somewhere, that man can not be great. Failure is the true test of greatness. And if it be said, that continual success is a proof that a man wisely knows his powers,—it is only to be added, that, in that case, he knows them to be small.”
—Herman Melville (1819–1891)