The History of AI

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

Threads that pass through here

Sources

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.

Open in the interactive timeline