Alan Turing and the Enigma

Abstract

This article traces the life and work of Alan Turing, mathematician, codebreaker, computer theorist, and one of the most consequential and most wronged scientists of the twentieth century. In 1936, before electronic computers existed, he defined what computation is and proved what it cannot do. During World War II, he led the team that broke the German Enigma cipher, an achievement that altered the course of the war and remained classified for decades. In 1950, he posed the question that launched the field of artificial intelligence. In 1952, he was prosecuted by the government he had helped save, chemically castrated as a condition of avoiding prison, and died two years later. He was forty-one.

Alan Turing at age 16. Image: public domain, via Wikimedia Commons.

The Making of a Mathematician

Alan Mathison Turing was born on June 23, 1912, in London. His childhood was disrupted by his parents’ years in India; he and his brother spent long periods boarding with families in England while their parents were abroad. The emotional distance became habitual. Turing grew into a solitary, intensely focused young man with no particular interest in social convention and an extraordinary one in mathematics and science.

At Sherborne School in Dorset, his gifts created problems rather than opportunities. The school valued the classics; Turing was interested only in mathematics and natural science. His reports described him as brilliant but difficult to teach; he worked independently, often arriving at results by methods his teachers could not follow. A school report from 1927 complained: “If he is to stay at a Public School, he must aim at becoming educated. If he is to be solely a scientific specialist, he is wasting his time at a public school.”

He arrived at King’s College, Cambridge in 1931 and found his element. He read mathematics, graduated with first-class honors in 1934, and was elected a Fellow of King’s in 1935 (an extraordinary distinction for a twenty-two-year-old) on the basis of a dissertation on the central limit theorem. He had proved the theorem independently, not knowing that it had already been proved. His examiners recognized that the independent derivation demonstrated exceptional ability.

On Computable Numbers: The Paper That Defined a Field

In 1936, Turing submitted a paper to the Proceedings of the London Mathematical Society that would become one of the most important mathematical papers of the century: “On Computable Numbers, with an Application to the Entscheidungsproblem.”

The Entscheidungsproblem (Decision Problem) had been posed by the mathematician David Hilbert in 1928. It asked whether there existed a mechanical procedure that could, for any mathematical statement, determine in finite time whether the statement was true or false. Hilbert believed the answer was yes. Turing proved it was no.

The Entscheidungsproblem

Hilbert’s question was not merely technical. It touched on the deepest assumptions of mathematics: that any well-formed question had a determinate answer, and that mathematics was, in principle, completable. Kurt Gödel had already shaken this optimism in 1931 with his incompleteness theorems, proving that any sufficiently powerful formal system contained true statements it could not prove. Turing’s result was a companion: not only were there unprovable truths, there was no algorithm that could reliably identify which questions had answers. Some problems were, in a precise technical sense, undecidable.

To prove this, Turing needed a precise definition of what an “algorithm” or “mechanical procedure” was. In 1936, no such definition existed. He invented one.

He described an abstract machine (what we now call a Turing Machine) consisting of an infinitely long tape divided into cells (each containing a symbol or blank), a read/write head, and a finite set of states governing what the head would do given the current symbol and state: write a symbol, move left or right, and transition to a new state.

  Turing Machine — Conceptual Model:

    ┌──────────────────┐
    │  State Register  │  ← current state (e.g., q3)
    └────────┬─────────┘
             │  (reads current symbol, applies transition rule)
             ▼
    ┌───┬───┬───┬───┬───┬───┬───┬──────┐
    │ 1 │ 0 │ 1 │[1]│ 0 │ B │ 1 │  ... │  ← infinite tape
    └───┴───┴───┴───┴───┴───┴───┴──────┘
                  ↑
            Read/Write Head
            (can move left or right, write symbol, change state)

The machine was a thought experiment, not a blueprint. But Turing showed it was powerful enough to simulate any algorithm that could be carried out by a human following explicit rules. He then constructed a specific Universal Turing Machine, a machine that could read a description of any other Turing Machine from its tape and simulate it. Every general-purpose computer ever built is, in this sense, a physical instantiation of Turing’s 1936 abstraction.

