46 | 5 A CENTURy Of TURING
I probably simulated my first explicit Turing machine only in 1991. To me, Turing machines
were built a little bit too much like engineering systems, rather than things that were likely to
correspond to systems in nature. But I soon found that even simple Turing machines, just like
simple cellular automata, could produce immensely complex behaviour.
In a sense, Alan Turing could easily have discovered this, but his intuition—like my original
intuition—may have told him that no such phenomenon was possible. So it would probably
only have been luck—and access to easy computation—that would have led him to find it.
Had he done so, I am quite sure that he would have become curious about what the threshold
for his concept of universality would be, and how simple a Turing machine would suffice. In
the mid-1990s I searched the space of simple Turing machines and found the smallest possible
candidate, and after I put up a $25,000 prize a British college student named Alex Smith showed
in 2007 that indeed this Turing machine is universal (Fig. 5.2). No doubt Alan Turing would
very quickly have grasped the significance of such results for thinking about both mathematics
and natural processes. But without the empirical discoveries, his thinking did not progress in
this direction. Instead, he began to consider from a more engineering point of view to what
extent computers should be able to emulate brains, and he invented ideas like the ‘Turing test
(see Chapters 25 and 27)’. Reading through his writings today, I find it remarkable how many
of his conceptual arguments about artificial intelligence still need to be made—though some,
like his discussions of extrasensory perception, have become quaintly dated (see Chapter 32).
Looking at Turing’s famous 1950 article ‘Computing machinery and intelligence’,^3 one sees
a discussion of programming into a machine the contents of Encyclopaedia Britannica—which
he estimated as occupying sixty workers for fifty years. I wonder what he would think of
Wolfram|Alpha which, thanks to progress over the past sixty years, and perhaps some clever-
ness, has so far taken at least slightly less human effort.
figure 5.2 A Turing machine that is known to be the simplest possible universal Turing machine. I first identified it
in the mid-1990s, and its universality was proved in connection with a prize that I sponsored in 2007. The machine
has two states of the scanner (up or down) and three symbols (represented by colours or shades). The left-hand
diagram shows twenty steps of evolution, while the compressed form on the right corresponds to a total of
129,520 steps.