Turing's Cathedral

by George Dyson

  Turing introduced two fundamental assumptions: discreteness of time and discreteness of state of mind. To a Turing machine, time exists not as a continuum, but as a sequence of changes of state. Turing assumed a finite number of possible states at any given time. “If we admitted an infinity of states of mind, some of them will be ‘arbitrarily close’ and will be confused,” he explained. “The restriction is not one which seriously affects computation, since the use of more complicated states of mind can be avoided by writing more symbols on the tape.”13

  The Turing machine thus embodies the relationship between an array of symbols in space and a sequence of events in time. All traces of intelligence were removed. The machine can do nothing more intelligent at any given moment than make a mark, erase a mark, and move the tape one square to the right or to the left. The tape is not infinite, but if more tape is needed, the supply can be counted on never to run out. Each step in the relationship between tape and Turing machine is determined by an instruction table listing all possible internal states, all possible external symbols, and, for every possible combination, what to do (write or erase a symbol, move right or left, change the internal state) in the event that combination comes up. The Turing machine follows instructions and never makes mistakes. Complicated behavior does not require complicated states of mind. By taking copious notes, the Turing machine can function with as few as two internal states. Behavioral complexity is equivalent whether embodied in complex states of mind (m-configurations) or complex symbols (or strings of simple symbols) encoded on the tape.

  It took Turing only eleven pages of “On Computable Numbers” to arrive at what became known as Turing’s Universal Machine. “It is possible to invent a single machine which can be used to compute any computable sequence,” he announced.14 The Universal Machine, when provided with a suitably encoded description of some other machine, executes this description to produce equivalent results. All Turing machines, and therefore all computable functions, can be encoded by strings of finite length. Since the number of possible machines is countable but the number of possible functions is not, noncomputable functions (and what Turing referred to as “uncomputable numbers”) must exist.

  Turing was able to construct, by a method similar to Gödel’s, functions that could be given a finite description but could not be computed by finite means. One of these was the halting function: given the number of a Turing machine and the number of an input tape, it returns either the value 0 or the value 1 depending on whether the computation will ever come to a halt. Turing called the configurations that halt “circular” and the configurations that keep going indefinitely “circle free,” and demonstrated that the unsolvability of the halting problem implies the unsolvability of a broad class of similar problems, including the Entscheidungsproblem. Contrary to Hilbert’s expectations, no mechanical procedure can be counted on to determine the provability of any given mathematical statement in a finite number of steps. This put a halt to the Hilbert program, while Hitler’s purge of German universities put a halt to Göttingen’s position as the mathematical center of the world, leaving a vacuum for Turing’s Cambridge, and von Neumann’s Princeton, to fill.

  After a full year of work, Turing gave Newman a draft of his paper in April of 1936. “Max’s first sight of Alan’s masterpiece must have been a breathtaking experience, and from this day forth Alan became one of Max’s principle protégés,” says William Newman, Max’s son. Max Newman lobbied for the publication of “On Computable Numbers, with an Application to the Entscheidungsproblem,” in the Proceedings of the London Mathematical Society, and arranged for Turing to go to Princeton to work with Alonzo Church. “This makes it all the more important that he should come into contact as soon as possible with the leading workers on this line, so that he should not develop into a confirmed solitary,” Newman wrote to Church.15

  Turing arrived in Princeton carrying his sextant, and stretching his resources to survive on his King’s College fellowship (of £300) for the year. The page proofs of “On Computable Numbers” arrived by mail from London on October 3. “It should not be long now before the paper comes out,” he wrote to his mother on October 6. The publication of “On Computable Numbers” (on November 30, 1936) went largely unnoticed. “I was disappointed by its reception here,” Turing wrote to his mother in February 1937, adding that “I don’t much care about the idea of spending a long summer in this country.”16 Only two requests for reprints came in. Engineers avoided Turing’s paper because it appeared entirely theoretical, and theoreticians avoided it because of the references to paper tape and machines.

  “I remember reading Turing’s paper in the Trinity College library in 1942,” says Freeman Dyson, “and thinking ‘what a brilliant piece of mathematical work!’ But I never imagined anyone putting these results to practical use.” A twenty-four-year-old graduate student was an unlikely source for a technological revolution, and mathematical logic the unlikeliest of fields. “When I was a student, even the topologists regarded mathematical logicians as living in outer space,” commented Martin Davis in 1986. “Today, one can walk into a shop and ask for a ‘logic probe.’ ”17 Turing’s Universal Machine has held up for seventy-six years.

  In March of 1937, Alonzo Church reviewed “On Computable Numbers” in the Journal of Symbolic Logic, and coined the term Turing machine. “Computability by a Turing machine,” wrote Church, “has the advantage of making the identification with effectiveness in the ordinary (not explicitly defined) sense evident immediately.”18 Church’s thesis—equating computability with effective calculability—would be the Church-Turing thesis from then on.

  Even Gödel, who dismissed most attempts to strengthen his own results, recognized the Church-Turing thesis as a major advance. “With this concept one has for the first time succeeded in giving an absolute definition … not depending on the formalism chosen,” he admitted in 1946. Before Church and Turing, the definition of mechanical procedure was limited by the language in which the concept was defined. “For the concept of computability however … the situation is different,” Gödel observed. “By a kind of miracle it is not necessary to distinguish orders, and the diagonal procedure does not lead outside the defined notion.”19

  “It is difficult today to realize how bold an innovation it was to introduce talk about paper tapes and patterns punched in them, into discussions of the foundations of mathematics,” Max Newman recalled in 1955. For Turing, the next challenge was to introduce mathematical logic into the foundations of machines. “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.”20

  The title “On Computable Numbers” (rather than “On Computable Functions”) signaled a fundamental shift. Before Turing, things were done to numbers. After Turing, numbers began doing things. By showing that a machine could be encoded as a number, and a number decoded as a machine, “On Computable Numbers” led to numbers (now called “software”) that were “computable” in a way that was entirely new.

  Although Turing was at the university and von Neumann was at the Institute, both groups of mathematicians shared offices in Fine Hall. “Turing’s office was right near von Neumann’s, and von Neumann was very interested in that kind of thing,” says Herman Goldstine. “He knew all about Turing’s work, and … understood the significance … when the time came. The whole relation of the serial computer, tape and all that sort of thing, I think was very clear—that was Turing.” Julian Bigelow agrees. “It was no coincidence that the stored program computer came to fruition about ten years after … Post and Turing set the framework for this kind of thinking,” he confirms. Von Neumann “knew Gödel’s work, Post’s work, Church’s work very, very well.… So that’s how he knew that with these tools, and a fast method of doing it, you’ve got the universal tool.”21

  “I never heard of Turing until I came down here [to Princeton],” Bigelow explains.

  But a
