Entscheidungsproblem
E87086
The Entscheidungsproblem is a foundational decision problem in mathematical logic that asks whether there exists a general algorithm to determine the truth or falsity of any given first-order logical statement.
Aliases (3)
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
decision problem
→
problem in computability theory → problem in mathematical logic → |
| appliesTo |
arbitrary first-order sentences
→
|
| asksFor |
effective procedure to determine truth or falsity of any first-order formula
→
general algorithm for deciding validity of first-order logic statements → |
| concerns |
algorithmic decidability
→
decision procedures → first-order logic → formal languages → logical validity → satisfiability in first-order logic → |
| excludes |
restriction to specific decidable theories
→
|
| field |
computability theory
→
mathematical logic → model theory → proof theory → recursion theory → theoretical computer science → |
| formulatedIn |
1928
→
|
| formulatedInWork |
Grundzüge der theoretischen Logik
→
|
| historicalContext |
Hilbert’s program
→
|
| impact |
development of recursive function theory
→
emergence of theoretical computer science → formalization of the notion of algorithm → foundation of computability theory → |
| implies |
limits of mechanical reasoning
→
no algorithm decides validity for all first-order formulas → |
| introducedBy |
David Hilbert
→
Wilhelm Ackermann → |
| language |
German
→
|
| negativeAnswerGivenBy |
Alan Turing
→
Alonzo Church → |
| negativeAnswerYear |
1936
→
|
| provedUndecidableUsing |
Turing machines
→
lambda calculus → reduction from the halting problem → |
| relatedTo |
Church–Turing thesis
→
Hilbert’s tenth problem → completeness theorem → first-order theory validity problem → halting problem → incompleteness theorems → |
| solvedBy |
Alan Turing
→
Alonzo Church → |
| status |
undecidable
→
unsolvable → |
| translation |
decision problem
→
|
Referenced by (4)
| Subject (surface form when different) | Predicate |
|---|---|
|
On Computable Numbers, with an Application to the Entscheidungsproblem
→
|
addressesProblem |
|
On Computable Numbers, with an Application to the Entscheidungsproblem
("David Hilbert’s Entscheidungsproblem")
→
|
influencedBy |
|
Alonzo Church
("Church’s theorem on the undecidability of first-order logic")
→
|
notableWork |
|
Church–Turing thesis
("Hilbert’s Entscheidungsproblem")
→
|
relatedTo |