408 | 37 DECIDABIlITy AND THE ENTSCHEIDUNGSPROBLEM
produced this theory single-handedly at the age of 24. Although not alone in the achievement,
his version of it, profound yet eminently practical, was to bequeath to mathematics ideas and
techniques that are still being worked out today.
The Entscheidungsproblem
By the 1920s Hilbert had enlarged his vision well beyond the scope of his tenth problem, to
encompass nothing less than all of mathematical truth. Diophantine equations are a part of
arithmetic, and to say that a particular equation is solvable is to assert a theorem of arithmetic.
We should have a systematic procedure for deciding whether this assertion is valid or not—and
the same should be true of geometry or logic, or any other part of mathematics.
So, Hilbert was aiming to conquer, literally in his view, the whole of mathematics: given
any mathematical system S (such as arithmetic), he wanted to establish that, for any propo-
sition P,
Completeness: either P or not P is provable in S
Consistency: P and not P are not both provable in S
Decidability (the Entscheidungsproblem): there is a process for deciding in a finite num-
ber of steps whether P is provable in S.The grandness of Hilbert’s concept cannot be overestimated: from completeness and consist-
ency, truth and provability become synonymous; then by the Entscheidungsproblem, truth
becomes ascertainable. It is a wonderful implementation of Hilbert’s resounding ‘in mathemat-
ics there is no ignorabimus’.
Alas, as Hilbert entered the last decade of his life his programme was destroyed in every par-
ticular. In 1931 Kurt Gödel proved his incompleteness theorems.^3 The first exhibits a counter-
example to completeness in any system S that has at least the expressive power of ordinary
arithmetic; the second establishes that consistency cannot itself be provable as a theorem of S.
This leaves open the Entscheidungsproblem: we might at least hope to have a process for check-
ing which theorems are provable, even if an answer of ‘no’ fails to provide a certificate of a
theorem’s falsehood. By 1936 this hope too had been demolished—simultaneously, and on both
sides of the Atlantic, by Alonzo Church and Emil Post, working independently at Princeton,
and by Alan Turing.
Cantor and diagonalization
There is an indication in the title of Alan Turing’s 1936 paper, ‘On computable numbers with
an application to the Entscheidungsproblem’, of the extraordinary amount of inventiveness
that it contains. The refutation of the final part of Hilbert’s noble programme was almost an
afterthought, appearing as the last of eleven numbered sections. Before that there were the
creation of a model of computation and the notion of universal computation, and the demon-
stration that there are properties of numbers that are undecidable by computation, as modelled.
Transferring this undecidability to the Entscheidungsproblem is accomplished by yet another
new idea, that of reductions between computations: this idea was eventually to deny Hilbert
even the solvability of Diophantine equations.