As I sit writing this, the tap of my fingers on laptop keys triggers massive strings of circuit defined logic which lighten or darken any of several hundred thousand pixels so that the words I type can be encoded by yet more processes and read by another brick of circuit logic before being translated by a process parallel to mine into more pixels rendered onto your screen so that you can read this sentence. As normal as computers are today, really contemplating how they work can feel as confusing and daunting as witnessing magic. But computers aren’t magic, and they weren’t always here. They owe their most basic design principles to Alan Turing, a WWII code breaker who broke Germany’s “Enigma” cipher, and, in the process, invented most of the integral concepts of the information age.
Alan Turing deserves to have an article written about him every week, but I’m writing about him today because the Bank of England recently unveiled their official design for a £50 note celebrating his life and work. Reading about it made me realize that while I was aware of Turing’s work and his impact on the war, I did not really understand what he achieved. Dear reader, it turns out that computing is hard. After close to two hours of Googling and reading, I am still not sure exactly how Turing did what he did, but this is what I did figure out.
To understand what Turing accomplished you first have to understand the problem he was trying to solve, in this case Nazi military codes. During WWII Germany used a machine called “Enigma” to encrypt all of their communications. It’s easiest to think of Enigma as the strange hybrid of a typewriter and one of those cipher wheels with two spinning alphabet rings, only vastly more complicated. Let’s look at it in steps:
- The user types a letter
- The letter is sent to the “plugboard”, which adds an arbitrary shift. For example, A becomes B, B becomes C, and so on.
- The letter the plugboard produced is sent to the first wheel, which adds another arbitrary shift based on its rotation.
- The second wheel adds a third shift to the letter produced by the first wheel.
- The third wheel adds a fourth shift to the letter produced by the second wheel.
- The letter “bounces back” along the wheels, adding a fifth and sixth shift on the second and first wheels.
- The letter, now six shifts removed from the original, is sent to a second plugboard which adds a seventh shift.
- The seven shifts removed letter lights up on a “screen” above the keys, the user writes it down.
- The outer ring of the first wheel turns one letter. When it goes through all 26 positions the next wheel will turn, and then the next. This means that double letters like “oo” will appear as different letters, for example “bh”, in the code, denying code breakers patterns.
What made Enigma so seemingly unbreakable was that the spinning wheels changed the code over time. Not only was the message encoded, but the second letter was concealed with an entirely different code from the first letter and the third from the second and so on.
In order to use the system, Axis Enigma operators kept code books with unique three letter guide strings that were agreed on well before the code was used. For example, if the code book entry for a particular day was “BCD”, the operator would know to set their first enigma wheel to A->B, their second wheel to A->C, and their third wheel to A->D. Both the transmitting and receiving machines would scramble the code over time, but since the scrambling method was universal as long as the starting points were the same each subsequent code generated would also be the same.
However, if you were, for example, an Allied code breaker and didn’t have the starting string, the probability of guessing it was 1/26^3, one multiplication for each 26 character wheel, or 1/17576. Allied code breakers were able to break some messages with educated guesses about their content, for example looking for phrases that could match to “cloudy” or “sunny” or “high wind” in air force messages. However, truly breaking the Enigma code meant finding a way to routinely pick out the one correct key from 17576 possibilities with only a matter of hours to work on each code before it was changed, or the message was no longer relevant.
Enter Alan Turing! Understand that entire books could be, and have been, written about Turing’s life and work, so in writing this I am skipping over vast and important parts of his life, but so be it. Basically Turing volunteered to join Britain’s top codebreakers at Bletchley Park, a secret cryptography base that wouldn’t be fully declassified until the 1970s. Turing asked the question: if this task is too complicated for a human to complete quickly enough, why not build a machine to do it?
In a world of smart phones and calculators that run PacMan, automating math doesn’t seem very revolutionary, but in Turing’s time it was. Turing designed a machine called the Bombe, which essentially cracked the Enigma code by doing guess and check really, really fast. Code breakers would give the Bombe, and eventually many Bombes, the scrambled messages they had intercepted. The Bombe would look at the message and ‘think’, “If the key is AAA, does the message make sense?” If the answer was yes it would stop, and if it wasn’t it would check if the code was BAA, and then CAA, and so on. But, unlike human codebreakers, it would do this so fast that it could reliably crack at least some of the German codes in just 2-4 hours, allowing Allied convoys to avoid German submarines and, eventually, paving the way for the D-Day landings and Allied victory in WWII.
If that wasn’t dramatic enough, Turing then continued his work in computing, a field he essentially invented, to create the idea of the “Universal Turing Machine”. In simple terms, a Turing machine is like a Bombe, a mechanized device that performs a set operation on arbitrary inputs. You feed it letters, and it gives you different letters based on a pattern or set of patterns. If you want it to perform a different function, like turn letters into numbers, you build a new Bombe.
A Universal Turing Machine is a meta-Bombe, or the Bombe of other Bombes if you prefer to think of it that way. Instead of a machine that computes a single function, the UTM is a machine that can compute any function. A Universal Turing Machine that stores information electronically, instead of on a tape, is a modern computer. In a very real sense, the “wheels” in your phone that turn 1s and 0s into this web page are the end of a direct lineage from Enigma, and Turing defined the concepts that made those advancements possible.
Tragically, in 1952 Turing was arrested for homosexuality, which would remain illegal in Britain until 1967. As a result of his trial, he was sentenced to twelve months of hormone “therapy”, his security clearances were removed, and he was permanently banned from employment by all sectors of the British government, including cryptography and computing research. This essentially exiled him from the frontier he created. Two years later, in 1954, he was found dead after apparent cyanide poisoning. While there is some historical debate about what happened, most historians have concluded that he died by suicide.
Featured on one of the bills the Bank of England unveiled today, 67 years after his death, is a quote from a Times interview with Turing: “This is only a foretaste of what is to come, and only the shadow of what is going to be.” He was right, about computing, dreaming of the computers that have become so integral to modern life when few people of his time could even imagine the potential. I, for one, hope that his prediction will also prove correct when it comes to historical figures who have been too often erased. Turing deserves this bill, but he also deserves so much more, as do all the other amazing people who have been written out of history textbooks because of the prejudice of others. So as I take this announcement as cause for celebration, I also hope that this single decision to remember is only a foretaste of what is to come.