406 | 37 DECIDABIlITy AND THE ENTSCHEIDUNGSPROBLEM
0
110 101 011 01 10 01 (= 27353)0(^0) A A
A
B
B
B
C
C
C p q
1
1
1
0
0
00
0
0
1
11
11
11
1
figure 37.2 Machine to table to^1
(binary) number.
The details of our picture are not especially important. As it happens, it is a machine for
deciding which whole numbers, written in binary form, are multiples of 3. It works thus: sup-
pose the number is 105, whose binary representation is 1101001, because (1 × 2^6 ) + (1 × 2^5 ) + (0
× 2^4 ) + (1 × 2^3 ) + (0 × 2^2 ) + (0 × 2^1 ) + (1 × 2^0 ) = 64 + 32 + 8 + 1 = 105. We start at the node labelled
A and use the binary digits to drive us from node to node. The first couple of 1s take us to node
B and back to A again. The third digit, 0, loops us around at A. Now a 1 and a 0 take us across to
node C; and the final 0 and 1 take us back via B to A once more. Now, if we finish at A we have a
multiple of 3, otherwise we do not. You can try some more examples for yourself: 9 in binary is
1001 and that works; 19 is 10011 which leaves us at node B, so that works too, and so on.
Suppose you allowed me 90 seconds for my Turing pitch! Now I would draw a more elaborate
picture (Fig. 37.2). The table tells me how to connect the nodes with arrows (1 for an arrow, 0
for no arrow) and what labels to put on the arrows (columns p and q). This table is completely
described by writing down all the entries (the labels A, B, C, p, and q are immaterial) as a string
of zeros and ones. And my machine itself has become a binary number! Just because we can,
we can run the machine on itself: we finish up at node C, so 27,353 is not a multiple of 3. (You
probably know the ‘divides-by-3’ trick anyway, but my machine, if a bit slow, is impressively
minimalist.)
Allow me a 2-minute pitch in total and I will add this run-on-itself feature to my drawing
(Fig. 37.3). The machine has a ‘tape’ from which it reads the binary input, from left to right, just
as you would do yourself if you wrote down a number and experimented with the machine.
But my final extra 30 seconds has bought me another much more crucial enhancement. The
machine now outputs on the tape as well: at the bottom of the diagram it has rubbed out the
input digits and written, in their place, a two-digit binary number. This number is 00 if the
machine stops at node A, 01 if it stops at node B, and 10 if it stops at node C. In fact, the machine
is computing: it has computed, in binary, the remainder when 27,353 is divided by 3.
The machine as it now operates, reading and writing on the tape, incorporates the original
three-node diagram (Fig. 37.1) in tabular form, but it has extra columns to tell it to move left as
well as right on its tape and to write as well as read, as appropriate.
So, in a 2-minute picture, this is how Alan Turing invented computer science: with a machine
that reads and writes binary digits on a linear tape. The machine itself can be represented by a
binary number and can then be applied to itself: this seems like a curiosity, but it is very much
more than that, as we shall see. But first, some historical background.
Hilbert’s doomed programme
The back-story to Turing’s work is this (see also Chapter 7). In 1900 David Hilbert, whose
mathematical endeavours were, among his contemporaries, unequalled in breadth and depth,
addressed the International Congress of Mathematicians in Paris with a list of ‘millennium