David Hilbert and the Entscheidungsproblem

Zusammenfassung

David Hilbert was the most influential mathematician of the late nineteenth and early twentieth centuries, a man who believed so deeply in the power of human reason that he set out to place all of mathematics on an unshakeable logical foundation. His 1928 challenge — the Entscheidungsproblem, or decision problem — asked whether a mechanical procedure could determine the truth or falsity of any mathematical statement. The answers he received, from Kurt Gödel and then from Alan Turing and Alonzo Church, shattered his dream. Yet in the wreckage of that dream, theoretical computer science was born.

The Göttingen Giant

David Hilbert was born in Königsberg, Prussia, in 1862, and died in Göttingen, Germany, in 1943. In the decades between, he reshaped mathematics so thoroughly that it is almost impossible to discuss the subject without encountering his fingerprints. Königsberg — the city of Kant, the city of the seven bridges — gave him his philosophical disposition: a conviction that rigorous thought, properly disciplined, could answer any question worth asking. He studied at the University of Königsberg, where he formed a lifelong friendship with Hermann Minkowski, and by 1895 he had been called to a professorship at Göttingen, then the world capital of mathematics. He would remain there for the rest of his life.

Hilbert’s early career was marked by startling versatility. He solved Gordan’s problem in invariant theory in 1888, a problem that Paul Gordan himself had declared impossible, using a bold non-constructive existence proof that showed an infinite family of invariants must be finitely generated without actually exhibiting the generators. Gordan’s famous complaint — “Das ist nicht Mathematik, das ist Theologie” (This is not mathematics, this is theology) — captured the controversy perfectly. Hilbert had proved something existed without building it. He did not care. He was interested in truth, not construction.

In 1897 he published the Zahlbericht, a magisterial synthesis of algebraic number theory that set the agenda for the field for a generation. In 1899 he published Grundlagen der Geometrie, in which he re-axiomatized Euclidean geometry so rigorously that, as he liked to say, one could replace the words “points, lines, and planes” with “tables, chairs, and beer mugs” and the logical structure would remain intact. Mathematics, Hilbert insisted, was about formal relationships, not physical intuitions.

The Twenty-Three Problems

On August 8, 1900, Hilbert stood before the International Congress of Mathematicians in Paris and delivered a lecture that would echo through the century. He presented twenty-three unsolved problems — some precise, some programmatic — that he believed should guide mathematical research in the new century. The list was not exhaustive; Hilbert had prepared a longer version and trimmed it for the occasion. But the twenty-three problems he chose were influential beyond anything he could have imagined. They included the Riemann hypothesis (still unsolved), the continuum hypothesis (shown to be independent of standard axioms by Paul Cohen in 1963), and the consistency of arithmetic — the question that would eventually consume him.

The deeper theme running through the Paris lecture was optimism. Hilbert believed that every well-posed mathematical problem had a definite answer, and that patient, rigorous effort would eventually find it. “We must know,” he would say in a famous 1930 radio address. “We will know.” The German phrase — “Wir müssen wissen, wir werden wissen” — became his motto, and it was engraved on his tombstone. It was a declaration of faith in human reason that was, within two years of his death, the most poignant possible epitaph.

Hilbert’s Program

By the 1920s, Hilbert had crystallized his philosophical ambitions into what became known as Hilbert’s Program: a project to place all of mathematics on a secure axiomatic foundation. The program had several components. First, mathematics should be fully formalized — every proof should be a finite sequence of symbols manipulated by explicit rules, leaving no room for intuition or ambiguity. Second, the formal system should be complete — every true statement expressible in the system should be provable within it. Third, the system should be consistent — it should be impossible to derive a contradiction. And fourth — most ambitiously — consistency should be provable by finitary methods, meaning by a restricted form of reasoning that even the most skeptical mathematician would accept.

Hilbert was not naive. He understood that foundational questions were genuinely hard. The paradoxes discovered around the turn of the century — Russell’s paradox, Burali-Forti’s paradox — had shaken the naive set theory of Georg Cantor. Hilbert’s response was to build a formal system careful enough to exclude paradoxes while preserving the richness of mathematics. He recruited talented collaborators, including Wilhelm Ackermann and Paul Bernays, and together they published Grundzüge der theoretischen Logik in 1928. This text posed the Entscheidungsproblem in its definitive form.

The Decision Problem

The Entscheidungsproblem asked: Is there an algorithm — a definite mechanical procedure — that, given any mathematical statement, can determine in a finite number of steps whether that statement is provable from the axioms of logic? Note what the problem presupposes. It assumes that “algorithm” and “mechanical procedure” are intuitively clear concepts. It assumes that completeness has been achieved or could be. And it assumes that the answer is probably yes.

Hilbert was almost certainly confident the answer was yes. An affirmative answer would have been the crowning jewel of his program: mathematics as a machine, truth as computation.

Info

The Entscheidungsproblem is distinct from the question of completeness. Completeness asks whether every truth is provable. Decidability asks whether provability itself is mechanically checkable. Even a complete system might lack a decision procedure — though Hilbert’s intuition was that these properties would come together.

Gödel’s Bombshell

