Monday, June 07, 2004


50 years ago today Alan Turing brushed some cyanide crystals onto an apple, tucked himself into bed in his Cheshire home, and drifted off into his final sleep with the bluish tinge of cyanide on his lips. His many accomplishments include inventing the theory of computation that brought forth the modern computer and cracking the German Enigma and Fish codes in the second world war - if he hadn't been so unfathomably brilliant, there is a pretty good chance you'd either be reading this in German or not reading it at all for want of suitable technology.

Unfortunately, the classified nature of his work meant that there was no public awareness of his invaluable contributions to the war effort. They were aware, however, of his homosexuality, which (classified as 'gross indecency') was illegal at the time in Britain. Male homosexuality, that is... lesbianism was never a crime in England because Queen Victoria said "women don’t do such things". When one of Turing's flings stole some money from him and he reported this to the police, the ensuing investigation revealed Turing's homosexuality, and his society dealt with him in the standard manner of the times: estrogen shots to subdue his libido. There is some belief that the 'fling' in question was working for British intelligence, which had harassed Turing and denied him a position - no pun intended, but this was like removing their queen from the board - because of his sexuality.

Turing's early work on the theory of computation opened the door for the modern electronic computer. The first practical application of his ideas, however, was a mechanical device. While the Germans were busy dropping bombs all over Britain, Turing himself dropped the Bombe into Hut 11 at Bletchley Park, the center of the British cryptanalysis effort in the war. This device used Turing's ideas (and some ace statistical work done by Polish mathematicians) to reduce the possible decodings of intercepted Enigma ciphertext from almost infinite numbers to a size that could most often be tackled in a day, before the codes changed at midnight and the process would start all over again.

The ability to decode intercepted German messages gave the Allies a tremendous advantage in the war (particularly in the Atlantic, where German subs were sinking millions of tons of relief supplies bound for Britain from the US), but it also created a conundrum: acting on a certain piece of data might prove to the Germans that the Allies had broken their code, and then they would change it and we'd all be fucked. This led to a few situations where the Allies had to sit back and watch their ships or cities be destroyed to avoid showing their hand.

With his work at Bletchley Park, Turing probably contributed more to the Allied war effort than any other single person anywhere. His idea of a universal computing machine, which eventually led to the computer you are using right now, has had similar effects on the world at large: an information revolution to rival or even surpass the industrial revolutions of previous ages. Thinking of what this one man did for the world, I'm reminded of that scene in The Fellowship of the Ring where Legolas chastises Boromir, saying 'you owe him your allegiance'.

Turing's memorial in Sackville Park, Manchester, includes a life-size bronze statue of Turing sitting on a bench, apple in hand. His epitaph reads

Alan Mathison Turing
Father of computer science, mathematician, logician, wartime codebreaker, victim of prejudice

I've always wondered about Turing's choice of suicide method: there are other stories in which poisoned apples play a part, from the book of Genesis to Snow White. It is easy to imagine Turing finding some fitting symbolism in one or both of those stories to guide his hand.


For Turing's life story, the BBC's Breaking the Code (double-entendre here: Turing broke the German war code with his genius, and the British social code with his sexuality) starring Derek Jacobi is a little slow but covers the more personal side of Turing's life quite well.

His technical achievements can be found in hundreds of books, but the best explanation I've read of the process used to decode Enigma is in The Code Book by Simon Singh. This webpage also gives an excellent and thorough introduction to the workings of Enigma and the techniques used to break it. There are also some online Enigma simulators (such as this 3-rotor java applet version) if you get to the point where you want to actually try it yourself.

The best film I've seen on the subject doesn't explicitly feature Turing - in Enigma, the main character (Tom Jericho, played by Dougray Scott) is a mashup of Turing and a few other historical characters, the result of some creative license on the part of the screenplay writer (Tom Stoppard, who also did Brazil, Empire of the Sun, Rosencrantz and Guildenstern Are Dead, and Shakespeare in Love). This film does an excellent job of explaining the immensity of the problem they faced:

Tom Jericho: Enigma is a very sophisticated enciphering machine, and Shark is its ultimate refinement. So... we're not talking about the Times crossword here... it weighs twenty-six pounds, battery included, and goes anywhere. The Enigma machine - the Germans have thousands of them.
Hammerbeck: What's it do?
Tom Jericho: It turns plain-text messages into gobbledygook. Then the gobbledygook is transmitted in Morse. At the other end is another enigma machine, which translates the message back to the original text. Press the same key any number of times, it'll always come out different.
Hammerbeck: And you have one of your own.
Logie: Uh, courtesy of the Polish Cipher Bureau.
Hammerbeck: So what's the problem?
Tom Jericho: The problem? The problem is the machine has a hundred and fifty million, million, million ways of doing it, depending on how you set these three rotors, and these four plugs.
Hammerbeck: And that's Shark?
Tom Jericho: No. No, no, no, this is the one we can break. Shark is enciphered on a special Enigma machine with a fourth rotor, designed especially for U-Boats - which gives it about four thousand million, BILLION starting positions. And, uh, we've never seen one.
Hammerbeck: Holy shit...

The math nerd in me is a little bit peeved that the second 'harder' number he gives is actually smaller than the first one by a factor of 37.5, I guess they figured since they only used the word 'million' in the 3-rotor description and they used the word 'billion' in the 4-rotor description, and 'billion' is clearly bigger... doh. In reality, the 3-rotor version has about 3*10114 possible configurations, while the 4-rotor version has about 2*10145 possible configurations. Turing's breakthrough ideas reduced these numbers to a maximum of 'only' about 1023 possible configurations, and the analytic techniques he and his cohorts developed brought that number down much lower, until it was within reach of the Bombes.

If you're interested in the science of cryptography, there's really only one place to start: Bruce Schneier's Applied Cryptography. If you're still interested/able/sane after reading that and you want to go further, Lawrence Washington's Elliptic Curves: Number Theory and Cryptography is pretty good.

If you're interested in fiction that involves cryptography, here too there is really only one place to start: Neal Stephenson's Cryptonomicon.