Computing with Quantum Cats Read online

  Not long after this, Turing had another experience that made a deep impression on him. In Cambridge that October he saw the Disney film Snow White and the Seven Dwarfs, and became fascinated by the scene in which the Evil Queen prepares the apple for Snow White. He used to go around reciting her incantation:

  Dip the apple in the brew,

  Let the Sleeping Death seep through.

  BLETCHLEY AND THE BOMBE

  GC&CS had become aware of the need to recruit mathematicians in case war should break out largely because of the adoption by the German military of a cipher machine called Enigma. The version of Enigma in use at that time contained three moveable discs (called rotors) in a line and a fourth, fixed, “reflector,” each with twenty-six electrical contacts, one for each letter of the alphabet. An electronic signal produced by pressing an individual letter on a keyboard (A, perhaps) passed into the first rotor and out through a different contact (maybe corresponding to L) into the adjacent contact in rotor two, and so on for rotors two and three, following a path determined by the alignment of the rotors and their internal wiring; then it was scrambled once more before being reflected back from the fourth rotor. After another three stages of scrambling, going back through the three rotors in reverse order, it then lit up a light bulb corresponding to another letter of the alphabet (crucially, never the same letter as the original keystroke). The operator then entered this as the first letter of the coded message, and proceeded to the next—but as that next key was pressed, the rotors moved on one click, so that a different electrical path would now be followed, and if the operator pressed A twice in a row, for example, two different letters would appear in the coded message.

  The great practical advantage of these machines, thanks to the reflection process, was that, assuming the rotors of two machines were set up in the same way to start with, in order to decipher the message coded on one machine and broadcast by, say, Morse code, an operator far away using the other machine had only to type in the coded message, letter by letter, to retrieve the original plain text. The military version of Enigma also included a development called a plugboard, which involved literally plugging wires into pairs of holes in a board to connect pairs of letters at the first stage of the coding process. If, for example, J and G were joined in this way, and also Q and B, pressing key J would send the signal through contact G on the first rotor, not through J, and back perhaps as the coded letter Q which would follow the plugboard to emerge as B. Fortunately for the codebreakers, only six or seven pairs of letters were usually connected in this way.

  There are 26 × 26 × 26 = 17,576 different ways to connect the three rotors in such a machine (the reflector does not rotate), and the code for a particular message could be cracked (if you knew the wiring of the rotors themselves) simply (if tediously) by trying out all 17,576 combinations to find the one that worked. The three rotors could be arranged in six different orders (1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,1,2; 3,2,1), but even 6 × 17,576 is not a number to daunt cryptanalysts. A plugboard with seven possible pairs out of 26 letters, though, introduced 1,305,093,289,500 ways of setting the machine for each of the 6 × 17,576 rotor settings. This was such a high number that the Germans were convinced that the Enigma code was uncrackable, and initially the British, sharing that view, devoted little attention to it. But, through a combination of luck and brilliance, the Poles, deeply concerned about the threat to their country from the Nazis, found a way into Enigma.

  The luck came in 1932, when French spies got hold of a set of instructions which could be interpreted to reveal the wiring of the Enigma rotors. The French shared this information with their allies Poland and Britain, but only the Poles had the initiative to set a team of mathematicians the task of interpreting the information in this way. The skill came first in unraveling the wiring, and then in breaking the pattern used by the Germans to set up the Enigma machines each day. These basic settings were laid down in a set of instructions issued to all operators, and known as a “ground setting.” This would involve arranging the order of the rotors, then adjusting the three rotors, rather like setting a combination lock, so that a particular set of three letters, such as BKW, was at the top. Using this setting, the operator would choose his own setting for the rotors, perhaps XAF, and encipher this twice, producing a six-letter string such as AZQGBP, and send this on the ground setting before turning the rotors to the chosen setting and enciphering his message.

  The snag was that each operator was using the same triplet, coded twice, based on the same rotor setting, at the start of every day—so that hundreds of short messages with identical content were going out coded the same way. The system was later improved so that although all operators used the same rotor setup each day, each operator could choose the initial setting and transmit it uncoded, in plain language, before going through the rest of the setup procedure. Even with this refinement, the repetition involved, and details such as the fact that no letter could be coded as itself, produced patterns when many messages were analyzed, and this enabled the Poles to draw up statistical tables from which they could eliminate most possible settings of the Enigma machines each day and end up with the right setting. This was still a time-consuming process to carry out by hand. But the great breakthrough came when the Poles devised an electromechanical machine, using commercially available relays like those in Turing's prototype multiplier, to work through all the possibilities. The relays clicking inside the machine when it was working made a sound like the ticking of the clockwork mechanism of a time bomb, so the machines became known as Bombas to the Poles, and more advanced machines, essentially developed by Turing and superficially similar to the Polish devices, were later dubbed Bombes by the British.

  Until the end of 1938, with the aid of their Bombas the Poles were cracking the German Enigma codes not because Enigma was inherently unsafe, but because the Germans, complacently sure it was uncrackable, were careless in its use. This would be a recurring theme: what should have been an uncrackable system (and was, when used properly—by the German navy, in particular) was compromised by foolishness at high level, as in the use of repeated triplets just described, and personal stupidity at lower levels, as when operators began or signed off their messages “Heil Hitler” or used a girl's name for their initial rotor setting.

  It was further made vulnerable by the carelessness of its operators and the bureaucratic nature of their system, so that many messages might begin with the German words for “Daily Report,” for example. One way into a message would be to take a “crib” for a common word, such as Flugzeug (airplane) and find a match by “dragging” a string of letters corresponding to the word through a message;7 and there were other statistical techniques. This process was greatly simplified by the German habit of using standard phrasing: for example, starting weather reports with the words Wetter für die Nacht (“weather for the night”) and instructions sent out to Luftwaffe squadrons with the phrase “special instructions for” followed by the squadron number. But all that only just made the Enigma codes crackable, and the cryptanalysts’ work often suffered setbacks—as at the end of 1938, when the Germans introduced two new rotors for each machine, making sets of five, from which three were chosen each day. Instead of there being six ways to order the rotors actually used, there were now sixty possibilities, and even with the aid of their Bombas the Poles could no longer cope. Worse, early in 1939 the Germans increased the number of pairings on the plugboard from six to ten. This was the situation in the summer of 1939 when, with war looming, the British and French sent teams to Warsaw to discuss the situation, and were astonished when the Poles revealed what they had managed to achieve.

  Not the least of those achievements was that the Poles managed to keep the secret of the Bombas and the cracking of Enigma from their German occupiers after their country was invaded in September 1939. By then, GC&CS had been moved to a country house in Buckinghamshire, Bletchley Park, where Turing was among the prospective codebreakers ordered to report on Septemb