The first blow against Hilbert’s Program came not from the Entscheidungsproblem but from completeness. In 1931, Kurt Gödel, a twenty-five-year-old logician from Brno, published his incompleteness theorems. The first theorem showed that any consistent formal system strong enough to express basic arithmetic must contain true statements that cannot be proven within the system. The second theorem showed that such a system cannot prove its own consistency.

Hilbert reportedly reacted with disbelief and then genuine distress. The completeness pillar of his program had collapsed. Gödel’s result did not immediately answer the Entscheidungsproblem — a system could be incomplete yet still have a decision procedure for what it could prove — but it made the overall landscape look far more treacherous. Mathematics contained irreducible mysteries. There was no master key.

Gödel’s proof was itself constructive in a precise sense: he showed how to build a specific unprovable statement by encoding the statement “this statement is not provable” in arithmetic — a mathematical version of the Liar’s paradox. The technique, known as Gödel numbering, was also a harbinger: it showed that statements about formal systems could themselves be represented as mathematical objects, a form of self-reference that would reappear in Turing’s analysis of computation.

Turing and Church Answer the Question

The Entscheidungsproblem was finally answered — negatively — in 1936, independently and by different methods, by Alan Turing in Cambridge and Alonzo Church at Princeton. Their answers required solving a prior problem: What, precisely, is an algorithm?

Church answered this question by using the lambda calculus, a formal system he had developed earlier in the decade (see Alonzo Church and Lambda Calculus). He defined “effectively computable” to mean “definable in lambda calculus,” and showed that the Entscheidungsproblem was equivalent to asking whether a certain property of lambda expressions was decidable — and it was not. His paper appeared in April 1936.

Turing’s approach, published in his landmark paper “On Computable Numbers, with an Application to the Entscheidungsproblem” (submitted May 1936, published January 1937), was more intuitive and ultimately more influential. Rather than using an existing formal system, Turing invented a new model of computation: the abstract machine that now bears his name. A Turing machine is a simple device that reads and writes symbols on an infinite tape, moving left or right according to rules. Turing showed that such machines could perform any mechanical computation, and then proved that no Turing machine could decide in general whether an arbitrary Turing machine would halt on a given input — the halting problem. Since a decision procedure for the Entscheidungsproblem would solve the halting problem, no such procedure exists.

(For the full story of Turing’s life and work, see Alan Turing and the Enigma.)

Info

Church and Turing reached the same conclusion by different routes, and Turing spent 1936–1938 studying under Church at Princeton, where they became convinced their approaches were equivalent. The Church-Turing thesis — that every effectively computable function is computable by a Turing machine — is now a foundational principle of theoretical computer science, though technically an empirical hypothesis rather than a theorem.

The Irony at the Heart of Hilbert’s Legacy

There is a deep irony in Hilbert’s legacy. He set out to show that mathematics was complete, consistent, and decidable. He received proof that it was none of these things. And yet, in the process of answering his questions, Gödel, Turing, and Church created the conceptual infrastructure of the computer age. Gödel numbering showed how symbols could encode other symbols — the basis of all programming. Turing’s machine model became the theoretical foundation of every algorithm ever studied, every program ever written. Church’s lambda calculus became the mathematical vocabulary of functional programming, still thriving in languages like Haskell, ML, and Clojure.

Hilbert asked whether truth was mechanically decidable. The answer was no — but the attempt to formalize the question demanded a rigorous theory of mechanical processes, and that theory was computing. The father of modern mathematics inadvertently fathered theoretical computer science by asking a question that turned out to be unanswerable.

Mathematical Legacy Beyond Foundations

It would be a distortion to remember Hilbert only as the man whose program was refuted. His direct mathematical contributions are immense. Hilbert spaces — the infinite-dimensional generalization of Euclidean space — are the fundamental mathematical objects of quantum mechanics; without them, modern physics would be incoherent. His work on integral equations founded functional analysis. His invariant theory results opened algebraic geometry. His axiomatization of geometry inspired the broader movement of rigorous axiomatization that transformed twentieth-century mathematics.

Of his twenty-three Paris problems, most have been solved or substantially advanced. The tenth problem — whether there is an algorithm to determine if a Diophantine equation has an integer solution — was answered negatively in 1970 by Yuri Matiyasevich, building on work by Martin Davis, Hilary Putnam, and Julia Robinson. This result, like the resolution of the Entscheidungsproblem, used the theory of computation that Turing built in response to Hilbert’s challenge.

The Last Years

Hilbert lived long enough to see Gödel’s results, but his response was complex. He continued to believe in the essential rightness of the formalist program and worked with Bernays on Grundlagen der Mathematik, attempting to salvage what could be salvaged. His mental powers declined in his late seventies. The Nazi seizure of power in 1933 devastated Göttingen: Jewish mathematicians were expelled or fled, and the great community Hilbert had built was destroyed. When the new Nazi minister of education asked Hilbert at a banquet how mathematics in Göttingen had fared since it had been freed from the Jewish influence, Hilbert reportedly replied: “Mathematics in Göttingen? There is really none any more.”

He died in Göttingen on February 14, 1943. According to contemporary accounts, only a handful of people attended his funeral; the mathematical world he had dominated for fifty years had been scattered and destroyed. His tombstone in Göttingen bears the words he had spoken on the radio in 1930: Wir müssen wissen, wir werden wissen.

He was right that we would know. He was wrong about what we would find.