The Entscheidungsproblem
Era 1 · The foundations (1763–1942) › Logic and the foundations of mathematics
- Lineage
- Symbols and logic
- Kind
- Theory
Who
University of Göttingen
What happened
David Hilbert and Wilhelm Ackermann publish Grundzüge der theoretischen Logik, the first textbook of first-order logic, which states the decision problem clearly.
Why it mattered
It poses the Entscheidungsproblem: is there a mechanical procedure that can decide whether any given formula is valid? Answering it forces a definition of what a mechanical procedure is.
The full story
In 1928 David Hilbert and a former student, Wilhelm Ackermann, published Grundzüge der theoretischen Logik with Springer, a 120-page textbook. It is the first elementary text to present clearly what is now called first-order logic, and its way of writing it became the standard one.
The book leaves two questions open. The first is whether that logic is complete, that is, whether every formula true under every interpretation can be proved from its axioms and rules. Kurt Gödel answered yes in 1929. The second is the Entscheidungsproblem, the "decision problem": to find a procedure that, given any formula, says in a finite number of steps whether or not it is universally valid.
The idea had old roots. In the seventeenth century Leibniz had imagined a machine that would manipulate symbols to decide whether a statement was true, and Hilbert turned that into a precise mathematical problem. In Hilbert's Göttingen group, Heinrich Behmann had already given it this name in a 1921 lecture. For some fragments of logic such a procedure exists, but no one could find one for logic as a whole.
Answering that it does not exist meant first defining what a mechanical procedure is. That is what Alonzo Church did with the lambda calculus and Alan Turing with Turing machines, independently, in 1936. Both answers were negative, and the theory of computation was born from that effort to define calculation.
Common misconceptions
What people often say: The decision problem asked whether every mathematical question has an answer.
In fact: It asked for a mechanical procedure that, given any formula of first-order logic, would say in a finite number of steps whether it is universally valid.
Builds on
Hilbert's 23 problems (August 8, 1900)
Inherited, with no proven direct link
The tenth problem asks for a decision procedure for one class of equations; the decision problem asks for one for all of logic, and the impossibility of the first implies that of the second
Leads to
The lambda calculus and an unsolvable problem (April 1936), On Computable Numbers (November 30, 1936)
Documented direct influence
Both papers answer the Entscheidungsproblem; Turing's names it in its title
The McCulloch-Pitts neuron (December 1943)
Documented direct influence
Hilbert and Ackermann's textbook is one of the three works the paper lists in its references
Threads that pass through here
- From Hilbert's question to the universal machine (step 3 of 7)
Sources
Scholarship and context
- Review of Grundzüge der theoretischen Logik, by D. Hilbert and W. Ackermann (The Mathematical Gazette) (opens in a new tab)
- Heinrich Behmann's 1921 Lecture on the Decision Problem and the Algebra of Logic (The Bulletin of Symbolic Logic, vol. 21, no. 2, pp. 164-187) (opens in a new tab). Paolo Mancosu and Richard Zach, 2015
How to cite
“The Entscheidungsproblem.” The History of AI, revised November 13, 2026. https://thehistoryofai.com/en/milestone/entscheidungsproblem
This entry was last reviewed on November 13, 2026.