fter having been here for a month, I was talking with von Neumann about various kinds of inductive processes and evolutionary processes, and just as an aside he said, “Of course that’s what Turing was talking about.” And I said, “Who’s Turing?” And he said, “Go look up Proceedings of the London Mathematical Society, 1937.” The fact that there is a universal machine to imitate all other machines … was understood by von Neumann and a few other people. And when he understood it, then he knew what we could do.22

  In 1937, both Turing and von Neumann were still working on pure mathematics, although Turing found the temptation of the Palmer Physical Laboratory, connected by a passageway to the mathematics department at Fine Hall, impossible to resist. “Turing actually designed an electric multiplier and built the first three or four stages to see if it could be made to work,” related Malcolm MacPhail, who lent Turing a key to the machine shop. “He needed relay-operated switches which, not being commercially available at that time, he built himself … and so, he machined and wound the relays and to our surprise and delight the calculator worked.”23

  Having pushed the boundaries of mathematical logic as far as he could with his Universal Machine, Turing began wondering about ways to escape the limitations of closed formal systems and purely deterministic machines. His PhD thesis, completed in May of 1938 and published as “Systems of Logic Based on Ordinals” in 1939, attempted to transcend Gödelian incompleteness by means of a succession of formal systems, incrementally more complete. “Gödel shows that every system of logic is in a certain sense incomplete, but at the same time … indicates means whereby from a system L of logic a more complete system L′ may be obtained,” Turing explained.24 Why not include L′? And then, since L′ is included, L″? Turing then invoked a new class of machines that proceed deterministically, step by step, but once in a while make nondeterministic leaps, by consulting “a kind of oracle as it were.”

  “We shall not go any further into the nature of this oracle apart from saying that it cannot be a machine,” Turing explained (or did not explain). “With the help of the oracle we could form a new kind of machine (call them O-machines).”25 Turing showed that undecidable statements, resistant to the assistance of an external oracle, could still be constructed, and the Entscheidungsproblem would remain unsolved. The Universal Turing Machine of 1936 gets all the attention, but Turing’s O-machines of 1939 may be closer to the way intelligence (real and artificial) works: logical sequences are followed for a certain number of steps, with intuition bridging the intervening gaps.

  “Mathematical reasoning may be regarded rather schematically as the exercise of a combination of two faculties, which we may call intuition and ingenuity,” Turing explained. “Intuition consists in making spontaneous judgments which are not the result of conscious trains of reasoning. These judgments are often but by no means invariably correct (leaving aside the question what is meant by ‘correct’).”26 Turing saw the role of ingenuity as “aiding the intuition,” not replacing it. “In pre-Gödel times it was thought by some that it would probably be possible to carry this programme to such a point that all the intuitive judgments of mathematics could be replaced by a finite number of these rules,” he concluded. “The necessity for intuition would then be entirely eliminated.” What if intuition could be replaced by ingenuity, and ingenuity, in turn, by brute force search? “We are always able to obtain from the rules of a formal logic a method of enumerating the propositions proved by its means. We then imagine that all proofs take the form of a search through this enumeration for the theorem for which a proof is desired. In this way ingenuity is replaced by patience.”27 No amount of patience, however, was enough. Ingenuity and intuition were here to stay.

  The relations between patience, ingenuity, and intuition led Turing to begin thinking about cryptography, where a little ingenuity in encoding a message can resist a large amount of ingenuity if the message is intercepted along the way. A Turing machine can be instructed to conceal meaningful statements in what appears to be meaningless noise—unless you know the key. A Turing machine can also be instructed to search for meaningful statements, but since there will always be uncountably more meaningless statements than meaningful ones, concealment would appear to win. “I have just discovered a possible application of the kind of thing I am working on at present,” Turing wrote to his mother in October 1936. “It answers the question ‘What is the most general kind of code or cipher possible,’ and at the same time (rather naturally) enables one to construct a lot of particular and interesting codes. One of them is pretty well impossible to decode without the key and very quick to encode. I expect I could sell them to H.M. [Her Majesty’s] Government for quite a substantial sum, but am rather doubtful about the morality of such things. What do you think?”28

  With his PhD completed, Turing began to prepare for his return to England. Von Neumann offered him a position as his assistant at the Institute, at $1,500 for the year, but war clouds were gathering and Turing was ready to return home. “Will be seeing you in middle of July,” he wrote to his friend and King’s College mathematical colleague Philip Hall. “I also expect to find the back lawn criss-crossed with 8ft trenches.”29 He arrived back at Southampton on July 19, 1938.

  Cryptography and cryptanalysis soon became as critical as physics to the course of World War II. At the close of World War I, a cryptographic machine had been invented by the German electrical engineer Arthur Scherbius, who proposed it to the German navy, an offer that was declined. Scherbius then founded the Chiffriermaschinen Aktiengesellschaft to manufacture the machine, under the brand name Enigma, for enciphering commercial communications, such as transfers between banks. The German navy changed its mind and adopted a modified version of the Enigma machine in 1926, followed by the German army in 1928, and the German air force in 1935.

  The Enigma contained a stack of flat wheel-shaped rotors with 26 electrical contacts, one for each letter of the alphabet, arranged in a circle on each face. The contacts were connected so that a signal entering one side of the rotor as a given letter emerged on the other side as something else. There were thus 26! (or 403,​291,​461,​126,​605,​635,​584,​000,​000) possible wirings for each rotor. Each station in a particular banking or communication network had an assortment of different rotors in matching sets. Messages were entered on a keyboard that sent an electric current through the stack of 3 adjacent rotors to a 4th, reflecting rotor (capable of only 7,905,853,580,025 states) before returning through the first 3 rotors in reverse, ending at one of 26 light bulbs, indicating the letter to be used for the enciphered text. The rotors were mechanically coupled to the keyboard like the wheels of an odometer, so that the machine’s state of mind changed with every step. If the recipient had an identical machine, with the exact same rotors placed in the same starting positions, the function could be executed in reverse, producing deciphered text.

  In September of 1939, Turing joined the Foreign Office’s Government Code and Cypher School, sequestered at a Buckinghamshire estate known as Bletchley Park. Their mission was to break the Enigma codes, now modified by the German military authorities, who had introduced new rotor configurations and were frequently changing the keys. For top-secret communications, especially with the U-boat fleet, an additional rotor position was added as well as an auxiliary plugboard that further scrambled ten pairs of letters, leaving only six letters unchanged. “Thus, the number of possible initial states of the machine at the beginning of the message was about 9 × 1020. For the U-boats it was about 1023,” recalled I. J. (Jack) Good, who signed on as Turing’s statistical assistant, at the age of twenty-five, in May 1941.30

  For the three-rotor Enigma a brute-force trial-and-error approach would have to test about a thousand states per second to run through all possible configurations in the three billion years since life appeared on Earth. A brute-force approach to the four-rotor Enigma would have to test about two hundred thousand states per second to be assured of a solution in the fifteen billion years
