Entscheidungsproblem

Uses your system voice; voice and rate in settings.

Snapshot

≈ 7 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematics and computer science, the ; ) is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928. It asks for an algorithm that considers an input statement and answers "yes" or "no" according to whether it is universally valid, i.e., valid in every structure. Such an algorithm was proven to be impossible by Alonzo Church and Alan Turing in 1936.

In mathematics and computer science, the ; ) is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928. It asks for an algorithm that considers an input statement and answers "yes" or "no" according to whether it is universally valid, i.e., valid in every structure. Such an algorithm was proven to be impossible by Alonzo Church and Alan Turing in 1936.

Completeness theorem

By 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 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 showing that a general solution to the 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. 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: \forall x, p(x) \to \pm q(x), \quad \exists x, p(x) \wedge \pm q(x) where p, q are atomic predicates, and +q := q, \; -q := \neg q . Given a finite set of Aristotelian logic formulas, it is NLOGSPACE-complete to decide its \rm{Sat} . It is also NLOGSPACE-complete to decide \rm{Sat} for a slight extension (Theorem 2.7): \forall x, \pm p(x) \to \pm q(x), \quad \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 \forall x, \rm{body}(x), \exists y, \rm{body}(y) \wedge \rm{love}(x, y) . Generally, we have 8 kinds of sentences: \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} It is NLOGSPACE-complete to decide its \rm{Sat} (Theorem 2.15).

Relational logic can be extended to 32 kinds of sentences by allowing \pm p, \pm q , but this extension is EXPTIME-complete (Theorem 2.24). 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, [\exists^*\forall^*]_= , is the class of first-order formulas with quantifier prefix \exists\cdots\exists\forall\cdots \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 \forall \exists \forall \exists^6 , the problem \rm{Sat}(\forall \exists \forall \exists^6) is undecidable. The precise boundaries are known, sharply: \rm{Sat}(\forall \exists \forall) and \rm{Sat}([\forall \exists \forall]_{=} ) are co-RE-complete, and the \rm{FinSat} problems are RE-complete (Theorem 5.2).

Same for \forall^3 \exists (Theorem 5.3). \exists^* \forall^2 \exists^* is decidable, proved independently by Gödel, Schütte, and Kalmár. [\forall^2 \exists]_= is undecidable. For any n \geq 0 , both \rm{Sat}(\exists^n \forall^*) and \rm{Sat}([\exists^n \forall^*]_=) are NEXPTIME-complete (Theorem 5.1). This implies that \rm{Sat}( [\exists^*\forall^*]_= ) is decidable, a result first published by Bernays and Schönfinkel. For any n \geq 0, m \geq 2 , \rm{Sat}(\exists^n \forall \exists^m ) is EXPTIME-complete (Section 5.4.1).

For any n \geq 0 , \rm{Sat}([\exists^n \forall \exists^*]_=) is NEXPTIME-complete (Section 5.4.2). This implies that \rm{Sat}(\exists^*\forall^*\exists^*) is decidable, a result first published by Ackermann. For any n \geq 0 , \rm{Sat}(\exists^n \forall \exists) and \rm{Sat}([\exists^n \forall \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.

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: from journal website, from Turing Digital Archive, from abelard.org. Errata appeared in Series 2, 43 (1937), pp 544–546. 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.

Biography of Alan M. Turing. Cf Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof. Soare, Robert I., "Computability and recursion", Bull. Symbolic Logic 2 (1996), no. 3, 284–321. 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. 3ff. Whitehead, Alfred North; 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. 37ff, and Chap. 2.VIII. "The Contradictions" p. 60 ff.

External links

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375684114 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

4 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.