The machine is now scanning the blank just to the left of the last 1, and has shifted into state D. It moves two squares to the left, then, remaining in state D, erases the x per its instructions, and moves one square to the right, where it scans a 0. Now it shifts into state C, moves two squares to the right, scans a 1, moves two further squares to the right, scans a blank, prints a 1, moves one square to the left, and shifts again into state D:
The machine, now in D, encounters a succession of blanks, which compel it to move ten squares to the left, where it encounters an . Its instruction upon encountering this symbol is to move one square to the right and shift into state E. The instructions for state E now require it to move, in total, twelve squares to the right, at which point it once again encounters a blank square. The machine now prints a 0, moves two spaces to the left, and reverts to state B.
Its next instruction, in state B, is to move one square to the right, print an x, and then move three squares to the left. This operation is repeated twice, producing two x’s.
A series of further moves adds a 1, erases the x’s, and adds another 1. The process repeats until we have:
We have now generated the beginning of the infinite sequence for which this particular machine is designed; we have 0010110111 . . . , written in alternate squares. As Turing notes, “the convention of writing the figures only on alternate squares is very useful: I shall always make use of it. I shall call the one sequence of alternate squares F-square and the other sequence E-squares. The symbols on the E-squares will be liable to erasure. The symbols on the F-squares form a continuous sequence.” The E-squares provide the scratch paper on which the machine works out the basic operations that underlie the algorithm it is performing.
Read in unary notation, the sequence generated by Turing’s second machine is simply the sequence of the natural numbers, with each number separated from the ones before and after it by a 0. The equation for which this machine provides an algorithm would thus be written
y = x + 1
with the machine endlessly putting in values for x and generating values for y.
Read in binary notation, on the other hand, we get the following sequence (with each number, again, separated by a 0 from the ones before and after):
1, 3, 7, 15, 31, 63, 127, . . .
These numbers—each of which is written in binary notation as a sequence of 1’s (1, 11, 111, 1111, 11111, 111111, etc.)—have in common that each is one less than a power of 2. The equation for which this Turing machine provides the algorithm can thus be written
y = 2x – 1
with the machine, once again, calculating successive values of y.
It is worth noting that in both of Turing’s examples, what the machine generates is not a computable number but a computable sequence. Most glosses on the Turing machine give examples such as the one with which I began, of machines that apply an algorithm to a particular set of values (in this case 2 and 2), find a solution (in this case 4), and then stop. Turing’s machines, by contrast, go on forever, each one printing an infinite sequence of integers. Both types fit Stephen Kleene’s definition of an algorithm as “a finitely described procedure, sufficient to guide us to the answer to any one of infinitely many questions, by finitely many steps in the case of each question.” The first type, however, gives only one of the infinitely many answers, while the second gives all of them. Thus in the case of Turing’s second example, each of the answers that the machine generates—1, 3, 7, 15, etc.—fits the definition of a computable number, while the numbers taken together fit the definition of an infinite computable sequence. Changing the configurations of the machine so that it answers for a specific n and then stops is a simple matter, and makes no substantive difference to Turing’s thesis.
Comparatively speaking, both of these Turing machines are elementary. Indeed, one of Turing’s principal points is that for every algorithmic procedure, no matter how complex, there exists a Turing machine the specific table of behavior for which will effect that algorithm. Each of these Turing machines would be defined by its table of behavior, the complexity of which would depend on the complexity of the algorithm in question. For certain algorithms, the table of behavior might require dozens of m-configurations and symbols. In his paper Turing sketches proofs for the algorithmic computability by Turing machines of values for π, e, all real algebraic numbers, and the real zeros of the Bessel functions.*
To simplify the process, Turing creates, in his paper, a sort of shorthand for writing out tables of behavior. He begins with the table for the first of his two machines, the one that prints out the sequence 0101010101:
Turing now proposes giving numbers to the m-configurations, calling them q1, q2, q3, q4, . . . q9. In addition, numbers are given to the symbols, which will be called S1, S2, S3, S4, . . . S9. In particular, S0 will signify a blank, S1will signify a 0, and S2 will signify a 1. The table can now be rewritten as follows:
Note that in this notation, “move right” is written as P S0, R, meaning “print blank, then move right.” A similar notation would take care of any E’s (erasures).
The P’s can now be removed, and the entire sequence rewritten on a single line:
q1 S0 S1R q2; q2 S0 S0 R q3; q3 S0 S2 R q4; q4 S0 S0 R q1;
Turing next assigns to each symbol a letter according to the following scheme: qi will be replaced by the letter D followed by i repetitions of the letter A, while Sj will be replaced by the letter D followed by j repetitions of the letter C. Right and left continue to be written as R and L, while “no move” is written as N. According to this system, q1 S0S1R q2 would thus be expressed as DADDCRDAA, with DA replacing q1, D replacing S0, DC replacing S1, and DAA replacing q2. The sequence now reads
DADDCRDAA; DAADDRDAAA; DAAADCCRDAAAA; DAAAADDRDA;
Turing calls this the standard description, or S.D., of the machine. Yet he has one more transformation in mind. By assigning a numeral to each letter—1 for A, 2 for C, 3 for D, 4 for L, 5 for R, 6 for N, and 7 for ;—he is able to represent this standard description as a sequence of numerals.* The integer represented by these numerals he calls the description number, or D.N., of the machine. For the machine we have been discussing, the description number would be:
31332531173113353111731113322531111731111335317
This is obviously a very long number. Yet it is microscopic compared with the description numbers of more complex Turing machines. To make matters more difficult, this number would under ordinary circumstances be written in some version of binary notation, rendering it simpler for a machine to read but more arduous for a human being. None of which matters. Like the human computer whom it replaces, the Turing machine is in no hurry. On the contrary, because it lives in a hypothetical universe, untouched by human concerns such as speed or efficiency, it has all the time in the world.
3.
Turing has now introduced and explained the idea of the a-machine and presented a system for encoding its instruction tables. He has also established that for every algorithmic procedure, an a-machine must, by definition, exist. And just as the sequence 001011011101111 . . . can be generated by the table we have given, “any computable sequence is capable of being described in terms of such a table.” More importantly, “to each computable sequence there corresponds at least one description number, while to no description number does there correspond more than one computable sequence.” Just as the computable sequences define the machines that generate them, each Turing machine defines a computable sequence. The uniqueness of the description numbers would even allow us to list them, as it were, alphabetically, starting at 0 and continuing on to infinity. On such a list, the machine for which we have just calculated, the description number would be in 31332531173113353111731113322531111731111335317th place.
Does every machine, however, generate a valid computable sequence? The answer is no. Some machines, as Roger Penrose puts it, are “duds.” An example of a dud machine proposed by Martin Davis would be one for which the instruction table
reads roughly as follows:
This machine would shuttle endlessly back and forth between 0 and 1; it would neither print a coherent sequence nor come to a stop. Such a machine Turing calls circular. On the other hand, a circle-free machine is one that is capable of generating a computable sequence. Apparently anticipating some head-scratching over the difference between a computable number and a computable sequence, Turing adds, “We shall avoid confusion by speaking more often of computable sequences than of computable numbers.”
All the machines we have looked at, with the exception of the last, are circle-free machines. The first of these—the machine designed to add two numbers together—is fed with an input and then stops when it reaches its answer; the two machines that Turing gives as examples generate computable sequences. It would not, however, be difficult to design a variant on the machine that generates the sequence 001011011101111 . . . . Remember that this machine simply gives successive (and infinite) answers to the equation y = 2x – 1 as the natural numbers from 1 onward are fed into it. The variant machine would be designed to plug one natural number at a time into the equation, halting when it gives each answer. Thus if one were to feed x = 3 into the machine, it would go through a process that would conclude with its generating the desired answer—7—and halt. But could one design a Turing machine that would analyze any other Turing machine and decide whether that machine was circular or circle-free? This question—known as the halting problem—lies at the heart of Turing’s paper and leads directly into his analysis of the Entscheidungsproblem.
Turing’s consideration of the halting problem brings him to what is unquestionably his most startling and original leap. By way of proposing a method for investigating how one might determine whether a given Turing machine is circular or circle-free, he puts forward the idea of a “universal machine”: a Turing machine that is capable of imitating the behavior of any other Turing machine, no matter what algorithm that machine is designed to perform. It is this hypothetical “universal machine” that really constitutes the prototype of the modern computer.
The section of Turing’s paper that describes his universal machine begins with characteristic modesty. “It is possible,” he writes, “to invent a single machine which can be used to compute any computable sequence. If this machine U is supplied with a tape on the beginning of which is written the S.D. of some computing machine M, then U will compute the same sequence as M.” Remember that “S.D.” stands for “standard description”—the sequence of letters into which the table of behavior for any given Turing machine can be translated, and which can in turn be translated into the integer (binary or denary) that is the machine’s “description number.”
By way of explaining the behavior of U, Turing begins by positing a third machine, M′, “which will write down on the F-squares of the tape the successive complete configurations of M.” Remember that earlier Turing defined a machine’s “complete configuration” at any stage in its progress as comprising “the motion of the machine, the number of the scanned square, the complete sequence of all symbols on the tape, and the m-configuration.” As an example of M, he recalls the second machine mentioned in the paper, the one that generates the sequence 001011011101111 . . . . Just as the table of behavior for this machine can be translated, with letters, into its standard description, so the sequence of moves that the machine goes through as it follows the rules prescribed by its table of behavior can be rewritten using letters. Once again, each m-configuration is written as D followed by the appropriate number of A’s, while each symbol is written as D followed by the appropriate number of C’s. As before, 0 is written as DC, 1 as DCC, and a blank as D. The symbol is written as DCCC, and though Turing does not mention the x, one can assume that it would be written as DCCCC.
Using this scheme, M′ can print out the sequences of F-square symbols generated by M:
DA : DCCCDCCCDAADCDDC : DCCCDCCCDAAADCDDC : . . .
Turing’s shorthand, here, requires a bit of unpacking. The first DA signifies that the machine begins in m-configuration A, which tells it to print the sequence 00 and then shift into m-configuration B. The second sequence of letters describes the action taken as a result of this instruction, and amounts to an abbreviation of
B 0 blank 0
This is, of course, the sequence written on the F-squares at the point when the machine moves into m-configuration C, with the m-configuration that has generated this sequence (B) inserted between the two ’s and the actual figures that have been printed in the F-squares: two 0’s and a blank. A colon separates this description from the next, which abbreviates
C 0 blank 0
This is the machine’s state as it shifts into its next complete configuration. No new figures have been generated because, as we recall, m-configuration B, upon encountering a 0, does nothing; it simply tells the machine to shift into m-configuration C. In letters, this sequence reads
DCCCDCCCDAAADCDDC
The next complete configuration, following the implementation of m-configuration C upon encountering a 0, describes the machine having shifted two spaces to the right but remaining in C. This would look like
C 0 blank 0 blank blank
which would translate into
DCCCDCCCDAAADCDDCDDCDD
Now the machine, still in m-configuration C, finds itself at a blank square, at which point it is instructed to print a 1, shift one square to the left, and enter into m-configuration D:
D 0 blank 0 blank 1
Or:
DCCCDCCCDAAAADCDDCDDCC
Once again, colons separate descriptions of the complete configurations of the machine at each move that it makes.
A : B 0 blank 0 : C 0 blank 0 : C 0 blank 0 blank
blank:
D 0 blank 0 blank 1
Or:
DA : DCCCDCCCDAADCDDC : DCCCDCCCDAAADCDDC : DCCCDCCCDAAADCDDCDD: DCCCDCCCDAAAADCDDCDDCC
“It is not difficult to see,” Turing concludes,
that if M can be constructed, so can M′.The manner of operation of M′ could be made to depend on having the rules of operation (i.e., the S.D.) of M written somewhere within itself (i.e. within M′); each step could be carried out by referring to these rules. We have only to regard the rules as being capable of being taken out and exchanged for others and we have something very akin to the universal machine.
Turing here describes—again, with little fanfare—a prototype of the modern computer, in which the rules are stored “somewhere within” the machine, the software within the hardware, but can be “taken out and exchanged for others.” It is a moment of insight made all the more extraordinary by its author’s apparent failure to apprehend its implications.
Just one thing is lacking: “at present the machine M′ prints no figures.” It prints only representations (in the form of letters) of the figures that M would print. Turing corrects this omission by arranging for M′ to print “between each successive pair of complete configurations the figures which appear in the new configuration but not in the old.” The sequence thus becomes
DA: 0: 0: DCCCDCCCDAADCDDC : DCCCDCCCDAAADCDDC : . . .
Leaving out the two ’s, which, we recall, function only to indicate the initiation of the sequence, the only figures printed as a result of m-configuration B are a pair of 0’s. At first it may seem slightly odd that these figures should be printed before the instruction that generates them—and yet we must remember that the machine we are dealing with is not M, but M′, and that the function of M′ is not to generate the sequence but to describe the behavior of M as it generates the sequence. No figures appear between the second and the third descriptions because the third—DCCCDCCCDAADCDDC—does not, in fact, result in the generation of any more 0’s or 1’s. On the other hand, if we were to continue the sequence, we would soon see a 1:
DA : 0 : 0 : DCCCDCCCDAADCDDC : DCCCDCCCDAAADCDDC : DCCCDCCCDAAADCDDCDD : 1 : DCCCDCCCDAAAADCDDCDDCC : . . .
Our machine M′ is now, in effect, operating as a universal machine, bec
ause in addition to the complete configurations of M, it is printing the computable sequence that M was designed to generate. With typical nonchalance, Turing concludes, “It is not altogether obvious that the E-squares leave enough room for the necessary ‘rough work,’ but this is, in fact, the case.” Finally, he notes that “the sequences of letters between the colons . . . may be used as standard descriptions of the complete configurations. When the letters are replaced by figures . . . we shall have a numerical description of the complete configuration, which may be called its description number.” For instance, the standard description of the complete configuration DCCCDCCCDAAAADCDDCDDCC would translate into the description number 3222322231111323323322.
4.
Turing’s next step is to set up the table of behavior for a universal machine, called U. At this point the symbolic language he employs—a combination of uppercase and lowercase German (Gothic) letters and lowercase Greek letters—becomes immensely confusing; indeed, to borrow a phrase from Roger Penrose, Turing’s system of skeleton tables “would be rather more complicated to explain than the machine is complicated itself.” I shall try in the following pages to offer a more reader-friendly précis of his ideas.
We recall that in order to employ the universal machine, U, we have to feed into it the description number of a specific Turing machine, T. The m-configurations listed on the table of behavior for U will now lead the machine through a series of maneuvers by means of which it is able to deduce from T’s description number the algorithmic process that T follows. U can then obtain the same result as T. Thus if T is the Turing machine that generates the sequence 0101010 . . . , and we want U to mimic T, we first feed into U the description number for T:
The Man Who Knew Too Much: Alan Turing and the Invention of the Computer (Great Discoveries) Page 7