View source for Entscheidungsproblem

{{short description|Impossible task in computing}}
{{italic title}}
{{Use dmy dates|date=August 2021}}
In [[mathematics]] and [[computer science]], the {{lang for|de|'''Entscheidungsproblem'''|decision problem|paren=left}}; {{IPA|de|ɛntˈʃaɪ̯dʊŋspʁoˌbleːm|pron}}) is a challenge posed by [[David Hilbert]] and [[Wilhelm Ackermann]] in 1928.<ref>David Hilbert and Wilhelm Ackermann. Grundzüge der Theoretischen Logik. Springer, Berlin, Germany, 1928. English translation: David Hilbert and Wilhelm Ackermann. Principles of Mathematical Logic. AMS Chelsea Publishing, Providence, Rhode Island, USA, 1950</ref> It asks for an [[algorithm]] that considers an inputted statement and answers "yes" or "no" according to whether it is universally valid, i.e., valid in every [[Structure (mathematical logic)|structure]]. Such an algorithm was proven to be impossible by [[Alonzo Church]] and [[Alan Turing]] in 1936.

==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]].

== History ==
The origin of the {{lang|de|Entscheidungsproblem}} goes back to [[Gottfried Leibniz]], who in the seventeenth century, after having constructed a successful mechanical [[calculating machine]], dreamt of building a machine that could manipulate symbols in order to determine the [[truth value]]s of mathematical statements.<ref>{{harvnb|Davis|2001|pp=3–20}}</ref> He realized that the first step would have to be a clean [[formal language]], and much of his subsequent work was directed toward that goal. In 1928, [[David Hilbert]] and [[Wilhelm Ackermann]] posed the question in the form outlined above.

In continuation of his "program", Hilbert posed three questions at an international conference in 1928, the third of which became known as "Hilbert's {{lang|de|Entscheidungsproblem}}".<ref>{{harvnb|Hodges|1983|p=91}}</ref> In 1929, [[Moses Schönfinkel]] published one paper on special cases of the decision problem, that was prepared by [[Paul Bernays]].<ref name="Kline">{{Citation | first1=G. L. | last1=Kline | title=Review of Foundations of mathematics and mathematical logic by S. A. Yanovskaya | journal=[[Journal of Symbolic Logic]] | volume=16 | pages=46–48 | year=1951 | doi=10.2307/2268665 | jstor=2268665 | issue=1 | last2=Anovskaa | first2=S. A.| s2cid=119004002 }}</ref>

As late as 1930, Hilbert believed that there would be no such thing as an unsolvable problem.<ref>{{harvnb|Hodges|1983|p=92}}, quoting from Hilbert</ref>

== Negative answer<!--'Church's theorem' redirects here--> ==
Before the question could be answered, the notion of "algorithm" had to be formally defined. This was done by [[Alonzo Church]] in 1935 with the concept of "effective calculability" based on his [[lambda calculus|λ-calculus]], and by Alan Turing the next year with his concept of [[Turing machine]]s. Turing immediately recognized that these are equivalent [[model of computation|models of computation]].

A negative answer to the {{lang|de|Entscheidungsproblem}} was then given by Alonzo Church in 1935–36 ('''Church's theorem'''<!--boldface per WP:R#PLA-->) and independently shortly thereafter by Alan Turing in 1936 ([[Turing's proof]]). Church proved that there is no [[computable function]] which decides, for two given λ-calculus expressions, whether they are equivalent or not. He relied heavily on earlier work by [[Stephen Cole Kleene|Stephen Kleene]]. Turing reduced the question of the existence of an 'algorithm' or 'general method' able to solve the {{lang|de|Entscheidungsproblem}} to the question of the existence of a 'general method' which decides whether any given Turing machine halts or not (the [[halting problem]]). If 'algorithm' is understood as meaning a method that can be represented as a Turing machine, and with the answer to the latter question negative (in general), the question about the existence of an algorithm for the {{lang|de|Entscheidungsproblem}} also must be negative (in general). In his 1936 paper, Turing says: "Corresponding to each computing machine 'it' we construct a formula 'Un(it)' and we show that, if there is a general method for determining whether 'Un(it)' is provable, then there is a general method for determining whether 'it' ever prints 0".

The work of both Church and Turing was heavily influenced by [[Kurt Gödel]]'s earlier work on his [[Gödel's incompleteness theorem|incompleteness theorem]], especially by the method of assigning numbers (a [[Gödel numbering]]) to logical formulas in order to reduce logic to arithmetic.

