Hand someone a long strip of paper divided into squares, a pencil, and a list of instructions so narrow that following them requires no thought at all. Look at the square in front of you. Depending on what you find there, rub it out and write something else, then move one square left or right. Nothing explains what the marks mean. No room for judgement or insight. There is only the list.
That person is a Turing machine — given an endless supply of paper, and some way of keeping track of which line of the list they are currently on. Those two provisions matter enormously, and we will come back to both. What should be said at once is that this is not a description of a computer. It describes a clerk.
Alan Turing built it in 1936 to settle an argument in mathematical logic, and the answer he obtained was negative. He was not designing a machine anyone should build. He was drawing a border, and proving that beyond it lay questions no procedure of any kind could ever settle. That the border happened to define the shape of computing for the next ninety years was, in a sense, a side effect — though nearly every popular retelling has the story pointing the other way.
What a Turing Machine Actually Is
The strangeness of Turing’s idea is that he made his machine as stupid as he possibly could, on purpose. If you want to prove that no possible method can solve some problem, you must first agree on what counts as a method — and any definition you offer can be attacked for being too narrow. Someone will always object that a cleverer procedure might succeed.
Turing closed that escape route by going in the opposite direction from cleverness. He looked at what a person actually does when calculating with pencil and paper, broke it into the smallest steps he could find, and argued that nothing had been lost in the reduction. If his ridiculous clerk can do everything a careful mathematician can do, then showing the clerk cannot solve a problem shows nobody can.
Watching a Turing Machine Run
Abstraction goes down more easily once you have seen the thing move, so here is a complete machine. Its job is to decide whether a row of tally marks contains an even or an odd number of them.
This sounds trivial and is not, because it requires something the strip of paper cannot supply. The machine has to remember. Looking at any single mark tells you nothing about whether you have seen an even or odd number so far, and the machine can see only one square at a time. What it needs is an internal setting it can flip — and that setting is what Turing called a state.
So give the clerk two states, named even and odd, and four instructions. In state even, on a tally mark: step right and switch to odd. In state odd, on a tally mark: step right and switch to even. In state even, on a blank: write E and stop. In state odd, on a blank: write O and stop. Start in state even, since no marks have been seen yet.
Now run it on three marks. The bracket shows where the head is looking, and the word on the left is the state it is in at that moment.
even → [1] 1 1 _
odd → 1 [1] 1 _
even → 1 1 [1] _
odd → 1 1 1 [_]
stop → 1 1 1 O
Three is odd, and the machine has said so. Look closely at what happened in the first three lines, because it is the whole trick. The head saw the same thing every time — a tally mark, indistinguishable from the others. Yet the machine did something different on each encounter, because it was in a different state. The tape holds the data; the state holds what the machine knows about the data so far. That is memory, built out of nothing but a label the clerk keeps flipping.
Notice, too, that the machine has no concept of evenness. It shuffles symbols according to a table, and we supply the meaning by agreeing to read O as a verdict. This mindlessness is exactly what makes the device useful for proving things: there is nowhere for hidden intelligence to hide.
From here the ascent is steep but unbroken. Add a few more states and the machine compares two numbers. Add more, and it multiplies, sorts, searches. Turing’s paper makes a claim that should sound implausible at first: with enough states and enough tape, this same absurd apparatus can carry out any calculation that any computer, present or future, can carry out. Your laptop is doing nothing the clerk could not do, given a long enough strip of paper and an unreasonable amount of time.
The Question That Started It: Hilbert’s Decision Problem
In the spring of 1935, Turing was a twenty-two-year-old fellow of King’s College sitting in Max Newman’s Cambridge lectures on the foundations of mathematics, where he met a question David Hilbert had posed seven years earlier.
Hilbert wanted mathematics placed beyond doubt, resting on foundations that were consistent, complete, and mechanically checkable. In 1928, in a textbook written with Wilhelm Ackermann, he posed the Entscheidungsproblem — the decision problem. Is there a definite procedure that, given any statement of formal logic, determines whether it follows from the axioms? A crank you could turn, in other words, that would grind out mathematical truth without anyone needing to be brilliant. Hilbert expected the answer to be yes, and said so without qualification: in a 1930 radio address he declared that in mathematics there is no ignorabimus, no question that must remain forever unanswered.
Within a year the ground shifted. In 1931 Kurt Gödel proved that any consistent formal system rich enough to express arithmetic contains true statements it cannot prove. Completeness was gone. But the decision problem survived, because it asked something subtly different — not whether every truth is provable, but whether provability itself could be settled by rote.
Answering that required a precise definition of what “by rote” means, and here the story usually stumbles, because the obvious word was already taken. In the 1930s a computer was a person. Observatories and insurance offices employed rooms of them, mostly women, working through long calculations by hand according to fixed instructions. Turing’s imaginary clerk was drawn from life. Mechanical computers existed too — Leibniz built a stepped reckoner in the seventeenth century, Charles Babbage designed his unfinished Analytical Engine in the 1830s — but those mechanical computers were built to perform particular calculations faster. None offered a theory of what calculation is.
1936: How the Turing Machine Answered Hilbert
Turing’s paper, “On Computable Numbers, with an Application to the Entscheidungsproblem,” reached the London Mathematical Society on 28 May 1936. He did not call his construction a Turing machine. He called it an a-machine, for automatic machine.
Then came the move that changed everything. A machine is entirely specified by its little table of rules — and a table of rules can be written out as a row of symbols, which is precisely what a tape holds. So Turing built a machine that reads the description of any other machine and then behaves exactly as that machine would. He called it the universal machine.
Pause here, because this is the foundation of every device in your house. Hardware and software separate. You do not need a different machine for each task; you need one machine and a different description on its tape. The distinction between a program and the thing running it, now too obvious to state, was born as a step in a logic paper.
With the universal machine in hand, Turing turned the argument on itself. The manoeuvre is easier to feel in human terms first. Imagine someone who claims to be able to read a full description of you and predict what you will do next. You can defeat that claim without knowing anything about how the prediction works: resolve to do the opposite of whatever is predicted. The predictor does not fail because it is badly built. It fails because you can turn its own answer against it, and no amount of improvement will help.
Turing’s version is the same shape, made precise. Suppose a machine could inspect any description and determine in advance whether that machine would run forever or eventually stop. Build a new machine out of the inspector, rigged to do the opposite of whatever verdict the inspector reaches, and hand it its own description. If the inspector says it runs forever, it stops; if it says it stops, it runs forever. The contradiction is immediate, and the technique — assume a complete list, then construct something that cannot be on it — is Georg Cantor’s diagonal argument of 1891, turned against procedures rather than numbers. No such inspector can exist.
One step remains, and it is the one popular accounts skip, though it is what actually answers Hilbert. Turing had shown that a question about machines is unanswerable by any machine — but Hilbert had asked about formal statements, not about tape and pencils. Turing built the bridge by encoding machine behaviour into logic. For any given machine, he showed how to write a first-order logical formula that is provable precisely when that machine does the thing in question. A decision procedure for logic would therefore hand you, free of charge, a decision procedure for the machine question, which has just been proved impossible. The Entscheidungsproblem inherits the impossibility. Hilbert’s crank was not merely undiscovered; it could not exist. The Stanford Encyclopedia of Philosophy’s treatment of Turing machines sets out the formal machinery for readers who want it.
Turing was neither first nor alone. In April 1936, while his paper was still unfinished, Alonzo Church at Princeton published a solution to the same problem using an entirely different formalism, the lambda calculus. Turing had been scooped by weeks. Newman helped argue that the work was independent and worth publishing anyway, and Turing added an appendix showing that his notion of computability and Church’s pick out the same functions. That same year Emil Post, in a three-page note, independently described a worker moving through a sequence of boxes, marking and erasing according to fixed directions — so close to Turing’s clerk that the two are now taught as one idea. The difference was conviction rather than content: Turing argued that his analysis captured all effective calculation, while Post offered his as a working hypothesis still needing continual verification. Three men, working separately with tools that look nothing alike, had drawn the same line in the same place. Turing sailed for Princeton that autumn and finished a doctorate under Church in 1938.
What the Legend Gets Wrong
Turing never wrote the words “Turing machine.” Church coined the term in a review of Turing’s paper published in the Journal of Symbolic Logic in 1937. The most famous object in computer science was named by the man who had just beaten its inventor to publication.
The halting problem is likewise attributed to Turing as casually as gravity is attributed to Newton. He did prove an undecidability result of that shape, but framed it differently — in terms of whether a machine is what he called circle-free, meaning it goes on producing output indefinitely. The version everyone now learns, and the phrase itself, arrive later: Stephen Kleene stated something very close to it in 1952, and the words first appear in print in Martin Davis’s Computability and Unsolvability in 1958.
The largest misconception concerns purpose. The 1936 paper contains no suggestion that anyone should build one of these things, and the tape is infinite, which is exactly what no physical object can be. A Turing machine is not an impractical computer; it is a mathematical instrument, useful for the same reason a frictionless plane is useful in mechanics. This matters for the war years too. Turing’s work at Bletchley Park was real and enormous, but the Bombe he helped design was an electromechanical device for searching Enigma settings, not a general-purpose computer, and Colossus — the machine that genuinely deserves the name programmable electronic computer — was built by the engineer Tommy Flowers for a different problem. Turing did later design a real computing machine, the Automatic Computing Engine, in a 1945 report for the National Physical Laboratory. That is where he was doing engineering. The 1936 paper is not.
Photo: GabrielF via Wikimedia Commons — CC BY-SA 3.0. Cropped and straightened.
And the impossibility proof is not a museum piece. You meet its consequences regularly: when a program locks up, and your operating system offers only the limp diagnosis that it is not responding, that vagueness is not laziness on the part of the engineers. No general method exists to look at a program and decide whether it will finish, so the system waits and guesses like everybody else. A result known as Rice’s theorem, established in the early 1950s, widens this dramatically — essentially any interesting question about what a program will do, as opposed to how it is written, is undecidable in general. No compiler will ever reliably certify that your code contains no infinite loops, and no antivirus can be perfect in principle. Software engineering lives inside Turing’s border, and its tools are negotiated retreats from a proven impossibility.
The frontier still moves, too. The busy beaver problem, introduced by Tibor Radó in 1962, asks how long the longest-running machine with a given number of states can run before halting; the answer grows faster than any computable function. For five-state machines, the value was conjectured in 1989 and settled only in July 2024, when a distributed collaboration of amateurs and mathematicians proved it to be 47,176,870 and verified the whole proof inside the Coq proof assistant. Anyone curious can run a Turing machine simulator in a browser and watch a head crawl back and forth, which is still the fastest way to feel why these questions are hard rather than merely be told so. Readers who want the mathematical lineage behind them will find more in our mathematics archive as an example.
The Border and the Map
There is a temptation to treat 1936 as the year the computer was invented in theory. It is a tidier story than what happened, and it points the achievement in exactly the wrong direction.
Turing was not trying to expand what machines could do. He was trying to establish, with finality, what nothing could do — and the imaginary clerk he built for that demolition turned out to be a more precise description of computation than anything the engineers would produce for another decade. The universal machine was a step in a proof by contradiction. It became the organising idea of an industry.
Turing did not live to see much of it. He died in June 1954, at forty-one, two years after a criminal conviction for homosexuality and the hormone treatment imposed as its condition. The inquest recorded suicide, a verdict some later scholars have questioned. The British government apologised in 2009 and granted a posthumous pardon in 2013, gestures that arrived far too late to mean anything to the man they concerned.
What survives is a curious monument. Every general-purpose computer ever built is, in the only sense that matters mathematically, the same machine — one that reads a description and becomes what the description says. Turing found that object while proving it could not answer everything. The power and the limits came from a single argument, and there has never been a way to have one without the other.
References
Alan M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, series 2, vol. 42 (1936–37), pp. 230–265.
Alonzo Church, “An Unsolvable Problem of Elementary Number Theory,” American Journal of Mathematics, vol. 58 (1936); and his review of Turing’s paper, Journal of Symbolic Logic, vol. 2 (1937).
Emil L. Post, “Finite Combinatory Processes — Formulation 1,” Journal of Symbolic Logic, vol. 1 (1936), pp. 103–105.
David Hilbert and Wilhelm Ackermann, Grundzüge der theoretischen Logik (Berlin: Springer, 1928).
Martin Davis, Computability and Unsolvability (New York: McGraw-Hill, 1958).
Andrew Hodges, Alan Turing: The Enigma (London: Burnett Books, 1983).
Charles Petzold, The Annotated Turing (Indianapolis: Wiley, 2008).
The bbchallenge Collaboration, “Determination of the Fifth Busy Beaver Value” (2024).
Trackbacks/Pingbacks