466 | 42 TURING’S lEGACy
every computer science student and called the ‘halting problem’ is based on the Turing machine
concept: this is the problem of deciding, given any computer program, whether the program
terminates or runs on forever (until memory is exhausted). Christopher Strachey, who features
in Chapters 20, 21 and 23, recounted how Turing gave him a verbal proof of the unsolvability of
the halting problem in a railway carriage in 1953.^5
Many developments in modern computer science still rely on the Turing machine concept,
for example quantum computing and complexity theory.^6 The latter is a rigorous formulation
of the idea that some problems are harder to solve than others. Another illustration of the
importance of the Turing machine concept is that new and seemingly very different forms
of computation have so far always turned out to be equivalent to standard Turing-machine
computation. An example is provided by the ‘Game of Life’, explained in Chapter 41: although
the Game of Life seems very different from the Turing machine concept, it has been proved that
whatever can be computed by the Game of Life can also be computed by a Turing machine, and
vice versa.^7 The emerging field of quantum computing might be another example where this
is true—that is to say, it might be true that everything computable by a quantum computer is
computable by Turing machine and vice versa—although in this case the jury is still out.
Apart from the Turing machine, another conspicuous ‘Turing first’ in computer science was
his work in artificial intelligence (Chapter 25), including his specification of the Turing test
(Chapter 27), his anticipation of connectionism (Chapter 29), and his pioneering discussion of
what is now called ‘superintelligence’—artificial intelligence that exceeds human intelligence.
He also published (in 1949) a very early proof of what is today called ‘program correctness’.
Arguably the first ever such proof, this innovative work was rediscovered later and appreciated
as an early foray into what is now an important subfield within computer science.^8
Any book on the history of the computer would be radically incomplete without an explana-
tion of Turing’s role in its development. He is also considered an important figure in the over-
all history of science. Charles Van Doren’s encyclopaedic 1991 book A History of Knowledge,
which set out to cover the entire range of human invention and creativity, devoted a section to
Turing and the Turing machine, while The Oxford Companion to the History of Modern Science
included not only an entry for ‘Computer science’ but also a separate entry for ‘Artificial intel-
ligence’: both entries described Turing’s foundational role. In addition the Oxford Companion
(which was edited by John Heilbron) contained an entry simply on Turing himself: this noted
presciently—in 2003—that ‘Turing’s status as a cult hero will undoubtedly increase’.
figure 42.2 Entrance to the
2012 ‘Codebreaker’ exhibition
at the Science Museum, London.
Photograph by Jonathan Bowen.