Computing with Quantum Cats

by John Gribbin

  The coding for Tunny involved a machine superficially like an Enigma machine, but much more complex. For a start, a Tunny machine contained twelve wheels, each of which could rotate to a different number of positions: 43 for the first wheel, then 47, 51, 53, 59, 37, 61, 41, 31, 29, 26 and 23. This odd-looking pattern was carefully chosen so that the numbers were “relatively prime,” which means that no more than one of them can be divided by any number except 1. So 26, for example, can be divided by 13 and 2, but none of the other numbers can be divided by either 13 or 2. This was a way to avoid certain statistical patterns emerging as the wheels rotated at different rates. When the operator pressed the lever for a letter, all the wheels in the machine worked together to produce another letter, called the key, which was then added to the original letter to produce the encrypted letter of the message. The wheels then moved on in a certain way before encrypting the next letter.

  This process of adding letters to one another is easy in binary language, where o + o = o, x + x = o, x + o = x, and o + x = x. So adding xxoxo and oxxox would give you xoxxx. And in a neat twist, adding the same key again restores the original message! So provided the Tunny machine at the other end had the same wheel settings, it would subtract out the key (by adding it again) to leave the message. In a useful but not essential refinement, Tunny did all this automatically, letter by letter as the operator typed or as a paper tape ran through the machine. But the system did have a weakness: in the first version of Tunny the operator had to transmit a string of twelve letters to tell his opposite number the initial wheel settings for the message that followed.

  Since the British had never seen a Tunny machine and did not know what went on inside it, this should not have mattered. But in August 1941 they intercepted two Tunny transmissions each preceded by the same code, HQIBPEXEZMUG, and followed by a message just under four thousand characters long. In an astonishing lapse, an operator had sent the same message twice, using the same wheel settings, which meant with the same key. Just as adding the key twice leaves the original message intact, so adding the encrypted message to itself leaves the key intact. By adding the two messages together and doing some further manipulation they were left with a key 3,976 characters long, which contained information about the encrypting process going on inside the machine. In one of the most impressive achievements of the entire Bletchley Park effort, Bill Tutte, a mathematician from Cambridge, was able, with assistance from his colleagues, to work out the entire structure and operation of the Tunny machine by analyzing the statistical patterns in this key. When the Tunny system changed in October 1942 so that the wheel settings were no longer being broadcast clear but were based on predetermined arrangements unknown to the codebreakers, at least the Bletchley people knew what they were confronted with.

  Tunny should still have been unbreakable, but like Enigma it was made vulnerable by the carelessness of its operators and the bureaucratic nature of their system. The greatest gifts to the codebreakers were messages repeated without the wheel settings being changed; these were known as “depths.” Making full use of such carelessness, the codebreaking depended on using techniques developed by Tutte to obtain some of the key wheel settings. This involved very straightforward but tedious calculations.

  It was Turing who developed the methods by which the messages could actually be read, once the workings of the machine were understood. These produced good results until the Germans tightened their security, but became significantly harder to apply as time passed and mistakes such as depths became rarer. The technique still worked, but the problem was that these methods were intensely labor intensive and slow. To paraphrase Turing, it was getting to the point where it would require “100 Britons working eight hours a day on desk calculators 100 years to discover the secret factor.” By the end of 1942, it was appreciated that the only way to tackle the problem was with a machine. This approach was suggested by Max Newman, Turing's former teacher in Cambridge, who had been recruited to Bletchley Park a few months earlier, and was now put in charge of the project.

  The prototype machine that began operating in June 1943 came to be known as Heath Robinson, because of its bizarrely complex appearance—after a cartoonist of the time who specialized in intricate drawings of complex fantasy machines to do simple things like boiling an egg. Bletchley's Heath Robinson could read two long loops of paper tape at once, using photoelectric detectors and light passing through the holes in the tape. One tape contained an encoded message to be broken, the other a “code” containing all the possible settings of one group of wheels in the Tunny machine known as chi-wheels. The machine compared the possible settings of chi with the message, one by one, using electronic counters to record the number of hits, until it found a match. Once the chi-wheels were broken, the cryptographers could tackle the message by hand, using cribs, dragging and so on.

  Heath Robinson worked after a fashion, but it was slow (limited by the speed with which paper tape could be read), prone to breakdowns when the tape stretched (making it impossible to keep the two tapes in synchrony) or broke, and not entirely reliable (sometimes it would give different results if set the same problem twice). But it proved that the machine approach to breaking Tunny could work. What was needed was a better machine, and by great good fortune the man Bletchley Park asked to build a better machine was exactly the right man for the job.

  Among those who had worked on the construction of Heath Robinson were engineers at the Post Office research station in Dollis Hill in north London, who knew all about relays from their work on automatic telephone exchanges. The top engineer at Dollis Hill was Thomas Flowers (known as “Tommy” at the time, although he preferred “Tom” in later life). Born in London's East End in 1905, Flowers was the son of a bricklayer, and a genuine Cockney. He had won a scholarship to a technical college, and then joined the Post Office as a trainee telephone engineer, continuing his studies at evening classes and earning a post at Dollis Hill in 1930. There, he pioneered the use of electronic valves for switching in the 1930s, flying in the face of the received wisdom that such valves were unreliable and prone to break down. He had found that the problems arose when valves were repeatedly turned on and off, but that if they were left on all the time, glowing like little incandescent light bulbs, they would run reliably for a very long time without burning out. As early as 1934, he had worked on an experimental telephone switching system using four thousand valves, and a design based on his work had just started to come into operation at the beginning of the war. Flowers himself, though, very nearly spent the war interned in Germany. He was working in Berlin in the late summer of 1939, but fortunately was warned by the British Embassy to go home, and crossed the border into Holland a few hours before the frontier was closed.

  Flowers was asked to help with Heath Robinson because Turing had discussed with him the possibility of building an electronic version of the Bombe; although this never happened, Turing was impressed by the engineer and recommended him to Newman as the right man to fix the problems with Heath Robinson. But when he was asked for his advice on how to make the relays in Heath Robinson more reliable, Flowers’ reply was that the best thing to do would be to forget about mechanical relays altogether, and use valves instead.

  The idea of a reliable machine using a couple thousand electronic valves was regarded as a fantasy by Newman and his colleagues, who doubted that even if it could be built it would be working in time to contribute to the war effort (this was in February 1943). Flowers was told that he was welcome to try once he was back at Dollis Hill, and in the meantime, rather than officially encouraging the project, Newman ordered another dozen Heath Robinson type machines. But the Director of the Dollis Hill research station, W. G. Radley, saw the potential of the idea (and had first-hand knowledge of Flowers’ success with valve-based machines) and gave his full support to the enterprise (moral support, that is: funds were limited, and Flowers had to pay for some of the equipment himself). The result was a prototype machine, dubbed Colossus, wh
