The Man Who Knew Too Much: Alan Turing and the Invention of the Computer (Great Discoveries)

by David Leavitt

  31332531173113353111731113322531111731111335317

  U, in turn, acts upon that number according to the instructions specified by its own table of behavior, with the result that it generates the same sequence as T: 0101010 . . .

  It is important to recognize here that within Turing’s morass of German and Greek alphabets there lies a precise and detailed account of exactly how U functions: the sequence of m-configurations that it follows on its path to becoming, for a time at least, T. Moreover, there is no limit whatsoever to what U is capable of. Indeed, as Stephen Kleene notes, in subsequent years mathematicians have

  convinced themselves that all possible algorithms for computing number-theoretic functions can be embodied in Turing machines (Turing’s thesis). The ingredients that are basically necessary were all provided by Turing: a fixed finite number of symbols, a fixed (perhaps very large) number of states, actions determined by the condition of one scanned square and the state in accordance with the constitution of the particular machine (i.e., its table), unlimited space (on the tape) for receiving the questions and reporting the answers and temporarily storing scratchwork, and of time (the moments) for completing the calculations.

  In order to operate as a Turing machine, all that the universal machine requires is its description number. This means that in order to operate U, one would in principle need to draw up a list of the description numbers of all Turing machines so that these could be fed into U when required. (This list, of course, would include the description number for U itself—a description number as singular as any other. Using a coding somewhat different from Turing’s, Roger Penrose provides the description number for U. It is 1,653 digits long and takes up an entire page of his book.) Some of these machines would be, by Turing’s definition, circular, in that they would never produce computable numbers or computable sequences. But others would be circle-free. Turing defines the “number which is a description number of a circle-free machine” as a “satisfactory number.” By analogy, the number that is the description number of a circular machine would be defined as an unsatisfactory number.

  Now Turing is able to begin his attack on the Entschei-dungsproblem. The question he asks is this: does there exist an algorithm (and hence a Turing machine) that can act upon the description number of another Turing machine in order to decide whether that number is satisfactory? In theory, such a machine (let’s call it D) would be able to analyze the description number of a given Turing machine M and then draw a conclusion as to its viability. If it turned out that M was circular, D would end its computations by printing a 1. If it turned out that M was circle-free, D would conclude by printing a 0. Machine D, if it existed, would in some cases amount to a positive solution to the Entscheidungsproblem, in that its verdict on the circularity or noncircularity of some specific Turing machine would provide a judgment as to the decidability of the statement to which that Turing machine corresponded. For instance, a mathematician trying to determine the truth or falsity of Goldbach’s conjecture would simply have to feed into it the description number of the machine designed to break even numbers down into primes, stopping only when it found one that did not split. If the machine printed a 1, he would know that Goldbach’s conjecture was true. More generally, machine D could be used to test out all logical statements—even those that don’t fit into the “try all numbers” model mentioned above—since by definition a proof is a series of axiom invocations and deductions based on rules of inference, and hence a mechanically checkable process. A proof must also consist of a finite numbers of sentences (or strings) each employing symbols from a finite symbolic alphabet. This means that, in theory, machine D could be fed with every possible combination of every possible symbol in the alphabet. It would take an extremely long time, but as we have noted, in Turing’s world, time is not of the essence. D would simply check the possible strings, one by one, weeding out those that were nonsense and verifying those that were valid proofs.

  But could such a machine exist? Turing addresses this question by taking the classic approach of reductio ad absurdum. That is to say, he begins with an assumption: let’s say that D does, in fact, exist. We set D to work on the first Turing machine (M0) in our list of all Turing machines, asking it to tell us whether, when fed with the whole number m, M0 generates a computable sequence. In that case, D will print a 0. Otherwise D will print a 1. We then do the same with M1, M2, M3, . . . and on to Mn, noting along the way which machines print 0 and which print 1. The machines that print 0 are the “good” machines, the ones that are circle-free.

  Next we draw up a list of the computable sequences generated by the circle-free machines, from the first to the last. For each of these machines we write out the computable sequence that it generates as different whole numbers, starting with 0, are fed into it. This will obviously be a very long list; what is important is that it is exactly the sort of list that lends itself to a method invented by Georg Cantor during his investigations into infinity. This is known as the diagonal method.

  Here’s how Turing used it. Let us imagine that a chunk from somewhere in the middle of the list looks like this:

  Bear in mind that this is a completely arbitrary list of actual computable sequences. The arrangement is also arbitrary, because it will have no bearing on what we are about to do.

  We now generate a new sequence by cutting a diagonal swath through the diagram; that is to say, by taking the first number from the first sequence, the second number from the second sequence, etc.:

  The new sequence we have generated is

  We now add 1 to each of the numbers in this sequence. Our new sequence is then

  Because the diagonal method is just the sort of algorithmic process for which one could design a Turing machine, this is obviously a computable sequence. Yet the list from which it was derived includes all the sequences that can be computed by circle-free Turing machines according to machine D—that is, all computable sequences—and that list cannot include our new sequence, because our sequence differs from the first sequence on the list in its first square, from the second in its second, etc. A contradiction has appeared. Therefore, there can be no machine D.

  As Turing writes, this proof, “although perfectly sound, has the disadvantage that it may leave the reader with the feeling that ‘there must be something wrong.’” After all, the number generated through the diagonal method can be described; then why can it not be computed? This is an important question, and one that he will address shortly. First, however, he offers an alternative proof that D cannot exist—one that has not the disadvantage of leaving the reader feeling as if she has fallen into a hole, and that also “gives a certain insight into the significance of the idea ‘circle-free.’”

  This alternate proof employs the universal machine. Let us imagine that we can somehow link the deciding machine, D, to the universal machine, U, thus creating a new hybrid machine, DU. Into this machine we feed the description number of arbitrary Turing machine M. DU now runs D, which determines whether M is circular or circle-free. If M is circular, the process stops, since there would be no point in feeding the description number of a circular machine into U, which would then replicate its circularity and run on forever. If, however, M turns out to be circle-free, U can be used to simulate its algorithmic action. Because DU includes this “checking” mechanism, by means of which it can make sure that U is fed only the description numbers of circle-free machines, DU itself is circle-free; that is to say, under no circumstance will it lapse into circularity.

  Now we feed DU’s description number into DU itself. D quickly establishes that DU’s description number is, as Turing has shown, satisfactory—that is, that DU is circle-free. It therefore passes the description number onto U, which simulates the action of DU, feeding the description number of DU into D, which then passes it on to U, which then simulates the action of DU . . . and on and on. In other words, DU, when fed with its own description number, runs on forever. DU is circular. But we have just shown that
