wHITTy | 407
problems’ covering most of mathematics as it was then known. The tenth problem, in post-
Turing language, was to write a computer program which would read in equations and write
out ‘yes’ or ‘no’ according to whether the equation had whole-number solutions.
This was an immense challenge, of course. For example, Fermat’s last theorem, that
xynnn+=z has no positive integer solutions for n ≥ 3, would be proved if we wrote
xynn++^22 +=zn+^2 as our input and received ‘no’ as output. But Hilbert was convinced that any
such challenge must yield to human ingenuity:^2
This conviction of the solvability of every mathematical problem is a powerful incentive to the
worker. We hear within us the perpetual call: There is the problem. Seek its solution. You can
find it by pure reason, for in mathematics there is no ignorabimus.
To be strictly accurate, Hilbert’s tenth problem concerns so-called ‘Diophantine equations’, in
which whole-number values are sought for variables x, y, z, etc., which are added, multiplied,
and raised to whole-number powers—algebraic expressions of this kind are called ‘polynomi-
als’. In Fermat’s equation the variable n is itself a power, so the equation is not, properly speak-
ing, Diophantine. Hilbert would not have accepted this as an extenuating circumstance. No
mathematical equation should be able to plead ignorabimus (‘we shall not know’): the problem,
solvable or not solvable, must still succumb to pure reason.
More generally, to say that a problem is ‘decidable’ is to say that it can be given to a computer
programme that will solve it. The output of the programme can just be ‘yes’ or ‘no’: we do not
have to be more demanding than this, but we need the output to arrive in a finite number of
steps. With the aid of this definition we can rephrase Hilbert: he was insisting that the problem
of solving equations with integers is decidable.
In making this definition we can rely on familiarity with the ideas of computers and com-
puter programming; in 1936 Alan Turing had to invent these ideas for himself. But the chal-
lenge of decidability had by then been set out clearly enough over a period of thirty years by
the Hilbert problem. And to solve this—that is, to supply a computational foundation for some
branch of mathematics, seemed to involve a monumental—but foreseeable—accumulation of
painstaking technical progress. However, to demonstrate that the Hilbert problem could not
be solved would require a complete innovation, a theory of what it means to compute. Turing
0000
000000000011......^11111111... ...CBAABC1111
111...
...
...11 1
1figure 37.3 Machine with input/output tape.