Editing Entscheidungsproblem (section)

==Completeness theorem==
By [[Gödel's completeness theorem|the completeness theorem of first-order logic]], a statement is universally valid if and only if it can be deduced using logical rules and axioms, so the ''{{lang|de|Entscheidungsproblem}}'' can also be viewed as asking for an algorithm to decide whether a given statement is provable using the [[rules of logic]].

In 1936, [[Alonzo Church]] and [[Alan Turing]] published independent papers<ref>Church's paper was presented to the American Mathematical Society on 19 April 1935 and published on 15 April 1936. Turing, who had made substantial progress in writing up his own results, was disappointed to learn of Church's proof upon its publication (see correspondence between [[Max Newman]] and Church in [https://findingaids.princeton.edu/collections/C0948/c00385 Alonzo Church papers]). Turing quickly completed his paper and rushed it to publication; it was received by the ''Proceedings of the London Mathematical Society'' on 28 May 1936, read on 12 November 1936, and published in series 2, volume 42 (1936–7); it appeared in two sections: in Part 3 (pages 230–240), issued on 30 Nov 1936 and in Part 4 (pages 241–265), issued on 23 Dec 1936; Turing added corrections in volume 43 (1937), pp. 544–546. See the footnote at the end of Soare: 1996.</ref> showing that a general solution to the ''{{lang|de|Entscheidungsproblem}}'' is impossible, assuming that the intuitive notion of "[[effectively calculable]]" is captured by the functions computable by a [[Turing machine]] (or equivalently, by those expressible in the [[lambda calculus]]). This assumption is now known as the [[Church–Turing thesis]].