DU is circle-free. And since it is impossible that DU be both, Turing writes, “we conclude that there can be no machine D.” Decidability is impossible. We are back in the land of paradox, with Epimenides declaring that he is a liar and Bertrand Russell upsetting Frege’s applecart.

  5.

  Turing’s next maneuver in his journey toward a solution of the Entscheidungsproblem foreshadows a strategy he later employed in his work on artificial intelligence. He shows that if we can answer a simple question—does there exist a machine E which, when fed with the description number of arbitrary Turing machine M, will establish whether M ever prints a given symbol?—then we can also answer a more complex one: is there a machine that can establish whether a given logical formula is or is not provable? This step is necessary if Turing is to make his proof airtight, meeting the demands of mathematical rigor.

  He begins, once again, by making a reductio ad absurdum assumption. Let’s say that machine E exists, and that we want to use it to find out whether M ever prints a 0. We feed into E the description number of M, and it replies by telling us that M either does or does not print a 0 at some point during its action. To use Turing’s own example, if the sequence that M prints out is

  A B A 0 1 A A B 0 0 1 0 A B . . .

  then E will tell us that, yes, M does sometimes print 0’s.

  Next we construct a variant on M—M1—which prints the same sequence as M but replaces the first 0 with another symbol; let’s say a %. Thus where M prints the sequence

  A B A 0 1 A A B 0 0 1 0 A B . . .

  M1 prints the sequence

  A B A % 1 A A B 0 0 1 0 A B . . .

  Likewise we construct a machine, M2, that replaces the first two 0’s in the sequence printed by M with %’s:

  A B A % 1 A A B % 0 1 0 A B . . .

  And on to M3, M4 . . . Mn . . .

  We now construct another machine—H—which, when fed with the standard description of M, generates successively the standard descriptions of M, M1, M2, . . . Mn. (In a parenthesis Turing assures us that such a machine exists.) Combining H with our original “Is there a 0?” machine, E, we obtain a new machine, HE. When fed with the description number of M, HE first goes into its H mode and writes down M′s standard description. Shifting into E mode, HE then determines, from that standard description, whether M will ever print a 0. If the answer is that M never prints a 0, HE prints :0:. HE then goes through the same procedure for M1, M2, . . . Mn, in each case printing :0: if the machine is shown never to print a 0. The thing to remember is that HE will print :0: only in cases where M never prints any zeros (i.e., 1111111 . . .) or where M prints a finite number of 0’s (e.g., 00011111111 . . .), in which case at some point in the iteration of M1, M2, . . . Mn, we will get a sequence along the lines of %%%1111111. . . . If, on the other hand, M does print an infinite number of 0’s, HE will not print :0:.

  The final step is reminiscent of Turing’s earlier proof that machine D cannot exist: we feed into our hypothetical machine E the description number of HE itself. Remember that the function of E is to determine whether a given arbitrary Turing machine ever prints a given symbol, in this case 0. If HE itself is shown never to print a 0, then M must print 0 infinitely often. But if HE sometimes prints a 0, then M must print no 0’s or a finite number of 0’s. A similar process would allow us to determine whether M prints a finite or an infinite number of 1’s. Because every computable number must contain an infinite number of 0’s or an infinite number of 1’s (or possibly both), Turing can now conclude, “By a combination of these processes we have a process for determining whether M prints an infinity of figures, i.e. we have a process for determining whether M is circle-free.” Turing has already shown, however, that there can be no such process. Therefore machine E cannot exist.

  It is now that Turing is able, at last, to establish the insolubility of the Entscheidungsproblem. Already he has demonstrated a method for expressing the action of a given Turing machine numerically. Now he explains how to represent that action in the form of a logical formula, which he calls Un (M). To the untrained eye, the symbolic language that he uses here appears, at the very least, daunting, yet the leap it represents is intuitively simple to grasp. He begins by showing how to describe simple aspects of M using logical statements and then coding those statements as logical formulae. For example, the statement “In the complete configuration x (of M) the symbol on the square y is S” would be coded as a logical formula that he calls Rs1(x,y). Likewise the statement “In the complete configuration x the square y is to be scanned” will be coded as I (x,y), the statement “In the complete configuration x the m-configuration is qm” will be coded as kqm, and the statement “y is the immediate successor of x” will be coded as F(x,y). Using these subformulae, Turing can now write out the logical formula Un (M) and then show that Un (M) “has the interpretation ‘in some complete configuration of M, S1 (i.e., 0) appears on the tape.” It follows that “if there is a general method for determining whether Un (M) is provable, then there is a general method for determining whether M ever prints a 0.” Earlier Turing explained that in his usage, the expression “There is a general process for determining . . .” is equivalent to the expression “There is a machine which will determine . . .” We can therefore conclude that if there exists a machine to solve the Entscheidungsproblem, then there must also be a machine E. Indeed, this may be why Turing labeled this particular machine with the letter E in the first place. Since we know, however, that machine E cannot exist, we can conclude that the Entscheidungsproblem solver cannot exist either. Therefore, the Entscheidungsproblem cannot be solved. Using logic—and a miraculous machine—Turing has brought an end to the old ideal of a serene and traversable mathematical landscape.

  * * *

  *In symbolic logic, first-order logic (also called the first-order predicate calculus) consists of quantified statements that begin with the so-called existential and universal quantifiers (∃ . . .) (∀ . . .). The first of these translates into “There exists an object such that . . .” The second translates into “For all objects, it is the case that . . .”

  *Hilbert posed a version of a decision problem, however, as problem 10 from his famous 1900 lecture, the text of which is included in Jeremy J. Gray’s The Hilbert Challenge.

  *However, as Prabhakar Ragde points out, “a decision procedure might not be efficient (that is, it could require millions of years on a fast computer . . .), and it almost certainly would not be illuminating.”

  *I follow Martin Davis’s lead in referring to the computer as “she,” since, as Davis points out, at that period most “computers” were, in fact, women.

  † This passage is quoted by Robin Gandy in his fascinating essay “The Confluence of Ideas in 1936.” Here Gandy also mentions two little-known inventors who made proposals for universal calculating machines after Babbage: P. E. Ludgate in 1909 and L. Torres y Quevedo in 1914. Others referred to Babbage in works on building more practical machines, but in each of these cases “the emphasis is on programming a fixed iterable sequence of arithmetical operations. The fundamental importance of conditional iteration and conditional transfer for a general theory of calculating machines is not recognized. . . .”

  *In the obituary for Turing in the Times of London, however, Newman wrote, “The description that he then gave of a ‘universal’ computing machine was entirely theoretical in purpose, but Turing’s strong interest in all kinds of practical experiment made him even then interested in the possibility of actually constructing a machine on these lines.”

  *This example is based on one given by Andrew Hodges in the biography.

  *I have altered slightly the symbols that Turing originally used.

  *Turing computes π as . He computes e, an irrational number that plays an important role in, among other things, the calculation of natural logarithms, as As we have seen earlier, algebraic numbers are those irrational numbers that satisfy algebraic equations. The Bessel functions are the solutions to the Bessel differential equat
