Movatterモバイル変換

Entscheidungsproblem

From Wikipedia, the free encyclopedia

Impossible task in computing

This article is about the decision problem in formal logic. For decision problems in complexity theory, seeDecision problem.

Inmathematics andcomputer science, theEntscheidungsproblem (German for 'decision problem';pronounced[ɛntˈʃaɪ̯dʊŋspʁoˌbleːm]) is a challenge posed byDavid Hilbert andWilhelm Ackermann in 1928.^[1] It asks for analgorithm that considers an inputted statement and answers "yes" or "no" according to whether it is universally valid, i.e., valid in everystructure. Such an algorithm was proven to be impossible byAlonzo Church andAlan Turing in 1936.

Completeness theorem

[edit]

Bythe 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 theEntscheidungsproblem can also be viewed as asking for an algorithm to decide whether a given statement is provable using therules of logic.

In 1936,Alonzo Church andAlan Turing published independent papers^[2] showing that a general solution to theEntscheidungsproblem is impossible, assuming that the intuitive notion of "effectively calculable" is captured by the functions computable by aTuring machine (or equivalently, by those expressible in thelambda calculus). This assumption is now known as theChurch–Turing thesis.

History

[edit]

The origin of theEntscheidungsproblem goes back toGottfried Leibniz, who in the seventeenth century, after having constructed a successful mechanicalcalculating machine, dreamt of building a machine that could manipulate symbols in order to determine thetruth values of mathematical statements.^[3] He realized that the first step would have to be a cleanformal language, and much of his subsequent work was directed toward that goal. In 1928,David Hilbert andWilhelm 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'sEntscheidungsproblem".^[4] In 1929,Moses Schönfinkel published one paper on special cases of the decision problem, that was prepared byPaul Bernays.^[5]

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

Negative answer

[edit]

Before the question could be answered, the notion of "algorithm" had to be formally defined. This was done byAlonzo Church in 1935 with the concept of "effective calculability" based on hisλ-calculus, and by Alan Turing the next year with his concept ofTuring machines. Turing immediately recognized that these are equivalentmodels of computation.

A negative answer to theEntscheidungsproblem 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 nocomputable function that decides, for two given λ-calculus expressions, whether they are equivalent or not. He relied heavily on earlier work byStephen Kleene. Turing reduced the question of the existence of an 'algorithm' or 'general method' able to solve theEntscheidungsproblem to the question of the existence of a 'general method' that decides whether any given Turing machine halts or not (thehalting 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 theEntscheidungsproblem 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 byKurt Gödel's earlier work on hisincompleteness theorem, especially by the method of assigning numbers (aGödel numbering) to logical formulas in order to reduce logic to arithmetic.

TheEntscheidungsproblem is related toHilbert's tenth problem, which asks for analgorithm to decide whetherDiophantine equations have a solution. The non-existence of such an algorithm, established by the work ofYuri Matiyasevich,Julia Robinson,Martin Davis, andHilary Putnam, with the final piece of the proof in 1970, also implies a negative answer to theEntscheidungsproblem.

Generalizations

[edit]

Main article:Decidability (logic) § Decidability of a theory

Using thededuction theorem, theEntscheidungsproblem encompasses the more general problem of deciding whether a given first-order sentence is alogical consequence of a given finite set of sentences, but validity in first-order theories with infinitely many axioms cannot be directly reduced to theEntscheidungsproblem. Such more general decision problems are of practical interest. Some first-order theories are algorithmicallydecidable; examples of this includePresburger arithmetic,real closed fields, andstatic type systems of manyprogramming languages. On the other hand, the first-order theory of thenatural numbers with addition and multiplication expressed byPeano's axioms cannot be decided with an algorithm.

Fragments

[edit]

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

The classicalEntscheidungsproblem 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.^[8]^[7]

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

[edit]

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 {\displaystyle p,q}$ are atomic predicates, and $+q:=q,\;-q:=\neg q$ . Given a finite set of Aristotelean logic formulas, it isNLOGSPACE-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 Aristotelean logic by allowing a relational predicate. For example, "Everybody loves somebody" can be written as ${\textstyle \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 isNLOGSPACE-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 isEXPTIME-complete (Theorem 2.24).

Arity

[edit]

The first-order logic fragment where the only variable names are $x, y {\displaystyle x,y}$ isNEXPTIME-complete (Theorem 3.18). With $x, y, z {\displaystyle x,y,z}$ , it isco-RE-complete to decide its ${\rm {Sat}}$ , andRE-complete to decide ${\rm {FinSat}}$ (Theorem 3.15), thus undecidable.

Themonadic predicate calculus is the fragment where each formula contains only 1-ary predicates and no function symbols. Its ${\rm {Sat}}$ is NEXPTIME-complete (Theorem 3.22).

Quantifier prefix

[edit]

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, theBernays–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 nofunction 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, andKalmá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.^[9]
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.^[10]
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)^[11] 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

[edit]

Having practical decision procedures for classes of logical formulas is of considerable interest forprogram verification and circuit verification. Pure Boolean logical formulas are usually decided usingSAT-solving techniques based on theDPLL algorithm.

For more general decision problems of first-order theories, conjunctive formulas overlinear real or rational arithmetic can be decided using thesimplex algorithm, formulas in linear integer arithmetic (Presburger arithmetic) can be decided usingCooper's algorithm orWilliam Pugh'sOmega test. Formulas with negations, conjunctions and disjunctions combine the difficulties of satisfiability testing with that of decision of conjunctions; they are generally decided nowadays usingSMT-solving techniques, which combine SAT-solving with decision procedures for conjunctions and propagation techniques. Real polynomial arithmetic, also known as the theory ofreal closed fields, is decidable; this is theTarski–Seidenberg theorem, which has been implemented in computers by using thecylindrical algebraic decomposition.

Notes

[edit]

^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
^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 betweenMax Newman and Church inAlonzo Church papers). Turing quickly completed his paper and rushed it to publication; it was received by theProceedings 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.
^Davis 2001, pp. 3–20
^Hodges 1983, p. 91
^Kline, G. L.; Anovskaa, S. A. (1951), "Review of Foundations of mathematics and mathematical logic by S. A. Yanovskaya",Journal of Symbolic Logic,16 (1):46–48,doi:10.2307/2268665,JSTOR 2268665,S2CID 119004002
^Hodges 1983, p. 92, quoting from Hilbert
^^a ^bPratt-Hartmann, Ian (30 March 2023).Fragments of First-Order Logic. Oxford University Press.ISBN 978-0-19-196006-2.
^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.
^Bernays, Paul; Schönfinkel, Moses (December 1928)."Zum Entscheidungsproblem der mathematischen Logik".Mathematische Annalen (in German).99 (1):342–372.doi:10.1007/BF01459101.ISSN 0025-5831.S2CID 122312654.
^Ackermann, Wilhelm (1 December 1928)."Über die Erfüllbarkeit gewisser Zählausdrücke".Mathematische Annalen (in German).100 (1):638–649.doi:10.1007/BF01448869.ISSN 1432-1807.S2CID 119646624.
^Börger, Egon; Grädel, Erich; Gurevič, Jurij; Gurevich, Yuri (2001).The classical decision problem. Universitext (2. printing of the 1. ed.). Berlin: Springer.ISBN 978-3-540-42324-9.

