Computing with Quantum Cats (4 page)

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;
⁷
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 September 4th.
⁸
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].”
⁹
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.