since the known universe began. Bletchley Park eventually succeeded in deciphering a significant fraction of intercepted Enigma traffic within a few days or sometimes hours before the intelligence grew stale. This success was a product of intuition and ingenuity on the part of the British aided by human error on the other side.

  “When the war started probably only two people thought that the Naval Enigma could be broken,” explained Hugh Alexander, in an internal history written at the end of the war. “Birch [Alexander’s boss] thought it could be broken because it had to be broken and Turing thought it could be broken because it would be so interesting to break it.” According to Alexander, Turing explained his interest as follows: “No one else was doing anything about it and I could have it to myself.”31 Breaking the naval Enigma to reveal the locations of the U-boats that were crippling the British supply lines was critical to keeping England afloat.

  Polish cryptographers had provided a head start by decoding three-rotor Enigma messages before the outbreak of the war. Three young Polish mathematicians (Henryk Zygalski, Jerzy Rózycki, and Marian Rejewski), assisted by French intelligence and with an interest in the German Enigma dating back to an interception by Polish customs officers in 1928, narrowed the search for rotor configurations so that electromechanical devices (called “bombas” by the Poles and “bombes” by the British) could apply trial and error to certain subsets that remained. The bombe incremented itself through a space of possibilities and, if it arrived at a possible rotor configuration, came to a halt. The characteristic ticking, followed by silence, may have given the machine its name. Later versions, designed with Turing’s assistance and mass-produced by the British Tabulating Machine Company, emulated thirty-six Enigma machines at a time. The bombes were a concrete implementation of Turing’s idea of a single machine able to imitate the behavior of a multitude of other machines.