Alan Turing and the Enigma

Alan Turing

Zusammenfassung

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.

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 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 drums (later 108)
  │  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.

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 prescient prediction: that by the year 2000, machines would be capable of passing the test under reasonable conditions.

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.

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.