60 | 7 HIlBERT AND HIS fAmOUS PROBlEm
By using programs stored in memory, Turing argued, the universal machine can carry out
every possible computation (see Chapter 41).^13 Scarcely more than a decade later, on the back
of wartime technology, Turing’s invention moved out of the realm of purely theoretical con-
structs to become real hardware. As we now know, the electronic universal machine went on
to transform both science and society, but when Turing invented it he was not thinking about
electronic computers at all. Strangely enough, he was intent on proving the existence of math-
ematical realms that, in a certain sense, lie beyond the range of any computer, no matter how
powerful.
Neither Gödel nor Church had come close to inventing the universal machine.^14 Gödel’s own
greatest gift to computer science was the branch of mathematics known as recursive function
theory, and like Turing’s universal machine, this was also a product of the curiosity-driven
exploration of the deepest foundations of mathematics. Recursive function theory is essentially
the theory of computer programs, yet when Gödel pioneered it (along with Thoralf Skolem,
Stephen Kleene, and Hilbert himself ) he was not thinking about what we now call computing
at all. He was working on the proof of his incompleteness theorem, and experiencing the first
hazy glimpses of an unknown mathematical world—the strange and exciting landscape that lies
beyond the computable.
As well as recursive function theory, Gödel also contributed another fundamental idea to
computing in the same mathematical paper: published in 1931, and containing proofs of his
first and second incompleteness theorems, this paper is one of the classics of twentieth-century
mathematics.^15 Gödel’s idea was that logical and arithmetical statements can be represented
by numbers. Turing, von Neumann, and others developed this idea much further, and it is
now ubiquitous in computing, with everyone’s laptop containing binary numbers that represent
program instructions, logical and arithmetical statements, and data of all types. Gödel himself,
though, took little or no interest in the development of the electronic computer.^16 Unlike Turing
and von Neumann, he was the sort of mathematician who did not care to descend from the
mountain-tops of abstraction.
Digital super-optimism
Returning to the question of the computer’s limits: would you yourself agree with the claim that
computers can perform any and every well-defined mathematical task—if not in practice, then
at any rate in principle?
In practice, some tasks would involve such vast amounts of processing that the fastest com-
puters would take zillions of years to complete them, and the numbers involved would get so
large as to swamp any realistic amount of memory. Let’s use the term ‘digital super-optimism’
for the view that computers can in principle do anything and everything mathematical—if only
there is enough memory and processing power on tap.
Even infinite tasks can be programmed, so long as it is assumed that the computer running
the program has access to unlimited memory (as does the universal Turing machine). One
example of an easily programmed infinite task is to calculate x^2 , first for x = 1, then x = 2, then
x = 3, and so on, ever onwards through the integers. There is no end to this program’s cal-
culations. Whatever gigantic number x you might consider—a billion times the number of
nanoseconds in a billion years, for instance—the program will eventually reach that number
and calculate its square.