Entscheidungsproblem

History

The origin of the 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 values of mathematical statements. 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 Entscheidungsproblem". In 1929, Moses Schönfinkel published one paper on special cases of the Decision problem, that was prepared by Paul Bernays.

As late as 1930, Hilbert believed that there would be no such thing as an unsolvable problem.

Negative answer

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 λ-calculus, and by Alan Turing the next year with his concept of Turing machines. Turing immediately recognized that these are equivalent models of computation.

A negative answer to the Entscheidungsproblem was then given by Alonzo Church in 1935–36 (Church's theorem) and independently shortly thereafter by Alan Turing in 1936 (Turing's proof). Church proved that there is no computable function that decides, for two given λ-calculus expressions, whether they are equivalent or not. He relied heavily on earlier work by Stephen Kleene. Turing reduced the question of the existence of an 'algorithm' or 'general method' able to solve the Entscheidungsproblem to the question of the existence of a 'general method' that 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 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 incompleteness theorem, especially by the method of assigning numbers (a Gödel numbering) to logical formulas in order to reduce logic to arithmetic.

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

Generalizations

Using the deduction theorem, the Entscheidungsproblem encompasses the more general problem of deciding whether a given first-order sentence is a logical consequence of 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 decidable; examples of this include Presburger arithmetic, real closed fields, and static type systems of many programming languages. On the other hand, the first-order theory of the natural numbers with addition and multiplication expressed by Peano's axioms cannot be decided with an algorithm.

Fragments

By default, the citations in the section are from Pratt-Hartmann (2023).

The classical Entscheidungsproblem asks, 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.

Some notations: ${\displaystyle \mathrm{S}\mathrm{a}\mathrm{t}(\mathrm{\Phi })}$ means the problem of deciding whether there exists a model for a set of logical formulas ${\displaystyle \mathrm{\Phi }}$. ${\displaystyle \mathrm{F}\mathrm{i}\mathrm{n}\mathrm{S}\mathrm{a}\mathrm{t}(\mathrm{\Phi })}$ is the same problem, but for finite models. The ${\displaystyle \mathrm{S}\mathrm{a}\mathrm{t}}$-problem for a logical fragment is called decidable if there exists a program that can decide, for each ${\displaystyle \mathrm{\Phi }}$ finite set of logical formulas in the fragment, whether ${\displaystyle \mathrm{S}\mathrm{a}\mathrm{t}(\mathrm{\Phi })}$ 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

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:$${\displaystyle \mathrm{\forall }x,p(x)\to \pm q(x),\mathrm{\exists }x,p(x)\wedge \pm q(x)}$$where ${\displaystyle p,q}$ are atomic predicates, and ${\displaystyle +q:=q,-q:=\mathrm{\neg }q}$. Given a finite set of Aristotelian logic formulas, it is NLOGSPACE-complete to decide its ${\displaystyle \mathrm{S}\mathrm{a}\mathrm{t}}$. It is also NLOGSPACE-complete to decide ${\displaystyle \mathrm{S}\mathrm{a}\mathrm{t}}$ for a slight extension (Theorem 2.7):$${\displaystyle \mathrm{\forall }x,\pm p(x)\to \pm q(x),\mathrm{\exists }x,\pm p(x)\wedge \pm q(x)}$$Relational logic extends Aristotelian logic by allowing a relational predicate. For example, "Everybody loves somebody" can be written as $\mathrm{\forall }x,\mathrm{b}\mathrm{o}\mathrm{d}\mathrm{y}(\mathrm{x}),\mathrm{\exists }\mathrm{y},\mathrm{b}\mathrm{o}\mathrm{d}\mathrm{y}(\mathrm{y})\wedge \mathrm{l}\mathrm{o}\mathrm{v}\mathrm{e}(\mathrm{x},\mathrm{y})$. Generally, we have 8 kinds of sentences:$${\displaystyle \begin{array}{cc}\mathrm{\forall }x,p(x)\to (\mathrm{\forall }y,q(x)\to \pm r(x,y)),& \mathrm{\forall }x,p(x)\to (\mathrm{\exists }y,q(x)\wedge \pm r(x,y))\\ \mathrm{\exists }x,p(x)\wedge (\mathrm{\forall }y,q(x)\to \pm r(x,y)),& \mathrm{\exists }x,p(x)\wedge (\mathrm{\exists }y,q(x)\wedge \pm r(x,y))\end{array}}$$It is NLOGSPACE-complete to decide its ${\displaystyle \mathrm{S}\mathrm{a}\mathrm{t}}$ (Theorem 2.15). Relational logic can be extended to 32 kinds of sentences by allowing ${\displaystyle \pm p,\pm q}$, but this extension is EXPTIME-complete (Theorem 2.24).

Arity