ich used 1,600 valves and required only one paper tape, carrying the message to be broken, as the “chi-stream” to be tested—all the possible settings of the chi-wheels—was generated electronically. After a heroic round-the-clock effort by Flowers and his colleagues, Colossus was tested at Dollis Hill in December 1943, then disassembled and taken on trucks to Bletchley Park, where it arrived on January 18, 1944. Re-assembled, it filled a whole room. The Bletchley Park codebreakers, including Newman, were astonished: “I don't think they [had] really understood what I was saying in detail—I am sure they didn't—because when the first machine was constructed and working, they obviously were taken aback. They just couldn't believe it!…I don't think they understood very clearly what I was proposing until they actually had the machine.”12

  The re-assembled Colossus broke its first message on 5 February 1944. It was ten times faster than Heath Robinson, and, equally important, more reliable. Orders for more Robinsons were canceled, and Flowers was asked how quickly Dollis Hill could produce more “Colossi.”

  One of the Wrens13 who worked on Colossus, Betty Houghton (née Bowden), now lives in a neighboring village to us. She was fourteen when the war broke out, and three years later joined the WRNS. She was told that there were two kinds of jobs available—cook/steward or “P5.” Having no wish to be a cook/steward, she asked what P5 was. “That's secret,” she was told, and promptly volunteered. She ended up as a Watch Leader in Hut 8 at Bletchley Park, working on Tunny, and recalls Turing as “a very nice man, very quiet; a bit daft, like most of them.”

  Colossus was the first electronic computer. It was also programmable, in a limited sense, because Flowers had deliberately designed it so that it could be adapted to new requirements by switches, and by plugging cables linking the logic units in different arrangements. The crucial difference from a modern computer, though, is that it did not store programs in its memory, the way Turing had envisaged; the programming had to be done literally “by hand” at the switches and plugboards. Even so, this adaptability proved an enormous asset, and Colossi could be adapted to use new codebreaking methods as they were invented, carrying out tasks that its designer could not have imagined.

  Flowers was asked to have an improved Colossus up and running at Bletchley by June 1, 1944. He was not told why, but the urgency was stressed. The tight deadline was met by having the machine, containing 2,400 valves and running 125 times faster than electromechanical machines, assembled and tested on site. It began operating on June 1, as requested; although Flowers did not know it at the time, this was intended to be D-Day, the date of the invasion of German-occupied France. Bad weather delayed the invasion, and as it continued there were serious doubts about whether the Allies would be able to ship enough men and matériel across the rough English Channel to support the invasion against a counter-attack. But on June 5 Colossus II was instrumental in breaking a message which revealed that Hitler had completely fallen for the Allied deception plan (Operation Fortitude), which led him to believe that the invasion would strike at the Pas de Calais, with a diversionary raid in Normandy. In the intercepted Tunny signal, he ordered Rommel to hold his forces in the Pas de Calais area to repel the “real” invasion, due five days after the expected Normandy landing. It was this piece of information, combined with a forecast of slightly improving weather, that clinched Eisenhower's decision to go ahead on June 6, knowing that even in bad weather five days would give his forces time to build up the beachhead.

  By the end of the war in 1945 eight more Colossi had been installed at Bletchley Park, and Eisenhower himself later said that without the work of the codebreakers the war would have lasted at least two years longer than it did. The two men who did more than anyone else to make all this possible were Turing and Flowers. They should each have been knighted at the end of hostilities, and given every support to develop their ideas further. But that isn't the way it happened.

  ANTICLIMAX: AFTER BLETCHLEY

  Harry Fenson, a member of Flowers’ team, has said that he was well aware at the time that Colossus was “a data processor rather than a mere calculator, and rich in logical facilities.” It had the potential to manipulate many kinds of data, “such as text, pictures, movement, or anything which could be given a value.” It contained “all the elements to make a general-purpose device”—a Turing machine.14

  At the end of the war, Bletchley Park could (and I would say, should) have become a scientific research center, equipped with ten Colossi and a world lead in computing. Instead, on the direct orders of Winston Churchill (who did many questionable things to set alongside his greater moments), all but two of the machines were physically broken up and most of their components smashed. This was part of a successful attempt to hide the success of the codebreaking work which had substantially shortened the war, so that the British could carry on reading the coded traffic of other nations without being suspected. The “other nations” included the Soviet Union, which used captured German Tunny machines long after the war. In April 1946, the codebreaking headquarters moved to Eastcote, a London suburb, and changed its name to the Government Communications Headquarters (GCHQ); GCHQ moved on to Cheltenham, its present home, in 1952. In both these moves, it took with it the two remaining Colossi (“Colossus Blue” and “Colossus Red”); the work they did is still classified. One was dismantled in 1959, the other in 1960. But all is not quite lost; a replica Colossus has been built at Bletchley Park, which is now a museum, and can be seen there in all its glory.

  As machinery was physically destroyed, so papers were burned and the codebreakers were all sworn to secrecy—and they all kept their secrets, in many cases taking them to the grave. The attitude that wartime secrets should not be inquired into was shared by people outside Bletchley Park. When I asked Betty Houghton what she had said to her parents when they inquired about her war work, she replied, “They never asked.” The story of Enigma did not emerge properly until the 1970s, and that of Colossus became known in detail only after a crucial document, called General Report on Tunny and written in 1945, was released in 1996 under the American Freedom of Information Act. Deliciously, it is now available online to anyone with a Turing machine.15

  Tom Flowers, the man who designed and built the first electronic computer, never imagined that the secrecy would last so long. Although he was granted £1,000 by the government at the end of the war, this did not cover his personal expenditure on Colossus, so he was actually out of pocket as a result of his work. Flowers was also awarded the MBE (the same honor later awarded to The Beatles), for work designated simply “secret and important”: no details were given. His career was hamstrung by the fact that he could not reveal anything about his wartime work, and so was unable to persuade his superiors to pursue the development of electronic telephone exchanges in the post-war years. This may sound trivial, but in these days of instant global communication it is hard even for those who were around at the time to remember how primitive telephones were even in the 1950s, when “long-distance” calls (that is, anything out of town) still had to be connected by a human operator plugging leads into the appropriate sockets. It was ten years after the end of the war before the Post Office began to move into the electronic era, missing out, apart from anything else, on the opportunity to boost British exports at a time of economic hardship. But Flowers lived just long enough to see the importance of his work beginning to be recognized by the computing community. He was able to give a talk in Boston in 1982 which lifted a corner of the veil of secrecy, and in 1997, on the occasion of his own eightieth birthday, Bill Tutte gave a talk detailing the way Tunny was broken. Thomas Flowers died in 1998 at the age of ninety-two.

  Unlike Flowers, Alan Turing was able to pick up the threads of his wartime work after the completion of the Delilah project in 1945. He too was “honored” by the government, with the award of an OBE—one step up from an MBE, but such an inadequate recognition of his true worth that when Max Newman was also offered an OBE he refused it in protest at Turing's “lu