The ''{{lang|de|Entscheidungsproblem}}'' is related to [[Hilbert's tenth problem]], which asks for an [[algorithm]] to decide whether [[Diophantine equation]]s have a solution.  The non-existence of such an algorithm, established by the work of [[Yuri Matiyasevich]], [[Julia Robinson]], [[Martin Davis (mathematician)|Martin Davis]], and [[Hilary Putnam]], with the final piece of the proof in 1970, also implies a negative answer to the ''Entscheidungsproblem''.

== Generalizations ==
{{Main|Decidability (logic)#Decidability of a theory}}

Using the [[deduction theorem]], the Entscheidungsproblem encompasses the more general problem of deciding whether a given first-order sentence is entailed by a given finite set of sentences, but validity in first-order theories with infinitely many axioms cannot be directly reduced to the Entscheidungsproblem. Such more general decision problems are of practical interest. Some first-order theories are algorithmically [[decidability (logic)|decidable]]; examples of this include [[Presburger arithmetic]], [[real closed field]]s, and [[Type system#Static typing|static type systems]] of many [[programming language]]s. On the other hand, the first-order theory of the [[natural number]]s with addition and multiplication expressed by [[Peano axioms|Peano's axioms]] cannot be decided with an algorithm.

== Fragments ==
By default, the citations in the section are from Pratt-Hartmann (2023).<ref name=":0">{{Cite book |last=Pratt-Hartmann |first=Ian |url=https://academic.oup.com/book/46400 |title=Fragments of First-Order Logic |date=2023-03-30 |publisher=Oxford University Press |isbn=978-0-19-196006-2 |language=en}}</ref>

The classical ''Entscheidungsproblem'' asks that, given a first-order formula, whether it is true in all models. The finitary problem asks whether it is true in all finite models. [[Trakhtenbrot's theorem]] shows that this is also undecidable.<ref>B. Trakhtenbrot. ''The impossibility of an algorithm for the decision problem for finite models''. Doklady Akademii Nauk, 70:572–596, 1950. English translation: AMS Translations Series 2, vol. 33 (1963), pp. 1–6.</ref><ref name=":0" />

Some notations: <math>\rm{Sat} (\Phi) </math> means the problem of deciding whether there exists a model for a set of logical formulas <math>\Phi  </math>. <math>\rm{FinSat} (\Phi) </math> is the same problem, but for ''finite'' models. The <math>\rm{Sat}  </math>-problem for a [[logical fragment]] is called decidable if there exists a program that can decide, for each <math>\Phi  </math> finite set of logical formulas in the fragment, whether <math>\rm{Sat} (\Phi) </math> or not.

There is a hierarchy of decidabilities. On the top are the undecidable problems. Below it are the decidable problems. Furthermore, the decidable problems can be divided into a complexity hierarchy.

=== Aristotelian and relational ===
[[Term logic|Aristotelian logic]] considers 4 kinds of sentences: "All p are q", "All p are not q", "Some p is q", "Some p is not q". We can formalize these kinds of sentences as a fragment of first-order logic:<math display="block">\forall x, p(x) \to \pm  q(x), \quad \exists x, p(x) \wedge \pm  q(x) </math>where <math>p, q </math> are atomic predicates, and <math>+q := q, \; -q := \neg q </math>. Given a finite set of Aristotelean logic formulas, it is [[NL (complexity)|NLOGSPACE]]-complete to decide its <math>\rm{Sat}  </math>. It is also NLOGSPACE-complete to decide <math>\rm{Sat}  </math> for a slight extension (Theorem 2.7):<math display="block">\forall x, \pm p(x) \to \pm  q(x), \quad \exists x, \pm p(x) \wedge \pm  q(x) </math>[[Relational algebra|Relational logic]] extends Aristotelean logic by allowing a relational predicate. For example, "Everybody loves somebody" can be written as <math display="inline">\forall x, \rm{body}(x), \exists y, \rm{body}(y) \wedge \rm{love}(x, y)  </math>. Generally, we have 8 kinds of sentences:<math display="block">\begin{aligned}
\forall x, p(x) \to (\forall y, q(x) \to \pm r(x, y)), &\quad \forall x, p(x) \to (\exists y, q(x) \wedge \pm r(x, y))  \\
\exists x, p(x) \wedge (\forall y, q(x) \to \pm r(x, y)), &\quad \exists x, p(x) \wedge (\exists y, q(x) \wedge \pm r(x, y)) 
\end{aligned} </math>It is [[NL (complexity)|NLOGSPACE]]-complete to decide its <math>\rm{Sat}  </math> (Theorem 2.15). Relational logic can be extended to 32 kinds of sentences by allowing <math>\pm p, \pm q  </math>, but this extension is [[EXPTIME]]-complete (Theorem 2.24).

=== Arity ===
The first-order logic fragment where the only variable names are <math>x, y  </math> is [[NEXPTIME]]-complete (Theorem 3.18). With <math>x, y, z </math>, it is [[RE (complexity)|RE]]-complete to decide its <math>\rm{Sat}  </math>, and co-RE-complete to decide <math>\rm{FinSat}  </math> (Theorem 3.15), thus undecidable.

The [[monadic predicate calculus]] is the fragment where each formula contains only 1-ary predicates and no function symbols. Its  <math>\rm{Sat}  </math> is NEXPTIME-complete (Theorem 3.22).

=== Quantifier prefix ===
Any first-order formula has a prenex normal form. For each possible quantifier prefix to the prenex normal form, we have a fragment of first-order logic. For example, the [[Bernays–Schönfinkel class]], <math>[\exists^*\forall^*]_=  </math>, is the class of first-order formulas with quantifier prefix <math>\exists\cdots\exists\forall\cdots \forall     </math>, equality symbols, and no [[Function symbol|function symbols]].

For example, Turing's 1936 paper (p. 263) observed that since the halting problem for each Turing machine is equivalent to a first-order logical formula of form  <math>\forall \exists \forall \exists^6 </math>, the problem <math>\rm{Sat}(\forall \exists \forall \exists^6)    </math> is undecidable.

The precise boundaries are known, sharply:

* <math>\rm{Sat}(\forall \exists \forall)  </math> and <math>\rm{Sat}([\forall \exists \forall]_{=} ) </math>are co-RE-complete, and the <math>\rm{FinSat}  </math> problems are RE-complete (Theorem 5.2).
* Same for <math>\forall^3 \exists  </math> (Theorem 5.3).
* <math>\exists^* \forall^2 \exists^* </math> is decidable, proved independently by Gödel, Schütte, and Kalmár. 
* <math>[\forall^2 \exists]_=  </math> is undecidable.
* For any <math>n \geq 0  </math>, both <math>\rm{Sat}(\exists^n \forall^*) </math> and <math>\rm{Sat}([\exists^n \forall^*]_=)  </math> are NEXPTIME-complete (Theorem 5.1).
** This implies that <math>\rm{Sat}( [\exists^*\forall^*]_= ) </math> is decidable, a result first published by Bernays and Schönfinkel.<ref>{{Cite journal |last1=Bernays |first1=Paul |last2=Schönfinkel |first2=Moses |date=December 1928 |title=Zum Entscheidungsproblem der mathematischen Logik |url=http://link.springer.com/10.1007/BF01459101 |journal=Mathematische Annalen |language=de |volume=99 |issue=1 |pages=342–372 |doi=10.1007/BF01459101 |s2cid=122312654 |issn=0025-5831}}</ref>
* For any <math>n \geq 0, m \geq 2   </math>, <math>\rm{Sat}(\exists^n \forall \exists^m )  </math> is EXPTIME-complete (Section 5.4.1).
* For any <math>n \geq 0 </math>, <math>\rm{Sat}([\exists^n \forall \exists^*]_=)   </math> is NEXPTIME-complete (Section 5.4.2).
** This implies that <math>\rm{Sat}(\exists^*\forall^*\exists^*) </math> is decidable, a result first published by Ackermann.<ref>{{Cite journal |last=Ackermann |first=Wilhelm |date=1928-12-01 |title=Über die Erfüllbarkeit gewisser Zählausdrücke |url=https://doi.org/10.1007/BF01448869 |journal=Mathematische Annalen |language=de |volume=100 |issue=1 |pages=638–649 |doi=10.1007/BF01448869 |s2cid=119646624 |issn=1432-1807}}</ref>
* For any <math>n \geq 0 </math>, <math>\rm{Sat}(\exists^n \forall \exists)   </math> and <math>\rm{Sat}([\exists^n \forall \exists]_=)   </math> are PSPACE-complete (Section 5.4.3).

Börger et al. (2001)<ref>{{Cite book |last1=Börger |first1=Egon |title=The classical decision problem |last2=Grädel |first2=Erich |last3=Gurevič |first3=Jurij |last4=Gurevich |first4=Yuri |date=2001 |publisher=Springer |isbn=978-3-540-42324-9 |edition=2. printing of the 1. |series=Universitext |location=Berlin}}</ref> describes the level of computational complexity for every possible fragment with every possible combination of quantifier prefix, functional arity, predicate arity, and equality/no-equality.

==Practical decision procedures==
Having practical decision procedures for classes of logical formulas is of considerable interest for [[program verification]] and circuit verification. Pure Boolean logical formulas are usually decided using [[Boolean satisfiability problem|SAT-solving]] techniques based on the [[DPLL algorithm]].

For more general decision problems of first-order theories, conjunctive formulas over linear real or rational arithmetic can be decided using the [[simplex algorithm]], formulas in linear integer arithmetic ([[Presburger arithmetic]]) can be decided using [[Cooper's algorithm]] or [[William Pugh (computer scientist)|William Pugh]]'s [[Omega test]]. Formulas with negations, conjunctions and disjunctions combine the difficulties of satisfiability testing with that of decision of conjunctions; they are generally decided nowadays using [[satisfiability modulo theories|SMT-solving]] techniques, which combine SAT-solving with decision procedures for conjunctions and propagation techniques. Real polynomial arithmetic, also known as the theory of [[real closed field]]s, is decidable; this is the [[Tarski–Seidenberg theorem]], which has been implemented in computers by using the [[cylindrical algebraic decomposition]].

== See also ==
* [[Automated theorem proving]]
* [[Hilbert's second problem]]
* [[Oracle machine]]
* [[Turing's proof]]

== Notes ==
{{Reflist}}

== References ==
* {{Cite book |last1=Hilbert |first1=David |title=Grundzüge der theoretischen Logik |last2=Ackermann |first2=Wilhelm |publisher=[[Springer-Verlag]] |year=1928 |isbn=0821820249 |language=de |trans-title=Principles of mathematical logic |author-link=David Hilbert |author-link2=Wilhelm Ackermann}}
* [[Alonzo Church]], "An unsolvable problem of [[elementary number theory]]", American Journal of Mathematics, 58 (1936), pp 345–363
* [[Alonzo Church]], "A note on the Entscheidungsproblem", Journal of Symbolic Logic, 1 (1936), pp 40–41.
* {{Cite book |last=Davis |first=Martin |title=Engines of logic: mathematicians and the origin of the computer |date=2001 |publisher=Norton |isbn=978-0-393-32229-3 |edition=1. publ. as Norton paperback |series=Norton paperback |location=New York, NY London |author-link=Martin Davis (mathematician)}}
* [[Alan Turing]], "[[On Computable Numbers, with an Application to the Entscheidungsproblem]]", Proceedings of the [[London Mathematical Society]], Series 2, 42 (1936–7), pp 230–265. Online versions: [https://wayback.archive-it.org/all/20171002211121/https://academic.oup.com/plms/article-abstract/s2-42/1/230/1491926/On-Computable-Numbers-with-an-Application-to-the?redirectedFrom=fulltext from journal website], [https://web.archive.org/web/20031007003709/http://www.turingarchive.org/browse.php/B/12 from Turing Digital Archive], [http://www.abelard.org/turpap2/tp2-ie.asp from abelard.org].  Errata appeared in Series 2, 43 (1937), pp 544–546.
* [[Martin Davis (mathematician)|Davis, Martin]], "The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions", Raven Press, New York, 1965. Turing's paper is #3 in this volume. Papers include those by Gödel, Church, Rosser, Kleene, and Post.
* {{Cite book |last=Hodges |first=Andrew |title=Alan Turing: the enigma |title-link=Alan Turing: The Enigma |date=1983 |publisher=Simon and Schuster |isbn=978-0-671-49207-6 |location=New York |author-link=Andrew Hodges}} Biography of Alan M. Turing. Cf Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof. 
* [[Robert Soare|Soare, Robert I.]], "Computability and recursion", Bull. Symbolic Logic 2 (1996), no. 3, 284–321. 
* [[Stephen Toulmin|Toulmin, Stephen]], "Fall of a Genius", a book review of "[[Alan Turing: The Enigma]] by Andrew Hodges", in The New York Review of Books, 19 January 1984, p.&nbsp;3ff.
* [[Alfred North Whitehead|Whitehead, Alfred North]]; [[Bertrand Russell|Russell, Bertrand]], Principia Mathematica to *56, Cambridge at the University Press, 1962. Re: the problem of paradoxes, the authors discuss the problem, that a set not be an object in any of its "determining functions", in particular "Introduction, Chap. 1 p. 24 "...difficulties which arise in formal logic", and Chap. 2.I. "The Vicious-Circle Principle" p.&nbsp;37ff, and Chap. 2.VIII. "The Contradictions" p.&nbsp;60 ff.

==External links==
* {{wiktionary-inline}}

{{Mathematical logic}}
{{Metalogic}}

[[Category:Theory of computation]]
[[Category:Computability theory]]
[[Category:Gottfried Wilhelm Leibniz]]
[[Category:Mathematical logic]]
[[Category:Metatheorems]]
[[Category:Undecidable problems]]