Alan Turing and the Enigma

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 intense 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. In his report for the summer term of 1927, the headmaster, Nowell Smith, wrote: “I hope he will not fall between two stools. 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 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 March 1935, aged twenty-two, on the basis of a dissertation on the central limit theorem. He had proved the theorem independently, not knowing that Jarl Waldemar Lindeberg had already proved a version of it in 1922. His examiners accepted the independent derivation as fellowship-worthy work.

On Computable Numbers

In May 1936, Turing submitted a paper to the Proceedings of the London Mathematical Society, published in the volume for 1936–37: “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.

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 diagonal argument. Turing showed that no machine could decide, for an arbitrary machine description, whether that machine was “circle-free” (would go on printing digits forever) or would ever print a given symbol; assuming such a decider existed led to a contradiction. Today this is usually taught as the Halting Problem, but the name and the modern formulation come from later work by Stephen Kleene (1952) and Martin Davis (1952–58); Turing’s 1936 machines did not even have a halting state.

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 September 1936 to study under Church and received his PhD in June 1938. Turing showed that his machines and Church’s lambda calculus define the same class of functions, and the claim that this class captures every effective procedure is now called the Church-Turing Thesis. It is a thesis, not a theorem, but it remains the working definition of computation.

Bletchley Park and the Polish Groundwork

When war broke out in 1939, Turing, who had already worked part-time for the codebreakers, 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 from 1932. Exploiting a procedural flaw in how German operators transmitted their message keys (each key was enciphered twice), Rejewski reconstructed the internal wiring of the Enigma rotors without ever seeing a military machine. Group theory alone was not quite enough: the decisive extra input was a set of German key tables for September and October 1932, bought by French intelligence from the spy Hans-Thilo Schmidt and passed to Warsaw in December 1932. By November 1938, the Poles had built six electromechanical devices called Bomba (bomby, plural) to automate the search for daily settings.

When Germany changed the indicator procedure in September 1938 and added two new rotors in December 1938 (which multiplied the work beyond what the Poles could handle) the Poles shared their work with Britain and France in a secret meeting at Pyry near Warsaw in late 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 depended on the doubled message key, a procedural weakness the Germans could drop at any time (and largely did in May 1940). Turing needed a method that would work even against correctly used Enigma.

He built it on the crib: a guessed fragment of plaintext. Cribs were an old codebreaking tool, and the Poles had used them too; Turing’s step was to turn them into a systematic, machine-driven search. Enigma operators were military personnel who followed predictable habits: weather reports began with WETTER (weather), and standard formats and 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 self-defeating property: because of its reflector, no letter could ever encrypt to itself. This let the codebreakers slide a crib along the ciphertext and discard every alignment in which a crib letter sat on top of the identical cipher letter. For each remaining alignment, Turing turned the crib into a “menu” of letter pairs linked by rotor offsets. The Bombe, his electromechanical device, then stepped through all 17,576 rotor positions for a given wheel order and, at each one, tested a hypothesis about the plugboard: any position where the hypothesis led to a contradiction was rejected, and the few survivors (“stops”) went to 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 ...
            ↓
  Place crib: reject any alignment where a crib
  letter matches its cipher letter (no A→A in Enigma)
            ↓
  Build menu: letter pairs linked by rotor offsets
            ↓
  ┌──────────────────────────────────┐
  │  Bombe: step through all 17,576  │  ← 36 scramblers (108 drums),
  │  rotor positions; reject any     │     several menus / wheel
  │  where the plugboard guess       │     orders at once
  │  contradicts itself              │
  └─────────────────┬────────────────┘
                    ↓
            "Stops" → hand-tested on an Enigma replica

Gordon Welchman added the diagonal board, extra wiring that exploited the symmetry of the plugboard (if A is swapped with B, B is swapped with A). It let each wrong hypothesis produce contradictions much faster, so the Bombe needed shorter cribs and gave far fewer false stops.

Turing joined the Government Code and Cypher School full-time on September 4, 1939, and visited the exiled Polish team in France in January 1940. The first Bombe, “Victory,” went into Hut 1 at Bletchley in March 1940 (the 14th or 18th; the records differ). Welchman devised the diagonal board around the end of 1939, and the first Bombe fitted with it, “Agnus,” started on August 8, 1940; it became the standard type. Each was about 2.1 metres long and 2 metres high, weighed a ton, and simulated 36 Enigmas with 108 rotating drums. The British Tabulating Machine Company, Britain’s Hollerith licensee at Letchworth, built them: the first took six weeks, and later about one a week left the factory, some 210 in all by the end of the war, at Bletchley and its outstations. For the four-rotor naval Enigma introduced in 1942, the US Navy and NCR set up a secret laboratory in Dayton, Ohio, under the engineer Joseph Desch, which built about 120 faster four-rotor Bombes from May 1943; one survives at the NSA’s museum. A working replica of the British Bombe, rebuilt by a Computer Conservation Society team under John Harper between 1994 and 2007, is demonstrated at The National Museum of Computing on the Bletchley Park estate. The naval Enigma also required the physical capture of Enigma materials from German vessels, as in the Lofoten raid of March 4, 1941 and the seizure of U-110 on May 9, 1941.