dicrous” treatment.16

  In October 1945, less than ten years after the publication of “On Computable Numbers,” Turing joined the National Physical Laboratory (NPL) at Teddington, in charge of a project to design and build an electronic “universal computing machine.” He was, in fact, head-hunted for the post by John Wormersley, the head of the mathematical research division at NPL, who had been an admirer of Turing's work since reading “On Computable Numbers.” The first fruit of this project was a report by Turing, produced before the end of the year, called “Proposed Electronic Calculator.” This contained the first full description of a practical stored-program computer—one in which the program is stored in the computer's memory, rather than being plugged in by hand. Each program, remember, can be a virtual machine in its own right, so a single computer can simulate other computers; when you open an app on a tablet or smartphone, you are actually opening a stored program that is itself equivalent to a computer. Turing's plan, as set out in this document, was more far-reaching than the work of his contemporaries in the United States (discussed in the next chapter). He was interested in developing an adaptable machine that could, through its programming, carry out many different tasks; he suggested that one program could modify another; and he understood better than his contemporaries the use of what we now call subroutines. Unlike modern computers, Turing's machine did not have a central processing unit, but worked in a distributed way, with different parts working in parallel with one another; also, instead of the instructions in a program being followed one after another in order, the program (or the programmer!) was to specify which instruction to go to next at each step. All of this made his planned computer faster and more powerful than those planned by his contemporaries; but it would require very skilled programmers to operate it. Why did Turing follow this route? As he wrote to a friend: “I am more interested in the possibility of producing models of the brain than in the practical applications to computing.”17