References

[edit]

Hilbert, David;Ackermann, Wilhelm (1928).Grundzüge der theoretischen Logik [Principles of mathematical logic] (in German).Springer-Verlag.ISBN 0821820249.{{cite book}}:ISBN / Date incompatibility (help)
Alonzo Church, "An unsolvable problem ofelementary 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.
Davis, Martin (2001).Engines of logic: mathematicians and the origin of the computer. Norton paperback (1. publ. as Norton paperback ed.). New York, NY London: Norton.ISBN 978-0-393-32229-3.
Alan Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of theLondon 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.
Hodges, Andrew (1983).Alan Turing: the enigma. New York: Simon and Schuster.ISBN 978-0-671-49207-6. 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

[edit]

The dictionary definition ofentscheidungsproblem at Wiktionary

Mathematical logic

General

Theorems
(list),
paradoxes

Logics

Traditional	Classical logic Logical truth Tautology Proposition Inference Logical equivalence Consistency Equiconsistency Argument Soundness Validity Syllogism Square of opposition Venn diagram
Propositional	Boolean algebra Boolean functions Logical connectives Propositional calculus Propositional formula Truth tables Many-valued logic 3 finite ∞
Predicate	First-order list Second-order Monadic Higher-order Fixed-point Free Quantifiers Predicate Monadic predicate calculus

Set theory

Set hereditary Class (Ur-)Element Ordinal number Extensionality Forcing Relation equivalence partition Set operations: intersection union complement Cartesian product power set identities
Types ofsets	Countable Uncountable Empty Inhabited Singleton Finite Infinite Transitive Ultrafilter Recursive Fuzzy Universal Universe constructible Grothendieck Von Neumann
Maps, cardinality	Function/Map domain codomain image In/Sur/Bi-jection Schröder–Bernstein theorem Isomorphism Gödel numbering Enumeration Large cardinal inaccessible Aleph number Operation binary
Theories	Zermelo–Fraenkel axiom of choice continuum hypothesis General Kripke–Platek Morse–Kelley Naive New Foundations Tarski–Grothendieck Von Neumann–Bernays–Gödel Ackermann Constructive

Formal
systems
(list),
language,
syntax

Example
axiomatic
systems
(list)

Principia Mathematica

Proof theory

Model theory

Computability
theory

Mathematics portal

v t e Metalogic andmetamathematics
Cantor's theorem Entscheidungsproblem Church–Turing thesis Consistency Effective method Foundations of mathematics of geometry Gödel's completeness theorem Gödel's incompleteness theorems Soundness Completeness Decidability Interpretation Löwenheim–Skolem theorem Metatheorem Satisfiability Independence Type–token distinction Use–mention distinction