1. The Computer Was a Person

In spring 1936, Alan Turing, a twenty-three-year-old fellow of King's College, Cambridge, completed a paper about computable numbers. The London Mathematical Society received it on May 28. Its title connected those numbers to the Entscheidungsproblem, the decision problem associated with Hilbert.

A computable number, roughly speaking, is one whose digits can be generated by a finite, effective procedure to any requested precision. Pi is an example. The paper's question was not simply how to calculate more digits. It was what calculating by a procedure means.

The machine now bearing Turing's name first appears through a comparison with a person. In the paper's analysis, a “computer” is someone working on paper. The paper can be divided into squares. The person can inspect only a limited amount at once, distinguish finitely many symbols, and have finitely many relevant states of attention. Each elementary action changes a symbol, shifts attention, or changes the state governing the next action.

That vocabulary was ordinary in 1936. Observatories and table-making institutions employed human computers to carry out prescribed calculations. They had bodies, fatigue, understanding, and moments of inspiration. Turing's analysis did not claim that these exhausted a human being. It isolated the part of the work performed by following an explicit rule.

Remove the freedom to invent the next step. Separate a complicated act into small, local acts. Retain only what the current instructions and currently inspected symbol determine. The remaining idealization is the machine.

The tape need not be manufactured; its unbounded extent expresses the absence of an arbitrary storage limit in the mathematical model. At any finite stage, only finitely much is used. That distinction separates the abstract machine from every physical device subsequently built to approximate it.

Turing was not beginning with a blueprint for electronic hardware. He was making an informal activity precise enough that mathematics could prove a limit on it. The original paper preserves the movement from the person with paper to the formal machine.

To understand why that reduction mattered, go back to a question posed before anyone could purchase a digital computer.

2. An Ordinary Phrase

In 1928, Hilbert and Wilhelm Ackermann placed the decision problem near the centre of mathematical logic. Given an arbitrary first-order formula, could a uniform mechanical procedure determine in finitely many steps whether it was valid under every interpretation?

Validity is not the same as truth in one chosen mathematical structure. A logically valid formula holds under all interpretations of its nonlogical symbols. Nor does the question ask whether a sufficiently clever mathematician can settle one particular example. It asks for a single method covering the entire class.

A positive answer would require an algorithm. A negative answer required something harder to formulate: a proof that no algorithm could possibly work. Yet “mechanical procedure” remained an ordinary phrase. Until its scope was made exact, how could all possible procedures be ruled out?

There had been encouraging partial successes. Bernays investigated decision procedures for propositional logic in 1918. Heinrich Behmann treated restricted logical classes in 1921. Presburger's arithmetic was another island where a uniform method existed. Such results made the larger ambition serious, not foolish.

Gödel's 1930 completeness theorem supplied a related but incomplete guarantee. If a first-order sentence is logically valid, systematic enumeration of formal proofs will eventually find a proof of it. If it is not valid, that particular search may continue forever.

Thus logical completeness did not establish decidability. It ensured that valid sentences have proofs, not that one can always determine in advance which search will succeed. The difference between reaching an answer and waiting indefinitely became decisive.

In March 1935, King's elected Turing to a fellowship on the strength of work in probability. He had independently obtained a result already proved by Jarl Waldemar Lindeberg in 1922. The prior publication did not prevent the election. The fellowship provided three years of support, £300 annually with accommodation and meals.

That spring he attended Max Newman's lectures on the foundations of mathematics. Newman later recalled presenting the decision problem in terms of a process that could be carried out mechanically, perhaps explicitly by a machine.

The recollection is late; it cannot supply a recording of the classroom. But it identifies the intellectual step Turing took. He did not first seek one more clever decision method. He examined the word describing every method under consideration.

If a claim says “no mechanical method can do this,” the word “mechanical” must become something one can reason about. Otherwise impossibility remains an assertion with an undefined boundary.

3. The Tape

Imagine a tape divided into cells. Each cell holds a symbol from a finite alphabet or is blank. The machine inspects one cell at a time and occupies one of finitely many internal states.

Its current state and the symbol under inspection determine the next move. It may write or erase, move along the tape, and enter a new state. A finite table specifies all the instructions.

Modern textbook versions normalize the details in slightly different ways: whether staying in place is allowed, how a halt is represented, whether one or several tapes are used. Those variations can simulate one another. They do not alter the class of effectively computable functions.

Turing's first example alternates zero and one indefinitely, placing output digits on alternating squares. Its four states and tiny instruction table are intentionally simple. Greater complexity comes from more elaborate tables and longer computations, not from an unexplained flash of intelligence inside the box.

