wHITTy | 409
There are two technical themes that Turing, already by his early 20s an accomplished and
widely read mathematician, was able to deploy in his paper. One is the concept of ‘enumerabil-
ity’, or ‘countability’: that an infinite collection of things may be listed systematically by aligning
its members with the positive integers (that is, by ‘counting’ them). The other is the reduction
of mathematical ideas to the symbolic manipulation of strings of letters, familiar in the 1930s
from certain problems in group theory and topology.
Before delivering his coup de grâce to the Entscheidungsproblem, Turing flexed his muscles
with an application of enumerability which, as Copeland in his guide to the paper observed,^4
the Hilbert camp appear to have overlooked. This is that completeness implies decidability
because we can enumerate all proofs of all propositions: those that are one letter long (if any such
exist), those that are two letters long, and so on. Eventually, in a finite number of steps, for any
proposition P, either P or not P must appear as a proved proposition.
The idea of enumerability dates back to the late 19th century—notably, to the work of Georg
Cantor, championed by Hilbert for putting the infinite on a secure mathematical footing. In
1874 he proved the following result, now known as Cantor’s theorem:
We cannot enumerate all infinite 0–1 sequences.
This is profound, but is demonstrated by what might seem to be a sleight of hand called
‘diagonalization’ that Cantor first used in 1891, and Turing was to redeploy forty-five years
later. Suppose that we can enumerate all infinite 0–1 sequences. Align them with the positive
integers: s 1 , s 2 , s 3 , .. . . Define a diagonal sequence S by making its ith entry the opposite of the
ith entry of si; for example, if s 4 = 0011001 ... with fourth entry ‘1’, then S must have fourth
entry ‘0’. Now S differs from every one of our enumerated sequences in at least one entry, and
has therefore escaped the enumeration, whose existence is thereby disproved by contradiction.
It is time to return to our opening portrayal of Turing’s work: a machine which is both
described by, and operates on, finite binary sequences. Such machines are enumerable (Cantor’s
diagonalization does not apply to collections of finite sequences). But Turing was able to use
exactly the same self-referencing trick as appears in Cantor’s proof and apply it to an enumer-
ation of machines. This had far-reaching consequences.
Turing’s machine
We used the remainder-on-division-by-3 machine to represent Turing’s model of human com-
putation. It has all the features of Turing’s general model: it can be represented by a binary
sequence and it reads and writes backwards and forwards on a tape. This tape is required to be
endless, so that a machine can go on working forever, perhaps producing an infinite amount
of output. Crucially, the machine’s binary representation can be written on its own input tape,
whereby the machine is applied to itself.
Turing’s idea of a machine which has a machine on its input tape is a game-changer, for two
reasons. First, one might conceive of an ingenious machine which, finding another machine on
its input tape, responds by carrying out exactly the steps which the input machine is designed to
carry out, no matter what machine this is. The ingenious machine is accordingly called ‘univer-
sal’: it is the blueprint of a modern, stored-program computer. Turing devised such a machine.
Second, putting the ingenious machine on to its own input tape produces self-referential
computation, and this, as we shall see, demolishes the Entscheidungsproblem.