The intelligence product, codenamed Ultra, gave the Allied high command a running view of German operational planning. Harry Hinsley, Bletchley veteran and official historian of British wartime intelligence, judged in 1993 that it shortened the war “by not less than two years and probably by four years.” The whole operation stayed secret until 1974, and Turing’s part in it was not told in detail until Andrew Hodges’s biography of 1983. The secret leaked in stages: David Kahn’s The Codebreakers (1967) named Bletchley Park but did not reveal that it had broken Enigma, the Sunday Times reported Enigma decryption at Bletchley in December 1967, Brian Randell’s 1972 paper described Colossus, and the French officer Gustave Bertrand’s 1973 book told the Polish story. Frederick Winterbotham’s The Ultra Secret (1974) finally put the whole operation in print.

Dead End: The ACE Computer

The war ended in 1945. Turing, now employed by the National Physical Laboratory, completed in December 1945 a 48-page design, “Proposed Electronic Calculator,” for a stored-program electronic computer he called the Automatic Computing Engine (ACE). It drew on his theoretical work from 1936 and on what he had learned about electronics during the war. It specified mercury delay-line memory and a speed that would have made it one of the fastest computers of its day. The project was approved in May 1946.

The NPL did not build it.

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. As deputy director of the Computing Machine Laboratory, he worked on the machine’s programming and wrote the programmer’s manual for its commercial version, the Ferranti Mark 1.

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 answered nine objections in turn, among them the theological objection, the mathematical objection drawn from Gödel’s theorem, Lady Lovelace’s objection that machines only do what they are told, and the argument from consciousness, the line of attack that John Searle’s Chinese Room (1980) later sharpened. It also made a cautious prediction: in about fifty years, computers with a storage capacity of about 10⁹ would “play the imitation game so well that an average interrogator will not have more than 70 per cent. chance of making the right identification after five minutes of questioning.”

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 20 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

In August 1952, Turing published a paper in a completely different field: “The Chemical Basis of Morphogenesis.” It combined partial differential equations, chemistry, and biology to address an old question of embryology: 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: chemical substances (he called them “morphogens”) reacting with each other and diffusing through tissue at different rates. In the form later made popular, one substance activates its own production while a faster-spreading one inhibits 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 became a foundation of mathematical biology, and “Turing-type” mechanisms have been demonstrated experimentally in systems from the stripes of tropical fish to the spacing of digits in the mouse limb (2012).

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; he had died the day before. 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 apple itself was never tested for poison. His mother, Sara Turing, always rejected suicide and believed in an accident with his home chemistry. Her biography Alan M. Turing (1959), begun in 1956, was for more than twenty years the only book about him; it left out his homosexuality and the trial, and first printed his 1951 radio talk “Intelligent Machinery, A Heretical Theory.” Andrew Hodges’s Alan Turing: The Enigma (1983) replaced it.

The classified nature of his wartime work meant that his death passed without public acknowledgment of what had been lost. Bletchley Park’s Enigma work stayed secret for another twenty years.

Rehabilitation

The ACM’s A.M. Turing Award, named for him, was first presented in 1966 and is often called the Nobel Prize of computing. Since 2014 it has carried a prize of one million dollars.

Britain’s formal acknowledgment took longer. Prime Minister Gordon Brown issued an official apology on September 10, 2009, saying that Turing “and so many thousands of other gay men who were convicted, as he was convicted, under homophobic laws, were treated terribly,” and ending: “we’re sorry, you deserved so much better.” Queen Elizabeth II granted a posthumous royal pardon in December 2013, more than sixty years after the conviction. The so-called Alan Turing law, a government amendment that became part of the Policing and Crime Act 2017 (royal assent January 31, 2017), extended posthumous pardons to men convicted under the abolished laws against consensual sex between men; a rival private member’s bill had been talked out in the Commons in October 2016.

Hugh Whitemore’s play Breaking the Code (1986), with Derek Jacobi as Turing, was filmed by the BBC in 1996; The Imitation Game (2014) won Graham Moore the Oscar for adapted screenplay while simplifying the Bombe into a machine that needed no cribs. Two operas followed: Anno Schreier’s Turing, premiered in Nuremberg on November 26, 2022, and Justine Chen’s The Life and Death(s) of Alan Turing, written for the American Lyric Theater in New York.