The decisive next move is to describe the table itself by symbols. Once a machine's instructions have a finite encoding, they can become another machine's input.

Turing showed how to construct a universal machine. It reads the encoded description of a machine and simulates its successive operations. A particular task need no longer require a new basic mechanism. Changing the description supplied to the universal machine changes the task.

This is a logical ancestor of programmable computing. It is not a claim that Turing alone invented the stored-program electronic computer, or that the universal machine was an engineering design ready for construction in 1936. Encoding instructions has its own prehistory, and practical computers required a further history of circuits, memory, organization, and engineering.

Universality also does not mean omnipotence. A universal machine can simulate any machine in the specified class. It cannot thereby compute functions outside that class. “Universal” quantifies over the model, not over every imaginable mathematical question.

The tape and table matter because they provide exact objects for a proof. Instruction tables can be listed; descriptions can be checked and manipulated; one machine can take another's description as input.

The earlier ordinary phrase now has a rigorous candidate meaning. Instead of gesturing toward all possible rule-following, a mathematician can speak about every finite table of this kind. The apparently modest reduction of a person to local steps makes a general impossibility argument possible.

4. Several Roads to the Same Boundary

Across the Atlantic, Alonzo Church had approached effective calculation through a different formalism. Working in Princeton with students including Stephen Kleene, he studied functions expressed through the lambda calculus, a symbolic system centred on abstraction and substitution.

In April 1936, Church published an undecidability result and proposed identifying effective calculability with the formally definable class he had investigated. A short paper later that year applied the result directly to the Hilbert–Ackermann decision problem.

An offprint reached Cambridge just as Newman had read Turing's manuscript. Newman wrote to Church about the painful coincidence for the young mathematician, whose independently developed definition used machines rather than lambda expressions. He also stressed the value of Turing's approach and encouraged a visit to Princeton.

It was Turing's second encounter with a predecessor, after Lindeberg. He did not discard the paper. The route to the result mattered because it offered a different account of what the formal class represented.

Turing acknowledged Church's work and argued that the definitions agreed. His appendix and a further 1937 paper established the connection with lambda-definability. Emil Post independently described a related model in which a worker follows fixed instructions while marking, erasing, and moving among boxes.

Machine computation, lambda-definability, and recursive-function methods converged on the same class. The agreement among formalisms is a mathematical result. The further assertion that this class captures every effective method in the ordinary sense is the Church–Turing thesis.

The thesis is not an ordinary theorem equating two already formalized notions, because one side refers to an informal concept. It is also not an arbitrary naming convention. Independent models agree, and Turing supplied a detailed analysis of finite, explicit human calculation.

This thesis concerns effective computation. It does not by itself claim that every physical process, every human thought, or every possible intelligence is adequately described by a standard Turing machine. Broader versions require further assumptions.

Church's 1937 review praised the directness of Turing's connection to effective calculability and used the name “Turing machine.” A person with paper, pencil, and explicit instructions could themselves count as one.

The reversal is striking without being mystical. Turing had abstracted a machine from a human activity. Church could then place that activity within the machine model. The model had not swallowed the whole person; it had identified the procedural part with enough precision to make it available for mathematics.

5. Do the Opposite

The modern halting problem gives the cleanest introduction to the obstruction.

Suppose a decision procedure H always determines whether a program halts on a supplied input. Construct another program D. Given a program description p, D asks H whether p halts when run on its own description. If H says yes, D runs forever. If H says no, D halts immediately.

Now run D on its own description.

If H predicts that D halts, D deliberately does not. If H predicts that it runs forever, D halts. Either answer contradicts the supposed correctness of H. Therefore no total, always-correct procedure of the assumed kind exists.

The construction does not require a mysterious machine that knows itself psychologically. It requires only encoded instructions and the possibility of treating an instruction description as data. Self-input is a syntactic operation.

Turing's 1936 presentation used somewhat different problems and terminology, particularly whether a machine would keep producing further output digits. A machine can continue moving without producing more digits, so that original question should not simply be renamed “halting” without qualification. Modern textbook arguments reorganize the result into related undecidable problems.

The diagonal pattern has appeared twice already in this series. Cantor changed entries along a proposed enumeration to produce an omitted sequence. Gödel encoded formal expressions arithmetically to construct a sentence tied to its own provability. Here a program receives its own code and reverses a predicted outcome.

The mathematical objects and hypotheses differ. The family resemblance lies in encoding, self-application, and a diagonal change designed to defeat an alleged exhaustive procedure.