The first-order logic fragment where the only variable names are ${\displaystyle x,y}$ is NEXPTIME-complete (Theorem 3.18). With ${\displaystyle x,y,z}$, it is co-RE-complete to decide its ${\displaystyle \mathrm{S}\mathrm{a}\mathrm{t}}$, and RE-complete to decide ${\displaystyle \mathrm{F}\mathrm{i}\mathrm{n}\mathrm{S}\mathrm{a}\mathrm{t}}$ (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 ${\displaystyle \mathrm{S}\mathrm{a}\mathrm{t}}$ 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, ${\displaystyle [{\mathrm{\exists }}^{\ast }{\mathrm{\forall }}^{\ast }{]}_{=}}$, is the class of first-order formulas with quantifier prefix ${\displaystyle \mathrm{\exists }\cdots \mathrm{\exists }\mathrm{\forall }\cdots \mathrm{\forall }}$, equality and relation symbols, and no 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 ${\displaystyle \mathrm{\forall }\mathrm{\exists }\mathrm{\forall }{\mathrm{\exists }}^6}$, the problem ${\displaystyle \mathrm{S}\mathrm{a}\mathrm{t}(\mathrm{\forall }\mathrm{\exists }\mathrm{\forall }{\mathrm{\exists }}^6)}$ is undecidable.

The precise boundaries are known, sharply:

• ${\displaystyle \mathrm{S}\mathrm{a}\mathrm{t}(\mathrm{\forall }\mathrm{\exists }\mathrm{\forall })}$ and ${\displaystyle \mathrm{S}\mathrm{a}\mathrm{t}([\mathrm{\forall }\mathrm{\exists }\mathrm{\forall }{]}_{=})}$are co-RE-complete, and the ${\displaystyle \mathrm{F}\mathrm{i}\mathrm{n}\mathrm{S}\mathrm{a}\mathrm{t}}$ problems are RE-complete (Theorem 5.2).
• Same for ${\displaystyle {\mathrm{\forall }}^3\mathrm{\exists }}$ (Theorem 5.3).
• ${\displaystyle {\mathrm{\exists }}^{\ast }{\mathrm{\forall }}^2{\mathrm{\exists }}^{\ast }}$ is decidable, proved independently by Gödel, Schütte, and Kalmár.
• ${\displaystyle [{\mathrm{\forall }}^2\mathrm{\exists }{]}_{=}}$ is undecidable.
• For any ${\displaystyle n\ge 0}$, both ${\displaystyle \mathrm{S}\mathrm{a}\mathrm{t}({\mathrm{\exists }}^{\mathrm{n}}{\mathrm{\forall }}^{\ast })}$ and ${\displaystyle \mathrm{S}\mathrm{a}\mathrm{t}([{\mathrm{\exists }}^{\mathrm{n}}{\mathrm{\forall }}^{\ast }{]}_{=})}$ are NEXPTIME-complete (Theorem 5.1).
  • This implies that ${\displaystyle \mathrm{S}\mathrm{a}\mathrm{t}([{\mathrm{\exists }}^{\ast }{\mathrm{\forall }}^{\ast }{]}_{=})}$ is decidable, a result first published by Bernays and Schönfinkel.
• For any ${\displaystyle n\ge 0,m\ge 2}$, ${\displaystyle \mathrm{S}\mathrm{a}\mathrm{t}({\mathrm{\exists }}^{\mathrm{n}}\mathrm{\forall }{\mathrm{\exists }}^{\mathrm{m}})}$ is EXPTIME-complete (Section 5.4.1).
• For any ${\displaystyle n\ge 0}$, ${\displaystyle \mathrm{S}\mathrm{a}\mathrm{t}([{\mathrm{\exists }}^{\mathrm{n}}\mathrm{\forall }{\mathrm{\exists }}^{\ast }{]}_{=})}$ is NEXPTIME-complete (Section 5.4.2).
  • This implies that ${\displaystyle \mathrm{S}\mathrm{a}\mathrm{t}({\mathrm{\exists }}^{\ast }{\mathrm{\forall }}^{\ast }{\mathrm{\exists }}^{\ast })}$ is decidable, a result first published by Ackermann.
• For any ${\displaystyle n\ge 0}$, ${\displaystyle \mathrm{S}\mathrm{a}\mathrm{t}({\mathrm{\exists }}^{\mathrm{n}}\mathrm{\forall }\mathrm{\exists })}$ and ${\displaystyle \mathrm{S}\mathrm{a}\mathrm{t}([{\mathrm{\exists }}^{\mathrm{n}}\mathrm{\forall }\mathrm{\exists }{]}_{=})}$ are PSPACE-complete (Section 5.4.3).

Börger et al. (2001) 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 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'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 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 fields, is decidable; this is the Tarski–Seidenberg theorem, which has been implemented in computers by using the cylindrical algebraic decomposition.