COPElAND | 59
Hilbert’s Entscheidungsproblem
Gödel’s epoch-making result, however, seemed to leave open one of the most fundamental
problems of mathematics—and that is where Turing entered the picture.^5 This unresolved
problem was known as the Entscheidungsproblem, or the ‘decision problem’.
The German mathematician David Hilbert (Fig. 7.2) had brought the Entscheidungsproblem
into the spotlight.^6 Hilbert, who was 50 years Turing’s senior, set the agenda for much of
twentieth- century mathematics in a lecture that he gave in Paris at the turn of the century,
and by the 1930s he was virtually the pope of mathematics.^7 Turing—untidy, irreverent, and
scarcely older than an undergraduate—took on the Entscheidungsproblem and showed that
matters were absolutely not as Hilbert thought.
Turing summarized the Entscheidungsproblem like this:^8
Is there a ‘general mechanical process’ for telling whether any given formula is provable?
Here ‘provable’ means that the formula can be derived, step by logical step, using the rules and
principles of Hilbert’s logico-mathematical calculus—known to mathematics buffs as the engere
Functionenkalkül.^9 Hilbert thought that there must be a general procedure for telling whether
any specified formula is provable, and the challenge—a fundamentally important challenge in
his view—was to find it.
Gödel gave a dramatic and easy-to-understand explanation of what Turing established about
the Entscheidungsproblem. He described an imaginary machine—a computing machine— looking
something like a typewriter, except for having a crank-handle at the side.^10 ‘Turning the handle’
was Gödel’s metaphor for what we now call ‘executing an algorithm’. The user typed a mathemati-
cal or logico-mathematical formula at the keyboard (the formula that the user elected to type
could be either true or false), and then the user turned the crank-handle round once. On Hilbert’s
view of mathematics, this computing machine could, in principle, be designed to behave as fol-
lows: when the crank was turned, the machine would sound its bell if the typed formula was a
provable one, but if the formula was not provable then the bell would remain silent.
In a word, this machine is able to ‘decide’—in the sense of ‘figure out’ or ‘calculate’—whether
the typed formula is provable or not (hence the term ‘decision problem’). What Turing estab-
lished is very simply stated: such a machine is impossible. Once you stray beyond the most
elementary areas of mathematics (such as Boolean algebra and the ‘pure monadic’ functional
calculus), it is simply not possible to design a finite computing machine that is capable of decid-
ing whether formulae are or are not provable. Hilbert was quite wrong to think that there must
be a general mechanical process for telling whether or not any specified formula is provable.
It was in a lecture in the United States in 1939 that Gödel gave this summary, and he rounded
off his exposition with the dramatic remark that what this shows is essentially that ‘the human
mind will never be able to be replaced by a machine’.^11 Had Turing been there, he might have
objected that the issue about the mind is not quite so simple—but that’s another story.^12
Turing’s universal computing machine
It was precisely in order to prove the impossibility of this decision-machine that Turing
dreamed up his universal computing machine—his ingeniously simple digital processor with
an indefinitely extendable memory (see Chapter 6).