On June 23, 2021, his birthday, the Bank of England issued a £50 note with Turing’s portrait, chosen in 2019 from 989 nominated scientists. Its design carries his birth date in binary, Bombe drawings, lines from On Computable Numbers, the Pilot ACE, and his remark to The Times of June 11, 1949: “This is only a foretaste of what is to come, and only the shadow of what is going to be.”

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 stored-program architecture that his ACE design shared with von Neumann’s 1945 EDVAC report is traced in The Von Neumann Architecture. The programming language tradition he helped motivate is explored in The Evolution of Language.

📚 Sources

• Heinz Nixdorf MuseumsForum blog, “Alan Turings Computer” (8 May 2020)
• Heinz Nixdorf MuseumsForum blog, “Bomben gegen Enigma” (6 April 2017)
• Heinz Nixdorf MuseumsForum blog, “Enigma und Lochkarte” (13 March 2020)
• Heinz Nixdorf MuseumsForum blog, “Geheimnis Ultra” (13 February 2018)
• Heinz Nixdorf MuseumsForum blog, “Kinoheld Alan Turing” (28 July 2015)
• Heinz Nixdorf MuseumsForum blog, “Alan Turing in der Oper” (13 December 2022)
• Heinz Nixdorf MuseumsForum blog, “Sara Turing und ihr Buch” (19 November 2024)
• Heinz Nixdorf MuseumsForum blog, “Geldschein mit Computerpionier” (18 June 2021)
• Turing, Alan M.: “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, Series 2, Vol. 42 (1936–37)
• Turing, Alan M.: “Computing Machinery and Intelligence,” Mind, Vol. 59, No. 236 (1950)
• Turing, Alan M.: “Intelligent Machinery”, National Physical Laboratory report (1948), repr. in Copeland (ed.), The Essential Turing, source of the “isolated man”/“human community as a whole” passage
• Schmeh, Klaus: “Enigma’s Contemporary Witness: Gisbert Hasenjaeger,” Cryptologia, Vol. 33, No. 4 (2009), pp. 343–346
• Borchers, Detlef: “Intelligenz ist ein soziales Produkt: Alan Mathison Turing zum 100. Geburtstag”, heise online, 23.06.2012
• Hodges, Andrew: Alan Turing: The Enigma (1983, rev. ed. 2014), Princeton University Press
• Copeland, B. Jack (ed.): The Essential Turing (2004), Oxford University Press
• Welchman, Gordon: The Hut Six Story: Breaking the Enigma Codes (1982), McGraw-Hill
• Rejewski, Marian: “How Polish Mathematicians Broke the Enigma Cipher,” Annals of the History of Computing, Vol. 3, No. 3 (1981), pp. 213–234
• Turing, Alan M.: “The Chemical Basis of Morphogenesis,” Philosophical Transactions of the Royal Society B, Vol. 237, No. 641 (1952)
• Rob Janoff interview, Creative Bits, the Apple logo designer on the bite (scale, not Turing)
• Jack Copeland on Turing’s death, BBC News (2012), the case that the suicide verdict was not established
• Hodges, Andrew: “Turing, Alan Mathison (1912–1954)”, Oxford Dictionary of National Biography entry, on turing.org.uk: life dates, Hut 8, trial of March 31, 1952, hormone injections, death on June 7, 1954
• Sherborne School: transcripts of Turing’s school reports 1926–1931 (Old Shirburnian Society), Nowell Smith’s summer-term 1927 report
• Petzold, Charles: “Turing and the Halting Problem” (2007), on the later origin of the term “halting problem”
• Lucas, Salvador: “The origins of the halting problem”, Journal of Logical and Algebraic Methods in Programming 121 (2021)
• Marian Rejewski, Wikipedia: French-supplied key tables of 1932, bomby of November 1938, German changes of September and December 1938
• Bombe, Wikipedia: Victory and Agnus, menus, stepping through 17,576 positions, US Navy bombes
• The Bombe Rebuild Project: history of the rebuild, completion of the replica in 2007
• Hinsley, Harry: “The Influence of ULTRA in the Second World War” (lecture, Cambridge, October 19, 1993)
• Prime Minister’s apology to Alan Turing (September 10, 2009), full text
• Alan Turing law, Wikipedia: Policing and Crime Act 2017, royal assent January 31, 2017
• ACM: “ACM’s Turing Award Prize Raised to $1 Million” (November 13, 2014)
• Gisbert Hasenjaeger, Wikipedia: missed the no-fixed-point weakness; relay Turing machine of 1963
• Kondo, Shigeru and Miura, Takashi: “Reaction-Diffusion Model as a Framework for Understanding Biological Pattern Formation”, Science 329 (2010), pp. 1616–1620
• Sheth, Rushikesh et al.: “Hox Genes Regulate Digit Patterning by Controlling the Wavelength of a Turing-Type Mechanism”, Science 338 (2012), pp. 1476–1480
• Mental Floss: “Did Alan Turing Inspire the Apple Logo?”, Janoff’s 2009 denial and the Stephen Fry / Steve Jobs exchange