Editing Turing machine (section)

===The Entscheidungsproblem (the "decision problem"): Hilbert's tenth question of 1900===
With regard to [[Hilbert's problems]] posed by the famous mathematician [[David Hilbert]] in 1900, an aspect of [[Hilbert's tenth problem|problem #10]] had been floating about for almost 30 years before it was framed precisely. Hilbert's original expression for No. 10 is as follows:

{{blockquote|''10. Determination of the solvability of a Diophantine equation''. Given a [[Diophantine equation]] with any number of unknown quantities and with rational integral coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.

The Entscheidungsproblem [decision problem for [[first-order logic]]] is solved when we know a procedure that allows for any given logical expression to decide by finitely many operations its validity or satisfiability ... The Entscheidungsproblem must be considered the main problem of mathematical logic.|quoted, with this translation and the original German, in Dershowitz and Gurevich, 2008}}

By 1922, this notion of "[[Entscheidungsproblem]]" had developed a bit, and [[Heinrich Behmann|H. Behmann]] stated that

{{blockquote|...&nbsp;most general form of the Entscheidungsproblem [is] as follows:
<blockquote>A quite definite generally applicable prescription is required which will allow one to decide in a finite number of steps the truth or falsity of a given purely logical assertion ...</blockquote>|Gandy p. 57, quoting Behmann}}
{{blockquote|Behmann remarks that ... the general problem is equivalent to the problem of deciding which mathematical propositions are true.|''ibid.''}}
{{blockquote|If one were able to solve the Entscheidungsproblem then one would have a "procedure for solving many (or even all) mathematical problems".|''ibid.'', p. 92}}

By the 1928 international congress of mathematicians, Hilbert "made his questions quite precise. First, was mathematics ''[[Completeness (logic)|complete]]'' ... Second, was mathematics ''[[Consistency proof|consistent]]'' ... And thirdly, was mathematics ''[[Decidability (logic)|decidable]]''?" (Hodges p.&nbsp;91, Hawking p.&nbsp;1121). The first two questions were answered in 1930 by [[Kurt Gödel]] at the very same meeting where Hilbert delivered his retirement speech (much to the chagrin of Hilbert); the third—the Entscheidungsproblem—had to wait until the mid-1930s.

The problem was that an answer first required a precise definition of "definite general applicable prescription", which Princeton professor [[Alonzo Church]] would come to call "[[effective calculability]]", and in 1928 no such definition existed. But over the next 6–7 years [[Emil Post]] developed his definition of a worker moving from room to room writing and erasing marks per a list of instructions (Post 1936), as did Church and his two students [[Stephen Kleene]] and [[J. B. Rosser]] by use of Church's lambda-calculus and Gödel's [[recursion theory]] (1934). Church's paper (published 15 April 1936) showed that the Entscheidungsproblem was indeed "undecidable"<ref>The narrower question posed in [[Hilbert's tenth problem]], about [[Diophantine equation]]s, remains unresolved until 1970, when the relationship between [[recursively enumerable set]]s and [[Diophantine set]]s is finally laid bare.</ref> and beat Turing to the punch by almost a year (Turing's paper submitted 28 May 1936, published January 1937). In the meantime, Emil Post submitted a brief paper in the fall of 1936, so Turing at least had priority over Post. While Church refereed Turing's paper, Turing had time to study Church's paper and add an Appendix where he sketched a proof that Church's lambda-calculus and his machines would compute the same functions.

{{blockquote|But what Church had done was something rather different, and in a certain sense weaker. ... the Turing construction was more direct, and provided an argument from first principles, closing the gap in Church's demonstration.|Hodges p. 112}}

And Post had only proposed a definition of [[Church–Turing thesis|calculability]] and criticised Church's "definition", but had proved nothing.