The proof of undecidability rested on a specific construction, the Halting Problem. Turing showed that no Turing Machine could determine, for every possible input, whether an arbitrary program would eventually halt or run forever. The proof was elegant and devastating: assuming such a machine existed led to a logical contradiction, so it could not exist.

Unknown to Turing, the American mathematician Alonzo Church had independently proved the same result using a different formalism (the lambda calculus) a few months earlier. Turing travelled to Princeton in 1936 to work under Church and received his PhD in 1938. The two results are now unified as the Church-Turing Thesis: any function computable by an effective procedure can be computed by a Turing Machine. It remains the foundational definition of computation.

Bletchley Park: The Polish Foundation

When war broke out in 1939, Turing reported to Bletchley Park, a Victorian estate in Buckinghamshire that served as the Government Code and Cypher School. His task was the German Enigma machine.

The Enigma was an electromechanical cipher device used by all branches of the German military. It worked through a series of rotating wheels (rotors) that scrambled each letter of plaintext into a different letter of ciphertext, and, crucially, the substitution changed with every keypress, so typing the same letter twice produced two different ciphertext letters. The theoretical number of possible configurations was astronomically large; without knowing the day’s settings, decryption appeared impossible.

What the British knew (what few in Britain publicly acknowledged for decades) was that the Polish had already broken Enigma before the war.

Marian Rejewski, Jerzy Różycki, and Henryk Zygalski of the Polish Cipher Bureau (see The Polish Cryptologists Who Broke Enigma) had attacked Enigma mathematically in the early 1930s. Exploiting a procedural flaw in how German operators transmitted their daily message keys, Rejewski reconstructed the internal wiring of the Enigma rotors purely from intercepted ciphertext, without ever seeing the machine. By 1938, the Poles had built electromechanical devices called Bomba (bomby, plural) to automate the search for daily settings.

When Germany added complexity to the Enigma procedure in 1938 (rendering the Bomba insufficient) the Poles shared their work with Britain and France in a secret meeting in Warsaw in July 1939, weeks before the German invasion. Turing arrived at Bletchley in September 1939 already equipped with this foundation.

The Bombe and the Crib Method

Turing’s contribution was to redesign the attack from first principles. The Polish Bomba had exploited a specific procedural weakness that Germany had now closed. Turing needed a method that could work against correctly used Enigma.

His key insight was the crib: a guessed fragment of plaintext. Enigma operators were military personnel who followed predictable habits, weather reports began with WETTER (weather), messages often ended with HEIL HITLER, certain station identifiers appeared reliably. If you could guess what part of a message said, you could use the Enigma’s own properties to constrain the search for the day’s settings.