Turing then connected an undecidable machine question to first-order validity. If a general decision procedure for logic existed, it would resolve a problem his argument showed could not be decided. Therefore the desired logical procedure did not exist.

This does not contradict Gödel's completeness theorem for first-order logic. Every valid sentence can still have a proof, while no algorithm always distinguishes valid sentences from invalid ones. Nor is it identical to the incompleteness theorem for effectively axiomatized arithmetic.

The distinctions are worth retaining. Semantic validity, formal provability, completeness of a theory, and termination of an algorithm are connected without being interchangeable. Hilbert's particular decision problem received a negative answer because Church and Turing made those connections precise.

6. Princeton and Bletchley

Turing went to Princeton in autumn 1936 to work with Church. His paper was read to the London Mathematical Society that November. At Princeton, the Institute for Advanced Study still occupied university space; Einstein, von Neumann, and Weyl worked nearby. Mathematical ideas travelled through institutions now also receiving refugees.

Turing completed his doctorate in 1938, on systems of logic based on ordinals. Von Neumann offered him an assistantship. He returned to Cambridge instead.

In 1939 he sought £40 from the Royal Society for a geared machine to investigate the Riemann zeta function. Riemann's hypothesis concerns its nontrivial zeros, asserting that they lie on the line with real part one half. Turing hoped to search for an exception. War interrupted construction, and no components are known to survive.

On September 4, 1939, the day after Britain declared war, he reported to the Government Code and Cypher School at Bletchley Park. He became central to the attack on naval Enigma.

This was collaborative work from the outset. Marian Rejewski, Jerzy Różycki, and Henryk Zygalski had made fundamental Polish breakthroughs during the 1930s. In July 1939 the Poles shared crucial methods and equipment knowledge with British and French colleagues. Turing met Polish cryptanalysts in France in January 1940.

The British bombe grew from Turing's logical design, Gordon Welchman's essential improvement, engineering work, and the labour of operators and analysts. Turing's design work had begun before that January meeting; the visit should not be made the single origin of the machine. Polish achievements were foundational without making the British bombe merely a copied Polish device.

In Hut 8, Turing developed Banburismus, a statistical method for evaluating evidence about naval Enigma settings. Long perforated sheets, printed in Banbury, could be overlaid to inspect coincidences between messages. Logarithmic weights expressed how strongly the evidence favoured an hypothesis, with units called bans and decibans.

Joan Clarke became an expert practitioner. Despite first-class results in Cambridge's mathematical examinations, she could not then receive the degree awarded to male students. At Bletchley she initially encountered clerical classification and low pay; promotion through a “linguist” category produced the absurdity of a language post without a corresponding foreign language. She later became Hut 8's deputy head. GCHQ's account confirms her substantive cryptanalytic role.

Staffing could be as decisive as mathematical invention. On October 21, 1941, Turing, Welchman, Hugh Alexander, and Stuart Milner-Barry appealed directly to Churchill. They needed trained typists, clerks, and naval personnel to operate machines. Shortages left experts doing routine trials and curtailed shifts.

Milner-Barry delivered the letter to Downing Street. Churchill ordered immediate priority for their requirements. The surviving letter and response show an intelligence system depending on apparently ordinary work.

Another cipher system led to another machine. Bill Tutte's analysis of Lorenz traffic and Tommy Flowers's engineering were crucial to Colossus. Max Newman directed the machine-based section. The lecturer whose words had helped prompt Turing's abstract model now organized an entirely different wartime machine operation.

By early 1945, Bletchley and its outstations employed nearly nine thousand people, about three quarters women. Secrecy hid much of their work for decades. Turing's mathematical reputation nevertheless survived independently: ACM named its major award after him in 1966, before the wartime story was widely public.

7. 1950, 1952

After the war, Turing joined the National Physical Laboratory and produced a detailed electronic-computer proposal, the ACE report, presented in 1946. The full machine was not built during his time there. Following leave in Cambridge, he moved to Manchester in 1948, where Frederic Williams, Tom Kilburn, and colleagues had developed working hardware.

No single name can carry the invention of the electronic computer. Turing's contribution is substantial enough without requiring that fiction.

At Manchester he returned to the zeta function. His calculations in 1950, reported in 1953, helped extend verification of the Riemann hypothesis through the first 1,104 nontrivial zeros. They were not the first checking of all those zeros from scratch. His hope, expressed with characteristic contrariness, was to find a counterexample.

The work depended on the machine remaining operational through an unusually long stretch, from mid-afternoon until the next morning. Abstract computation had met unreliable hardware. Andrew Booker's mathematical account explains the significance of Turing's zero-counting method beyond the raw total.

