Alan Turing was a young Fellow of King’s College Cambridge when he submitted a paper to the Proceedings of the London Mathematical Society in the spring of 1936 describing a machine made only of paper. The machine had an infinite tape divided into squares, a head that could read one square at a time, and a small table of instructions telling it what to do next. It could not be built. It did not need to be. Turing had invented it to answer a question posed by the German mathematician David Hilbert about whether a mechanical procedure could decide, for any mathematical statement, if the statement was provable.
The paper was called On Computable Numbers, with an Application to the Entscheidungsproblem. It ran 36 pages. It settled Hilbert’s question with a firm no, and in the process it defined what a computer is.
The question that had nothing to do with computers
Hilbert’s decision problem — the Entscheidungsproblem — had been sitting in front of mathematicians since 1928. The question sounded innocent: is there a definite method, a step-by-step procedure, that can take any statement in formal logic and determine whether it follows from the axioms? If yes, mathematics could in principle be mechanised. If no, some truths would forever require human insight.
To answer no, Turing needed to define what a “definite method” even was. Nobody had done this rigorously. The word “algorithm” existed, but only as an informal notion — recipes for long division, procedures for finding square roots. Turing had to formalise the idea of a procedure itself before he could prove that some problems escaped every possible procedure.
His trick was to imagine a human computer. In 1936, the word computer meant a person, usually a woman, whose job was to work through calculations with pencil and paper. Turing watched what such a person actually did: they looked at a symbol, consulted a rule in their head, wrote a new symbol, and moved their attention to a different spot on the page. That was it. He stripped the human away and left the mechanism.
What the machine actually was
The machine Turing described has four parts. A tape, unbounded in both directions, divided into squares. A head that sits over one square at a time and can read what is written there or write something new. A finite set of internal states — think of them as moods the machine can be in. And a table of rules: if you are in state 7 and you see a 1, erase it, write a 0, move one square left, and switch to state 12.
That is the whole apparatus. No memory beyond the tape. No arithmetic circuits. No screen. And yet Turing proved that with the right table of rules, this device could carry out any calculation a human being could perform by rote. Multiplication, division, solving equations, checking proofs — all of it reducible to shuffling symbols on a strip of paper.
Then he went further. He described a special version he called a universal machine, one whose table of rules could read the description of any other Turing machine off the tape and then behave exactly like it. As Robert Soare of the University of Chicago has put it, the universal machine took as inputs the program for another machine and an arbitrary input, and processed that input just as the given program would have done. One device, running different tapes, could be every device.
That is the idea sitting inside every phone, laptop, and server on the planet — hardware that stays fixed while software changes what it does.
The proof by contradiction that broke Hilbert’s dream
With the machine defined, Turing turned it on itself. He asked whether there could be a Turing machine that, given the description of any other Turing machine and its input, could decide in advance whether that machine would eventually halt or run forever. This is the halting problem, and the answer is no. Turing showed that assuming such a decider existed leads to a contradiction — you can always construct a machine that does the opposite of what the decider predicts.
From the impossibility of solving the halting problem, Turing derived the impossibility of a general decision procedure for logic. Hilbert’s question was answered by a machine that could not be built, running a program that would never end. It remains one of the founding results of computer science, and the halting problem is still taught as a cornerstone of undecidability in university courses today, including Northwestern’s introductory theory of computation, which walks students through Turing machines, universal computation, the Church-Turing thesis and Rice’s theorem.
Alonzo Church and the American parallel
Turing was not working alone on the question, though he did not know it. At Princeton, the mathematician Alonzo Church had reached the same conclusion a few months earlier using a different formalism called lambda calculus. An offprint of Church’s paper reached Cambridge that spring, and Turing’s mentor Max Newman — the Cambridge topologist whose 1935 lectures on the foundations of mathematics had drawn Turing to the decision problem in the first place — wrote to Church at the end of May to sort out the priority.
The two approaches turned out to be equivalent — anything expressible in Church’s lambda calculus could be computed by a Turing machine and vice versa. This equivalence became known as the Church-Turing thesis, and it is the reason the field of computability treats these two very different-looking systems as descriptions of the same underlying phenomenon. Turing went to Princeton in September 1936 to work under Church directly, completing his PhD there in 1938. Decades later, Robert Soare — himself a Princeton alumnus — would have Church as one of his undergraduate professors in the early 1960s, one link removed from the man who supervised Turing’s doctorate.
From paper machine to Bletchley Park
The war intervened. In September 1939, Turing arrived at Bletchley Park, the British Government Code and Cypher School’s country house north of London, and set to work on the Enigma cipher used by the German military. The machine he helped design there — the Bombe — was electromechanical rather than digital, but the habit of thinking about computation as a formal process, developed in the 1936 paper, shaped everything about how the Bletchley cryptanalysts approached the problem.
The Bombe eventually helped break German naval Enigma traffic, shortening the Atlantic campaign by an amount historians still argue about but always measure in years and lives.
Hollywood came for Turing in the 2014 film The Imitation Game, which compressed the life into a couple of dramatic hours. The 1936 paper barely appears in it. The war does.
Von Neumann, the EDVAC, and the wiring of the abstract
After the war, Turing returned to the question of building the universal machine for real. He designed the Automatic Computing Engine at the National Physical Laboratory in Teddington, a stored-program computer whose architecture drew directly on the 1936 paper. Meanwhile in the United States, John von Neumann was drafting the design that became known as the von Neumann architecture — a processor that fetches instructions and data from the same memory, executes them one at a time, and can be reprogrammed by changing the contents of memory rather than the wiring.
Von Neumann had read Turing’s paper. He said as much to colleagues. As Soare has noted, Turing’s universal machine became very useful a few years later when Turing used it in the design of an electronic computer in the United Kingdom after World War II, and John von Neumann used it in the United States for the same purpose. The chip inside a modern phone still works on that principle: instructions and data share memory, the processor reads them one at a time, and what makes the phone a camera or a calculator is which tape you feed it.
Why the paper feels like art
Soare, who has argued that Turing’s 1936 paper deserves to be read the way one reads Michelangelo’s David, points out that Michelangelo brought out the human form in his statues and the Sistine ceiling, and Turing invented a system that simulates how a human being computes, and then demonstrated that his creation did capture human computing. The machine on the tape is a portrait of a person doing arithmetic, stripped down to the bone.
That framing sits inside a wider body of work in mathematical logic and set theory, which continues to explore precise notions of proof, computability, and the hierarchy of infinities that Turing’s contemporaries — Gödel, Church, Kleene — helped set in place. The 1936 paper is where the abstract idea of computation crossed over from philosophy into engineering.
The end, and what came after
In 1952, Turing was prosecuted under British laws criminalising homosexual acts. He accepted chemical castration in lieu of prison. He died in June 1954, two weeks shy of his 42nd birthday, from potassium cyanide poisoning — ostensibly by his own hand, though the circumstances remain debated. On Christmas Eve 2013, nearly six decades later, Queen Elizabeth II issued a royal pardon.
What the paper set in motion did not stop. The Turing test, proposed in his 1950 paper Computing Machinery and Intelligence, still frames arguments about artificial intelligence three-quarters of a century later. The halting problem still guards the border between what software can and cannot decide about other software. Every compiler, every operating system kernel, every interpreter running JavaScript in a browser is, formally, a universal Turing machine reading a tape. The tape is longer now. The head moves faster. The rules are the same.
Somewhere in the Cambridge University Library sits a bound volume of the Proceedings of the London Mathematical Society, Series 2, Volume 42, published in 1937 — the volume that carried the 36 pages. The paper is available online now, freely, in the form of digital text stored on machines whose deepest logical structure it described before those machines existed. A tape, a head, a table of rules, and a young mathematician trying to answer a question about proofs.