er 4th.8 There, he was instrumental in the design and manufacture of the British Bombes, much more sophisticated machines capable of dealing even with the five-rotor system and the ten pairs of plugboard settings, provided the German operators of Enigma were careless enough to provide scraps of “cribs” such as weather reports headed Wetter, girls’ names used for ring settings, and at least one occasion when an operator had to repeat a long message and sent it twice using the same rotor settings. Without such cribs, the task of cracking Enigma would have been impossible; even with the cribs, it was horrendously difficult. The British Bombes—which, in spite of their name, were different from and far superior to the Polish Bombas which were their inspiration—each stood nearly 7 feet high, was a full 7 feet wide, and weighed a ton. Each simulated the effect of thirty Enigma machines (later versions were essentially thirty-six Enigmas wired together) working at once through all the possibilities for a particular message. And they only worked at all because of Alan Turing. There is no need to go into all the details here, but as Simon Singh has summed it up, “only Turing, with his unique background in mathematical machines, could ever have come up with [the British Bombe].”9 Turing worked out the logic of a system whereby the setup of the Enigma machines on a particular day could be worked out using cribs; the genius of his system was that instead of working through each possible setup until the codebreakers hit on the right one (by which time the setup might have been changed), he showed that it was possible to find all the wrong answers at once, leaving the correct setup clear by default. His logic was translated into the mechanics of the British Bombes by the British Tabulating Machine Company, based at Letchworth, in Hertfordshire; a key refinement of Turing's technique, speeding up the codebreaking significantly, was made by his colleague Gordon Welchman.

  It has been estimated by sober military historians that through the success of this project Turing was personally responsible for shortening the war by two years. He may even have been responsible for keeping Britain in the war at all; in the summer of 1941, after a desperate period when shipping was being sunk at such a rate that the country was on the brink of starvation, thanks solely to the codebreakers at Bletchley and their Bombes there was a period of twenty-three days without a single sinking, because convoys were being routed away from known U-boat positions. But the entire Bletchley Park effort was kept under wraps, and details only emerged decades later. Turing never spoke about it—not so much because he was bound by the Official Secrets Act, but because he had promised not to speak about it, and to Turing promises were never made lightly and always to be kept.

  Many of the stories about Turing's eccentricity date from his time at Bletchley Park. Some of these seem not unreasonable, such as his habit of cycling to work wearing a gas mask during the hay-fever season. Others, such as the time he was hauled over the coals for failing to sign his identity card and replied that he had been told not to write anything on the document, may have owed as much to bloody-mindedness as to an autistic literalism. In order to learn how to shoot, Turing joined the Home Guard, and when confronted with a form which asked, among other things, “Do you understand that by enrolling in the Home Guard you place yourself liable to military law?” wrote “No” in the appropriate space and went on to the next question. Having learned to shoot, Turing stopped attending the Home Guard, and was summoned before a Colonel Fillingham who warned him that he was subject to military law and could not pick and choose when to attend parade. Turing calmly explained the situation, the form was dug out from the files, and the authorities were forced to admit that he had never actually been a member of the Home Guard at all. Turing had got what he wanted, by being scrupulously honest and upfront. If others chose to make mistakes, then, as with the careless German Enigma operators, that was their lookout.

  Turing's mother recalls an incident which, although she could not have known it when she wrote her book, showed how his approach to problem-solving in everyday life resembled his approach to codebreaking. While at Bletchley, Turing had a bicycle with a fault which made the chain come off after a certain number of revolutions of the pedals. In order to avoid having to stop and re-fix the chain, he first hit on the approach of counting the number of turns of the pedals so that he could make a suitable jiggle at the right time to stop it jumping off its sprocket. Then, he fitted a counter on the bicycle to keep track of the rotation of the wheels for him. Finally, he discovered that there was a mathematical relationship between the number of rotations of the pedals, the number of turns of the wheel and the number of spokes in the wheel. The statistics revealed that the problem was caused by a bent spoke coming into contact with a slightly damaged link in the chain at regular intervals. When the spoke was straightened, the problem was solved. As Sara Turing says, “a bicycle mechanic could have fixed it in five minutes.” But Turing's approach was entirely logical—especially to a codebreaker involved in analyzing the wheel patterns of Enigma machines.

  One of the more curious aspects of Turing's life while working at Bletchley Park was that in 1941 he got engaged, to Joan Clarke, a mathematician and colleague. It was only after Joan had accepted his proposal of marriage that Alan told her about his “homosexual tendencies,” but she seemed entirely unworried, and the relationship continued as a close friendship until Alan decided that he could not go through with the charade, and broke the engagement off. At the time, nobody except Joan knew the real reason why.

  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, bu
t too late to play a part in the war effort.10 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.11 That message would, of course, be quite transparent, since the teleprinter language was no secret.