Computing with Quantum Cats (5 page)

Although he was instrumental in the success of the Bombe, Turing did not play a central role in the development of its successor, the first electronic computer, Colossus. His later contribution to the war effort took him in different directions—first, in November 1942, to the United States, sailing on the
Queen Elizabeth
to bring the Americans up to speed on the codebreaking work being carried out in the UK. He met up with his cryptographic counterparts in the US Navy's “Communications Supplementary Services (Washington)” branch, or CSSW, then moved on to the Bell Laboratories, at the time part of the American Telephone and Telegraph Company (AT&T), where he became engrossed in the problem of “scrambling” speech, so that voice conversations could be transmitted in a form that could not be deciphered without the right equipment. There, Turing met Claude Shannon. They were working on separate secret projects, and could not discuss their war work with one another; but they discovered a shared interest in the possibility of thinking machines, and encouraged each other to speculate about the possibilities. Lunching with Shannon in the executive dining room one day, Turing brought the hubbub of conversation in the room to a halt by declaring
loudly to his friend: “I'm not interested in developing a
powerful
brain. All I'm after is just a
mediocre
brain, something like the President of the American Telephone and Telegraph Company.” And he went on to consider the possibility of a computer that would follow the stock market and give advice on when to buy or sell.

There may have been more to this than unthinking honesty. John Turing says that although his brother could not stand social chat, “what he really liked was a thoroughly disputatious exchange of views,” and if “you ventured on some self-evident proposition, as, for example, that the earth was round, Alan would produce a great deal of incontrovertible evidence to prove that it was almost certainly flat.”

It is likely that Turing visited Princeton during his wartime travels in the United States; his mother recalled his mentioning such a trip, but there is no official record of such a visit. In the spring of 1943 he returned to Britain. While he had been away, the key turning point of the war in Europe occurred with the surrender of the German forces at Stalingrad on February 2, 1943. But this did nothing to reduce the risks of traveling by ship across the North Atlantic, where the U-boats were still very active. Turing sailed on the
Empress of Scotland
on March 23, nine days after the
Empress of Canada
had become one of their many victims; he might easily have been on the earlier ship.

Back in Britain, Turing's work concentrated on the speech encipherment system, codenamed Delilah, which would eventually work, but too late to play a part in the war effort.
¹⁰
This project was based not at Bletchley, but at a nearby secret center, Hanslope Park. So Turing was also physically distanced (if only by about 10 miles) from the new hardware
developments at Bletchley. But his fingerprints were all over the techniques used by the Bletchley team, and he would re-engage with the fruits of their labors after the war.

THE FLOWERING OF COLOSSUS

In the summer of 1941, the British intercepted a new kind of radio traffic, codenamed Tunny, operating initially between Berlin and Greece. This was an experimental link which operated until October 1942, when it was modified and began to appear on other routes, including those between Berlin and the German forces in Russia, from Berlin to Rome and North Africa, and to Paris. It emerged that this was being used for high-grade information, including direct orders from Hitler; a potential gold mine for the British and their allies. But Tunny was very different from Enigma, and even harder to crack.

The first difference was that Tunny used teleprinter language, rather than Morse code. This was not a problem in itself, but needs some explanation. Instead of the strings of dots and dashes produced by Morse, teleprinters represent letters of the alphabet and a few punctuation marks in terms of groups of five “on or off” symbols. These symbols could be represented by holes punched across the width of a paper tape, one and a half inches wide, where a hole meant “on” and no hole meant “off.” These symbols were usually represented by o and x, so that a single letter in teleprinter language might read xxoxo, and so on. This is exactly equivalent to a five-bit binary language, in which the same letter would be represented by 00101. A series of these “letters” was punched automatically along the tape as an operator typed on a teleprinter machine, which was rather like a typewriter. The
tape could then be fed into a transmitter and run at high speed, broadcasting the message in a concentrated burst of radio transmission. At the other end, the incoming message was read automatically by the receiving apparatus and used to punch out the holes in another strip of paper tape, which could be fed into a teleprinter machine to print out the message.
¹¹
That message would, of course, be quite transparent, since the teleprinter language was no secret.

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, which 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.”
¹²