In October 1950, Mind published “Computing Machinery and Intelligence.” Turing began with the question whether machines can think, then proposed replacing a battle over definitions with an imitation game conducted through written exchanges.

The original setup involves an interrogator distinguishing a man from a woman, before a machine is substituted into the arrangement. Later versions simplify or reinterpret that setup. His prediction that an average interrogator might achieve no more than seventy percent correct identification after five minutes was a prediction, not a universal pass mark declaring machines intelligent if they fooled thirty percent of people.

Turing also addressed a mathematical objection: machines have demonstrable limitations, therefore human minds must transcend them. His response separated the established premise from the unsupported inference. Particular machines have limits; no proof had shown that human intelligence is free of analogous limits.

In January 1952, a burglary at his Wilmslow home brought police inquiries into his relationship with Arnold Murray. Turing did not conceal their sexual relationship. Both men were prosecuted under the law criminalizing “gross indecency” between men.

A letter to Norman Routledge, written around February, combined apprehension with bitter logical humour. Turing imagined an invalid syllogism passing from his belief in thinking machines and his relationships with men to the conclusion that machines could not think. His sexual life had no bearing on that mathematical or philosophical question. He feared that public judgment would pretend otherwise.

On March 31 he pleaded guilty. Alexander, a fellow signatory of the wartime appeal, testified to his value to the country. The court imposed twelve months' probation conditional on hormonal treatment; imprisonment was the alternative. Treatment intended to suppress sexual desire continued for a year and caused physical changes.

The conviction barred him from further classified cryptanalytic work. He retained his Manchester position. Scientific work did not cease: in August 1952 the Royal Society published “The Chemical Basis of Morphogenesis.”

There he showed how interacting and diffusing chemical substances could destabilize a nearly uniform state and generate spatial patterns. Diffusion need not always smooth differences away. Under specified conditions, reaction and diffusion together can amplify them. This became a foundational mechanism in mathematical biology, alongside his continuing interest in leaf arrangements and growth.

The prosecution belongs in the life without reducing every subsequent paper to its consequence. He remained an active mathematician subjected to an unjust criminal and medical regime.

8. The Apple That Was Not Tested

A popular story makes Apple's bitten-apple logo a memorial to Turing. Its designer, Rob Janoff, has rejected that account: the bite helped distinguish an apple from a cherry. Resemblance and poignancy are not documentation of an intention.

The real apple appears in the record of Turing's death. On June 8, 1954, his housekeeper found him dead at home. He was forty-one. A partly eaten apple lay nearby. The post-mortem examination identified cyanide poisoning; the inquest concluded that he had died by suicide on June 7. The apple was not chemically tested.

His mother, Sara, rejected the suicide verdict and believed careless handling of laboratory chemicals responsible. She published a biography in 1959 and subsequently gave letters and other papers to King's. These became part of the archive through which later biographers encountered him. King's College displays the relevant records, including the inquest material, the post-mortem report, and her evidence.

Andrew Hodges's 1983 biography brought the mathematics, cryptanalysis, sexuality, prosecution, and death together on an unprecedented scale. Hodges regarded suicide as the most likely explanation. Jack Copeland has argued that the evidence does not exclude an accidental death connected with chemical experiments.

The positions are not interchangeable with established facts. Cyanide poisoning and the contemporary suicide verdict are documented. Turing's final intention is not directly recoverable; the untested apple cannot establish a precise route of exposure. The formal verdict remains suicide, while later historians have disputed how conclusively the surviving evidence determines intention.

An injustice does not need an embellished death story to remain an injustice. Neither certainty about suicide nor certainty about accident is necessary to condemn his prosecution and compulsory treatment.

In 2009, a petition initiated by John Graham-Cumming gathered more than thirty thousand signatures calling for an apology. Gordon Brown issued one on September 10. A posthumous royal pardon followed in December 2013. Legislation in 2017 extended pardons, subject to its conditions, to many others convicted under abolished same-sex offences. Turing's fame should illuminate those other lives, not imply that only exceptional service made persecution wrong.

On June 23, 2021, his birthday, the Bank of England issued the new £50 note bearing his portrait. The bank's announcement identifies both his achievements and his appalling treatment.

In the 1936 paper, the computer was a person with squared paper. The definition extracted one activity: proceeding by finite, explicit rules. It did not purport to include fatigue, affection, originality, or everything else in the person's life.

That extraction allowed mathematics to hand work to machines and to establish limits on what those machines could do. Before proving that something cannot be done mechanically, Turing made “doing it mechanically” precise.

While he developed that account in Cambridge, a group in Paris was creating mathematics under the name of a person who did not exist.