ion:

  *Turing’s thesis, however, in no way depends upon the use of this particular coding system, and in fact other coding systems are far more economical. Nor is his coding system limited to these particular letters and numbers. For instance, one might assign the letter P (and the number 8) to the symbol –, indicating a negative number. One might also assign the letter Q (and the number 9) to the symbol /, indicating the dividing line between the numerator and the denominator of a fraction.

  4

  God Is Slick

  1.

  Turing now had his result. He had provided a definition for a whole new category of numbers, the “computable numbers,” and along the way proved the insolubility of the Entscheidungsproblem. More importantly, he had introduced into the discourse of mathematics a startling and original concept: the a-machine. “It is difficult to-day,” Newman wrote in his memoir, “to realize how bold an innovation it was to introduce talk about paper tapes and patterns punched into them, into discussions of the foundations of mathematics. . . .” It was just as bold an innovation to talk about “states of mind” in a mathematics paper; as Hodges observes, the supplementary “instruction note” argument was in many ways a “safer” approach. Yet the problem of how human beings think had been on Turing’s mind at least since 1931, when he wrote an essay entitled “Nature of Spirit” for Christopher Morcom’s mother. The essay begins with a general account of the influence of developments in physics and quantum mechanics on the scientific conception of the universe, then moves quickly into the question of free will:

  We have a will which is able to determine the action of the atoms probably in a small portion of the brain, or possibly all over it. The rest of the body acts so as to amplify this. There is now the question which must be answered as to how the action of the other atoms of the universe are regulated. Probably by the same law and simply by the remote effects of spirit but since they have no amplifying apparatus they seem to be regulated by pure chance. The apparent non-predestination of physics is almost a combination of chances.