Darwin Among the Machines
Page 10
With wartime improvements to the Enigma and increasingly frequent rotor changes, even a growing array of far more powerful British bombes, designed with Turing’s assistance and mass-produced by the British Tabulating Machine Company, could barely keep up. By the end of 1943, ninety thousand Enigma messages a month were being decrypted, with round-the-clock shifts of cryptanalysts at Bletchley supported by satellite bombe installations at Wavendon, Gayhurst, Stanmore, and Eastcote. “The bombes were bronze-coloured cabinets about eight feet tall and seven feet wide . . . [and] made a considerable noise as the drums revolved, each row at a different speed, so there was not much talking during the eight-hour spell,” recalled Diana Payne, who set up (programmed) bombes according to the day’s cryptanalytic menus for more than three years. “For technical reasons which I never understood, the bombe would suddenly stop and we took a reading from the drums . . . it was a thrill when the winning stop came from one’s own machine.”25
Fish traffic—longer messages, transmitted automatically in binary code over high-speed cable and radiotelegraph links—presented a challenge beyond the reach of the bombes. Electronic data processing offered the only hope of catching up. A series of punched-tape machines known as Heath Robinson (code-named after an English cartoonist, in the style of Rube Goldberg, “well known for his drawings of ludicrous tasks performed by fantastic machines”)26 were built, on the principle that by simultaneous scanning of two different (and relatively prime) lengths of coded tape as continuous loops, all possible combinations of the two sequences could be compared. Based on standard teleprinter tape and standard 5-bit (Baudot) teleprinter code, but running at high speed through photoelectric heads, the Heath Robinsons used electronic circuits to count, combine, and compare the two sequences by means of Boolean operations performed at a tremendous pace. But it was difficult to maintain synchronization between two tapes. It was then proposed by Thomas H. Flowers, an engineer working for the British Post Office’s telecommunications research station at Dollis Hill, to eliminate one of the tapes by transferring its sequence to the internal memory (or state of mind, in Turing’s language) of an electronically more complicated but mechanically simpler machine. The internal sequence could then be precisely synchronized to the sequence of pulses input by the tape, which could be run without sprockets at much higher speeds by friction drive.
“The tapes were read at 5,000 characters per second,” recalled Jack Good. “There were parallel circuits, so that 25,000 binary digits were handled every second. . . . Teleprinter tapes have 10 characters to the inch, so that the speed of 5,000 characters per second implies a tape speed of nearly 30 miles per hour. I regard the fact that paper teleprinter tape could be run at this speed as one of the great secrets of World War II!”27 With practice, it was possible to run loops of tape as much as two hundred feet in length, although there were problems with the edges of the tape sawing through stainless-steel guide pins on longer runs. The new machine, constructed under the supervision of Thomas Flowers at the Dollis Hill research station and operated and programmed under the direction of M. H. A. Newman (under whose supervision Turing had written his paper on computable numbers in 1936), was code-named Colossus and incorporated fifteen hundred vacuum tubes, or, as the British more accurately described them, valves. The machine was so successful (and subspecies of Fish so prolific) that by the end of the war ten Colossi were in use, the later versions using twenty-four hundred vacuum tubes. The heaters were never turned off, since reheating was the most likely occasion for tubes to fail. “Ah, the warmth at two A.M. on a damp, cold, English winter!”28 recalled Howard Campaigne, a U.S. Navy cryptanalyst assigned to Bletchley Park in 1942. By the end of the war the Germans had begun to change the wheel patterns of both Enigma and Fish once a day instead of once a month.
The Fish were of two families: the Geheimschreiber, manufactured by Siemens, and the Schlüsselzusatz, manufactured by Lorenz. The latter was targeted by the Colossus and known as Tunny to the British, with various subspecies (Jellyfish, Bream, Gurnard, Sturgeon, etc.) representing different branches of German command. The Fish were substantial pieces of automatic teletypewriter equipment that produced a sequence of 0s and 1s (the key) that was then added to the binary representation of an unenciphered (plaintext) message and output for transmission as ordinary 5-bit teletypewriter tape. The machine’s twelve code wheels, of unequal length, were circumscribed by a combined total of 501 pins that could be shifted between two positions, giving the system a formidable number (2501 or about 10150) of possible states and a period of 1.6 × 1019 digits before the key produced by any given configuration began to repeat. The key was added modulo 2 to the plaintext message (counting by two the way we count hours by twelve, so that 0 + 1 = 1 and 1 + 1 = 0), with 1 and 0 represented by the presence or absence of a hole in the tape. Adding the key to the enciphered text a second time would return the original text. Each Fish was a species of Turing machine, and the process by which the Colossi were used to break the various species of Fish was a textbook example of the process by which the function (or partial function) of one Turing machine could be encoded as a subsidiary function of another Turing machine to produce simulated results. The problem, of course, was that the British didn’t know the constantly changing state of the Fish; they had to guess.
Colossus was programmed, in Boolean logic mode, by a plugboard and toggle switches at the back of the machine. “The flexible nature of the programming was probably proposed by Newman and perhaps also Turing, both of whom were familiar with Boolean logic, and this flexibility paid off handsomely,” recalled I. J. Good. “The mode of operation was for a cryptanalyst to sit at Colossus and issue instructions to a Wren for revised plugging, depending on what was printed on the automatic typewriter. At this stage there was a close synergy between man, woman, and machine, a synergy that was not typical during the next decade of large-scale computers.”29 Colossus did not directly reveal a plaintext message, but, when successful, a succession of clues as to the configuration and initial position of the wheels that had produced the key sequence in use at the time. The search for clues, often assisted by a “crib,” or probable string of text, relied on certain subtle statistical characteristics of the German language, a process that remained one of the more closely guarded secrets of the war. In a demonstration of the machine intelligence that would absorb Turing and several of his colleagues in the aftermath of World War II, Colossus was trained to sense the direction of extremely faint thermoclines that distinguished enciphered German from flat-random alphabetic noise. Said Andrew Hodges, “the line between the ‘mechanical’ and the ‘intelligent’ was very, very slightly blurred.”30
Colossus was not a stored-program computer (executing and modifying internally stored instructions), but it came almost as close as the U.S. Army–sponsored ENIAC, and some two years in advance. It was distinguished from other electronic calculators in that it was designed for performing Boolean operations, not producing numerical results. This counted against it by the standards of its day, but as a step toward the modern computer, these logical abilities placed it far ahead.
Turing’s role in the history of Colossus remains shrouded by the layers of secrecy that surrounded the project, further obscured by the legendary aura surrounding the universal machine. Good wrote that Turing “made important statistical contributions, but had little to do with the Colossus,”31 a view supported by Newman, Flowers, and others, although Brian Randell, after extensive interviews with these participants, noted “virtually all the people I have interviewed recollect wartime discussions of his idea of a universal automaton.”32 Peter Hilton wrote that Turing “was, in fact,—and quite consciously and deliberately—inventing the computer as he designed first the ‘Bombe’ and then the ‘Colossus.’”33 By the time of the actual construction and operation of the Colossi, Turing had moved on to the problem of real-time voice encryption, among other things. Bletchley Park had grown into an operation employing seven thousand people, ten Colossi, i
nnumerable bombes, large arrays of Hollerith equipment, and extensive telecommunications support. The Colossi were among the first programmable, if specialized, electronic digital computers. As an integrated data-processing installation the whole operation was years, if not decades, ahead of its time.
With the end of the war, the computational torch passed to the Americans, even though it was the alumni of Bletchley Park who were first to demonstrate a working stored-program computer (the Manchester Baby Mark I, which ran its first program on 21 June 1948) and first to construct a fully electronic memory (the electrostatic Williams tube). The driving force behind computer development was no longer the logical puzzle of cryptanalysis, but the numerical horsepower required to design atomic bombs. When Bletchley Park disbanded, the Official Secrets Act handicapped those who could not refer openly to their wartime work. The existence of Colossus would not be officially acknowledged for thirty-two years.
That Turing was thinking seriously about computers during the war is best evidenced by his report, produced in the final three months of 1945 for the National Physical Laboratory (NPL), entitled “Proposal for the Development in the Mathematics Division of an Automatic Computing Engine (ACE).”34 Turing’s design was commissioned by J. R. Womersly, superintendent of the Mathematics Division, who became interested in Turing machines before the war and had even suggested building one before strategic priorities intervened. At the end of the war Womersly had been sent to the United States to survey the latest (and still secret) computer developments, including the Harvard Mark I tape-controlled electronic calculator, which he described as “Turing in hardware” in a letter home.35 Womersly reported to Douglas R. Hartree, who reported to Sir Charles Darwin, Director of NPL and grandson of the Charles Darwin. But Darwin was slow to take an interest in Turing’s project, and the lumbering pace of the bureaucracy he commanded had already crippled the proposal by the time he applied his influence in an attempt to gain the project full support. Shuffled among a succession of departments, the original proposal was reconsidered to death. Turing’s automatic computing engine, like Babbage’s analytical engine, was never built.
Turing’s proposal “synthesized the concepts of a stored-program universal computer, a floating-point subroutine library, artificial intelligence, details such as a hardware bootstrap loader, and much else.”36 At a time when no such machines were in existence and the von Neumann architecture had only just been proposed, Turing produced a complete description of a million-cycle-per-second computer that foreshadowed the RISC (Reduced Instruction Set Computer) architecture that has now gained prominence after fifty years. The report was accompanied by circuit diagrams, a detailed physical and logical analysis of the internal storage system, sample programs, detailed (if bug-ridden) subroutines, and even an estimated (if unrealistic) cost of £11,200. As Sara Turing later explained, her son’s goal was “to see his logical theory of a universal machine, previously set out in his paper ‘Computable Numbers,’ take concrete form.”37
Turing’s design relied on mercury-filled acoustic delay lines for high-speed storage, a technique developed for processing radar signals by comparing a series of echoes to distinguish things that had moved and later applied to an early generation of computers, although “its programming,” as M. H. A. Newman said, “was like catching mice just as they were entering a hole in the wall.”38 A series of electrical pulses, about a microsecond apart, were converted to a train of sound waves circulating in a long tube of mercury equipped with crystal transducers at both ends. About a thousand digits could be stored in the millisecond it took a train of pulses to travel the length of a five-foot “tank.” Viewed as part of a finite-state Turing machine, the delay line represented a continuous loop of tape, a thousand squares in length and making a thousand complete passes per second under the read-write head. Turing specified some two hundred tubes, each storing thirty-two words of 32 bits, for a total, “comparable with the memory capacity of a minnow,” of about 200,000 bits.39
“The property of being digital,” announced Turing to the London Mathematical Society in a 1947 lecture on his design, “should be of more interest than that of being electronic.”40 Whether memory took the form of paper tape, vacuum-tube flip-flops, mercury pulse trains, or even papyrus scrolls did not matter as long as discrete symbols could be freely read, written, relocated, and, when so instructed, erased. The concept of random-access memory and the resulting ability to store and manipulate both instructions and data in common is considered to have been the key innovation in the development of electronic digital computers (producing twenty thousand pages of transcripts in the Honeywell-Sperry-Rand patent dispute alone). Both these developments were implicit in the concept of a one-tape Turing machine introduced in 1936. It made no difference whether binary digits (instructions, data, or temporary notes) were stored as sound waves in a vibrating column of mercury or as symbols on paper tape. But the five-channel tape readers of Colossus would have to be run at twelve hundred miles per hour to keep up with a single mercury delay-line store.
Turing’s vision for the ACE became bogged down in an institutional quagmire and failed to get off the ground. The routine miracles of war, when Cambridge theoreticians were granted unlimited engineering resources and even the post office could be counted on to deliver new hardware overnight, did not survive the peace. Turing’s decision that construction should be contracted out, as had been done for the Colossus, was in hindsight a mistake. But hindsight has shown that his design principles were sound. In May 1950 a partial prototype (the Pilot ACE) was finally built and “proved to be a far more powerful computer than we had expected,” wrote J. H. Wilkinson, even though its mercury delay lines only held three hundred words of 32 bits each. “Oddly enough much of its effectiveness sprang from what appeared to be weaknesses resulting from the economy in equipment that dictated its design.”41
In July 1947, Turing took a leave of absence from NPL, returning to his King’s College fellowship for a year. He resigned from NPL in May 1948, accepting an appointment to Manchester University, where M. H. A. Newman was germinating a mathematical computing department with talent from Bletchley Park. Turing, restless as ever, helped get machines and programs up and running at Manchester while his attention wandered to other things. Foremost was his mathematical theory of morphogenesis, which he worked at simulating digitally, writing programs longhand in machine language using his own base-32 notation (the digits reversed to match the patterns of bits as displayed by the Williams-tube store). Another focus was a series of reflections on artificial intelligence, labeled “mechanical intelligence” in language that remains more precise. Here more than ever his iconoclasm found free reign. “An unwillingness to admit the possibility that mankind can have any rivals in intellectual power,” Turing wrote in 1948, “occurs as much amongst intellectual people as amongst others: they have more to lose.”42
Turing’s thoughts about hardware and software ranged far ahead of anything in existence at the time. His approach to the question of machine intelligence was as uncluttered as his approach to computable numbers ten years before. He faced the question of incompleteness once again. A brisk trade would soon develop around the rehashing of Gödel’s proof of the incompleteness of formal systems, arguing whether this limitation constrained the abilities of computers to duplicate the intelligence and creativity of the human mind. Turing neatly summarized the essence (and weakness) of this convoluted argument in 1947, saying that “in other words then, if a machine is expected to be infallible, it cannot also be intelligent.”43 To Turing this demonstrated not a theoretical obstacle, but simply the need to develop fallible machines able to learn from their own mistakes.
“The argument from Gödel’s and other theorems rests essentially on the condition that the machine must not make mistakes,” he explained in a sabbatical report submitted to NPL in 1948. “But this is not a requirement for intelligence.”44 Turing made several concrete proposals. He suggested incorporating a random element
to create what he referred to as a “learning machine.” This proposal avoided the problem of having to specify all possible contingencies in advance by granting the computer an ability to take a wild guess and then either reinforce or discard the guess according to the consequent results. Guesses might be extended not only to external questions, but to modifications in the computer’s own instructions. A machine could then learn to teach itself. “What we want is a machine that can learn from experience,” wrote Turing. “The possibility of letting the machine alter its own instructions provides the mechanism for this.”45 In 1949, while developing the Manchester Mark I (commissioned by Ferranti Ltd. as the prototype of the first electronic digital computer to be commercially produced), Turing designed a random-number generator that instead of producing pseudorandom numbers by a numerical process, included a source of truly random electronic noise.
Carrying these ideas one step further (although pointing out that “paper interference” with a universal machine was equivalent to “screwdriver interference” with actual parts), Turing developed the concept of “unorganized Machines . . . which are largely random in their construction [and] made up from a rather large number N of similar units.”46 He considered a simple model with units capable of two possible states connected by two inputs and one output each, concluding that “machines of this character can behave in a very complicated manner when the number of units is large.” Turing showed how such unorganized machines (“about the simplest model of a nervous system”) could be made self-modifying and, with proper upbringing, could become more complicated than anything that could be otherwise engineered. The human brain must start out as such an unorganized machine, since only in this way could something so complicated be reproduced.