Turing's machine, or the question no algorithm can answer
In the summer of 1935, Alan Turing lay on his back in the meadow near Grantchester, outside Cambridge, and worked out the shape of a machine that did not exist. He had been attending lectures by the logician Max Newman on Hilbert’s Entscheidungsproblem — a question posed in 1928: could a general procedure determine, for any mathematical statement, whether it was provable? Turing came away thinking there was something worth finding in that word “procedure.”
The machine he arrived at was stripped to its essence: an infinite paper tape divided into squares, each holding a symbol from a small alphabet; a read/write head that could scan one square at a time; a finite table of rules specifying what to print and which direction to move next (Stanford Encyclopedia of Philosophy). No gears, no springs — just a description of the simplest possible act of following instructions. Turing called it an “a-machine,” for automatic.
With that formalism in hand, Turing submitted his 36-page answer to the London Mathematical Society on 28 May 1936. “On Computable Numbers, with an Application to the Entscheidungsproblem” appeared in print that November and December (Wikipedia). His verdict on Hilbert’s question was no. Using a diagonal argument borrowed from Cantor, Turing proved that no machine can reliably determine whether another machine will ever halt — the Halting Problem — and that this impossibility closes the Entscheidungsproblem’s door permanently.
While Turing was drafting, Alonzo Church at Princeton had reached the same conclusion by a different route, via lambda calculus, and published in April 1936 — weeks before Turing submitted. When Turing learned of this, he quickly showed the two approaches were equivalent. Church, reviewing Turing’s paper the following year, recognised the convergence and gave the abstract device its lasting name: the Turing machine.
Here is the part that complicates the story. Turing’s colleague David Champernowne, told about the universal machine — one device capable of simulating any other — reportedly dismissed the idea as a curiosity: a physical realisation would need a building the size of the Albert Hall (Stanford Encyclopedia of Philosophy). He was correct about the engineering problem and wrong about everything else. The universal machine is not a plan you build from iron; it is a principle you instantiate in silicon, at a scale Champernowne could not have imagined.
What Turing had done — as a side effect of proving a negative — was define computation. Before 1936, “mechanical procedure” was a phrase borrowed from common sense. After it, the phrase meant precisely: whatever a Turing machine can execute. That drew both a ceiling and a floor. The ceiling: some things no algorithm can ever decide. The floor: anything algorithmic can be captured in a single model. Every act of computation since — sorting a list, parsing a sentence, generating text — has taken place on that floor.
Turing had set out to answer a question about mathematics. He had accidentally answered a question about the nature of mind. Fourteen years later, in 1950, he would ask it directly.
Sources
- Alan Turing — Stanford Encyclopedia of Philosophy — Grantchester meadow anecdote, the a-machine’s structure, Church-Turing equivalence, and the Champernowne “Albert Hall” dismissal (drawing on Andrew Hodges’s biography).
- On Computable Numbers — Wikipedia — submission and publication dates, the Halting Problem proof, Church’s simultaneous work, and the paper’s reception.
- Alan Turing — Wikipedia — biographical timeline, Newman’s lectures, and the paper’s submission on 28 May 1936.