Entscheidungsproblem

The Entscheidungsproblem ('decision problem') was David Hilbert's 1928 challenge to find a mechanical procedure that could determine, for any statement of first-order logic, whether it is a theorem. It was the third pillar of the Hilbert Program — alongside consistency and completeness — and represented Hilbert's epistemological optimism that every well-posed mathematical question has a definite, mechanically discoverable answer.

The problem was proved unsolvable independently by Alan Turing and Alonzo Church in 1936. To refute it, Turing had to specify precisely what 'mechanical procedure' meant — and the Turing machine, invented for this purpose, became the foundation of computability theory. The Entscheidungsproblem's solution was its own impossibility proof, and that proof created computer science.