The Enigma had one critical self-defeating property, exploited by Turing: no letter could ever encrypt to itself. This property, built in for technical reasons by the original designers, was cryptographically disastrous. Given a guessed crib, Turing could generate chains of logical constraints on the rotor settings, and the Bombe, his electromechanical device, tested these constraints in parallel across all rotor positions, eliminating impossible settings and identifying candidates for hand-testing.

  The Bombe — Attack Method:

  Intercepted ciphertext:  X Q R M P J A T ...
  Guessed crib (plaintext): W E T T E R V O ...
            ↓
  Generate logical chain: if rotor position n is X,
  then position m cannot be Y (Enigma can't encrypt A→A)
            ↓
  ┌─────────────────────────────────┐
  │  Bombe: test all rotor positions │  ← 36 scramblers (108 drums)
  │  simultaneously, discard any    │     running in parallel
  │  that produce a self-encryption  │
  └──────────────────┬──────────────┘
                     ↓
            Candidate settings → hand-tested on Enigma replica

Gordon Welchman made a crucial improvement: his diagonal board added additional logical connections between the Bombe’s test circuits, dramatically reducing the number of false positives and making the machine orders of magnitude more efficient. Welchman later wrote that without the diagonal board, the Bombe might not have been operationally viable.

By 1940, Bombes were being produced. By the end of the war, more than two hundred were operating at Bletchley and at outstations. They broke Enigma settings for the Luftwaffe and Army reliably; the naval Enigma (which used an additional fourth rotor) required a separate campaign, including the physical capture of Enigma materials from German vessels.

The intelligence product, codenamed Ultra, provided the Allied high command with a real-time window into German operational planning. Historians estimate it shortened the war by two to four years. The assessment was classified until the 1970s; Turing’s central role was not publicly acknowledged until the 1980s.

The Man Who Certified Enigma

On the German side, checking Enigma’s security fell partly to Gisbert Hasenjäger, a young mathematician conscripted into the cipher department of the Wehrmacht High Command (OKW/Chi). Ordered by the mathematician Karl Stein to hunt for weaknesses, Hasenjäger examined an unsteckered three-rotor Enigma, found one flaw, and missed the decisive one: the reflector guaranteed that no letter ever encrypted to itself, the exact property Turing’s crib method turned against the machine. Only in the 1970s, when the Bletchley story was declassified, did Hasenjäger learn that Enigma had been broken at all, or that Turing had led the work. In 1963 he had built a working universal Turing machine out of surplus telephone relays; it now sits in the Heinz Nixdorf Museum in Paderborn. The man who signed off on Enigma’s security spent part of his later life building Turing machines by hand.

Dead End: The ACE Computer

The war ended in 1945. Turing, now employed by the National Physical Laboratory, produced in 1945–46 a detailed design for a stored-program electronic computer he called the Automatic Computing Engine (ACE). It was among the most sophisticated computer designs of its era, drawing on his theoretical work from 1936 and on what he had learned at Bletchley. It had a hierarchical memory architecture, a flexible instruction set, and specifications that would have made it one of the fastest computers in the world.

The NPL did not build it.

The Bureaucracy That Delayed British Computing

The ACE design was caught in institutional caution and inter-departmental conflict. NPL administrators were uncertain about committing resources to an unproven technology; there were disputes about who would build the hardware; decisions were deferred. Turing, frustrated and increasingly isolated, left the NPL in 1947 and returned to Cambridge. A scaled-down version (the Pilot ACE) was eventually completed in 1950, two years after simpler machines had run at Manchester and Cambridge, and well behind what a committed effort could have achieved in 1946.

The contrast with the United States, where military funding drove rapid computer development through von Neumann’s work at Princeton and the ENIAC team’s commercial descendants, illustrates how institutional environment shapes technological pace. Britain produced the theoretical foundations of computing in Turing’s 1936 paper. It fell behind in implementation by nearly five years.

Turing moved to Manchester in 1948, where Freddie Williams and Tom Kilburn had built the Manchester Baby (the Small-Scale Experimental Machine), the machine that ran the world’s first stored-program computation in June 1948, and were developing its full-scale successor, the Manchester Mark 1. He contributed to its software and to the design of its successor. It was practical, direct work, a long distance from the universal machines of his 1936 imagination, but the same idea made physical.

The Imitation Game

In 1950, Turing published a paper in the philosophy journal Mind that he opened with a question he immediately decided not to answer: “Can machines think?”

The question was too tangled in philosophy. Instead, he proposed an Imitation Game: a human judge communicates by text with both a human and a machine. If the judge cannot reliably distinguish them, the machine passes. The test (universally known today as the Turing Test) sidestepped metaphysics and replaced it with behavior. You did not need to resolve whether the machine was truly thinking; you only needed to observe whether it was indistinguishable from something that did.

The paper anticipated objections that would not be formally published for years (the Chinese Room argument, the theological objection, the argument from mathematical incapacity) and addressed each with characteristic precision. It also contained a prediction that by the year 2000, machines would be capable of passing the test under reasonable conditions.

Two years earlier, in an unpublished 1948 report for the NPL titled “Intelligent Machinery,” Turing had framed the human side of the same question. Machine intelligence, he argued, could no more be built in isolation than human intelligence was: “the isolated man does not develop any intellectual power. It is necessary for him to be immersed in an environment of other men, whose techniques he absorbs during the first twenty years of his life.” From this it followed that “the search for new techniques must be regarded as carried out by the human community as a whole, rather than by individuals.” Intelligence, for Turing, was a social product, an unsentimental claim from a man who spent much of his life as an outsider.

The paper became the founding document of artificial intelligence as a research program. Its fuller context and the history it initiated are traced in The Rise of Artificial Intelligence.

Morphogenesis: The Shape of Living Things

In 1952, Turing published a paper in a completely different field: “The Chemical Basis of Morphogenesis.” It was the most technically demanding paper he produced, combining partial differential equations, chemistry, and biology to address a question that had puzzled scientists since Darwin: how does a uniform ball of cells develop into an organism with differentiated structures, stripes, spots, limbs, segments?

Turing’s answer was reaction-diffusion systems: two chemical substances (he called them “morphogens”) diffusing through tissue at different rates, one activating growth and one inhibiting it. The interaction of these two processes could spontaneously generate regular spatial patterns from a uniform initial state, a mathematical explanation for why leopards have spots and fish have stripes.

The paper was largely ignored during his lifetime. Decades later, it was recognized as foundational to the field of mathematical biology and confirmed experimentally in systems from animal pigmentation to the development of limb buds.

The Human Cost

In December 1951, Turing began a relationship with a young man named Arnold Murray. In January 1952, Murray’s acquaintance broke into Turing’s house in Manchester. Turing reported the burglary to the police. The subsequent investigation revealed his relationship with Murray. Both men were charged with “gross indecency” under the 1885 Criminal Law Amendment Act, the same law that had been used to prosecute Oscar Wilde fifty-seven years earlier.

Turing did not deny the charge or express remorse. He saw nothing wrong with what he had done. He was convicted in March 1952 and given a choice: prison or chemical castration, a course of estrogen injections intended to suppress sexual drive, imposed as a condition of probation. He chose the injections.

The physical effects were significant. The psychological effects are harder to document. Turing’s friends and colleagues noted changes in his demeanor but also reported that he continued working, continued running, and retained his characteristic dry humor.

On June 8, 1954, Turing’s housekeeper found him dead. On his bedside table was a half-eaten apple. The inquest returned a verdict of suicide by cyanide poisoning. He was forty-one years old. Whether the apple had been laced with cyanide (as the inquest implied) or whether the cyanide came from electroplating experiments he kept in his home (a hobby) was never definitively established.

The classified nature of his wartime work meant that his death passed without public acknowledgment of what had been lost. His name did not appear in the history books for another twenty years.

Myth: Apple’s bitten-apple logo is a tribute to Turing’s poisoned apple

A beloved story holds that the bite in Apple’s logo honours Alan Turing, who died beside a half-eaten, supposedly cyanide-laced apple. It is not true. Rob Janoff, who designed the logo in 1977, has said he had never heard of Turing at the time; the bite exists purely for scale (so the silhouette reads as an apple rather than a cherry or tomato) and the “byte” pun was noticed only afterward. Steve Jobs himself, asked about the Turing legend, reportedly replied, “God, we wish it were true.” The death itself is also less certain than the legend suggests: the apple was never tested for cyanide, and the historian Jack Copeland has argued the evidence is consistent with accidental inhalation from Turing’s electroplating hobby. See Myths and Misconceptions.

Legacy: Rehabilitation, Delayed

The Turing Award (the highest honor in computer science, awarded annually by the ACM) was established in 1966 and named for him. It carries a prize of one million dollars and is considered the Nobel Prize of computing.

Britain’s formal acknowledgment took longer. Prime Minister Gordon Brown issued an official apology in 2009: “Alan Turing was treated terribly, which we should be ashamed of.” Queen Elizabeth II granted a royal pardon in 2013, sixty years after the conviction. A private member’s bill known informally as the Turing Law was passed in 2017, extending a posthumous pardon to all men convicted under the same law.

In 2021, Turing’s image appeared on the British £50 note.

His theoretical framework (the Turing Machine, the Halting Problem, the Church-Turing Thesis) remains unchanged. Every computer program ever written operates within the limits he defined in 1936. The architecture his ACE design pioneered is traced in The Von Neumann Architecture. The programming language tradition he helped motivate is explored in The Evolution of Language.