Entscheidungsproblem

E87086

decision problem problem in computability theory problem in mathematical logic

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.

Try in SPARQL Jump to: Surface forms Disambiguation Statements Elicitation Referenced by

AI illustration

All labels observed (5)

Label	Occurrences
Entscheidungsproblem canonical	2
Hilbert’s Entscheidungsproblem	2
Church’s theorem on the undecidability of first-order logic	1
David Hilbert’s Entscheidungsproblem	1
Hilbert's Entscheidungsproblem	1

How this entity was disambiguated

This entity first appeared as the object of triple T692618 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.

NED1 Entity disambiguation (via context triple) gpt-5-mini-2025-08-07

Target entity: Entscheidungsproblem
Context triple: [On Computable Numbers, with an Application to the Entscheidungsproblem, addressesProblem, Entscheidungsproblem]

A. Hilbert’s program
Hilbert’s program was an influential early-20th-century initiative in the foundations of mathematics that sought to formalize all of mathematics and prove its consistency using finitistic methods.
B. On Computable Numbers with an Application to the Entscheidungsproblem
"On Computable Numbers, with an Application to the Entscheidungsproblem" is Alan Turing’s landmark 1936 paper that introduced the Turing machine model and founded the formal study of computability and the limits of algorithmic decision procedures.
C. Church–Turing thesis
The Church–Turing thesis is a foundational principle in computability theory stating that any function that can be effectively computed by an algorithm can be computed by a Turing machine (or equivalently by other formal models of computation).
D. Hilbert problems
The Hilbert problems are a famous list of 23 unsolved mathematical problems presented by David Hilbert in 1900 that profoundly influenced the development of 20th-century mathematics.
E. Gödel's incompleteness theorems
Gödel's incompleteness theorems are two fundamental results in mathematical logic showing that any sufficiently powerful, consistent formal system cannot prove all true statements about arithmetic, and cannot prove its own consistency.
F. None of above. chosen
G. Unsure - the case is ambiguous/there is not enough information to decide.

NED2 Entity disambiguation (via description) gpt-5-mini-2025-08-07

Target entity: Entscheidungsproblem
Target entity description: 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.

A. Hilbert’s program
Hilbert’s program was an influential early-20th-century initiative in the foundations of mathematics that sought to formalize all of mathematics and prove its consistency using finitistic methods.
B. On Computable Numbers with an Application to the Entscheidungsproblem
"On Computable Numbers, with an Application to the Entscheidungsproblem" is Alan Turing’s landmark 1936 paper that introduced the Turing machine model and founded the formal study of computability and the limits of algorithmic decision procedures.
C. Church–Turing thesis
The Church–Turing thesis is a foundational principle in computability theory stating that any function that can be effectively computed by an algorithm can be computed by a Turing machine (or equivalently by other formal models of computation).
D. Hilbert problems
The Hilbert problems are a famous list of 23 unsolved mathematical problems presented by David Hilbert in 1900 that profoundly influenced the development of 20th-century mathematics.
E. Gödel's incompleteness theorems
Gödel's incompleteness theorems are two fundamental results in mathematical logic showing that any sufficiently powerful, consistent formal system cannot prove all true statements about arithmetic, and cannot prove its own consistency.
F. None of above. chosen

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 ⓘ linked to: "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 ⓘ linked to: Turing machine 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 ⓘ

How these facts were elicited

Referenced by (7)

Full triples — surface form annotated when it differs from this entity's canonical label.

On Computable Numbers, with an Application to the Entscheidungsproblem → addressesProblem → Entscheidungsproblem ⓘ

subject linked to: On Computable Numbers with an Application to the Entscheidungsproblem

On Computable Numbers, with an Application to the Entscheidungsproblem → influencedBy → David Hilbert’s Entscheidungsproblem ⓘ

subject linked to: On Computable Numbers with an Application to the Entscheidungsproblem