A question about mathematics, not machines
Alan Turing’s 1936 paper was not primarily about building machines; it was an attempt to answer a specific question in mathematical logic raised by David Hilbert in 1928, known as the Entscheidungsproblem, or decision problem: whether there exists a definite, mechanical procedure that could determine, for any given mathematical statement, whether it is true. Answering this required first pinning down precisely what counted as a ‘definite, mechanical procedure’ at all, since the question could not be settled rigorously while that phrase remained informal. Turing’s solution was to invent an abstract device simple enough to define with total precision, and specific enough that whatever it could and could not do would settle the broader question about mechanical procedures in general.
An abstract device with an infinite tape
The device, now called a Turing machine, consists of a tape divided into cells, extendable indefinitely in both directions, each holding a symbol from a small fixed alphabet; a head that reads one cell at a time and can write a new symbol there; and a finite table of rules specifying, for each combination of the machine’s current internal state and the symbol it is reading, what to write, whether to move the head left or right, and which state to enter next. Despite this minimal design, Turing showed the model was capable of expressing any computation that could be carried out by an explicit step-by-step procedure, which is precisely what made it suitable as a formal stand-in for the informal idea of a ‘definite mechanical procedure’ Hilbert’s question depended on.
What the machine proved
Using this formal model, Turing proved that no machine can exist which correctly determines, for every possible machine and starting tape given to it, whether that machine will eventually halt or run forever, a result now known as the halting problem. From this, he derived a negative answer to Hilbert’s original question: there is no general mechanical procedure that decides the truth of arbitrary mathematical statements, because such a procedure would let you solve the halting problem, which is impossible. This was a genuinely new kind of result, not showing that some particular problem is merely hard, but proving that certain well-defined problems can never be solved algorithmically by any machine, however powerful, a permanent rather than temporary limitation.
Church arrived first, by weeks
Turing was not alone in reaching a negative answer to Hilbert’s question, and was not even first. Alonzo Church published an independent proof of the same underlying undecidability result on 15 April 1936, using an entirely different mathematical framework called the lambda calculus, weeks before Turing submitted his own paper to the London Mathematical Society on 31 May 1936. What made Turing’s contribution distinct rather than redundant was that his machine model offered what the paper’s later reception treated as a more direct, intuitively compelling argument built from first principles, closing a gap in how convincingly Church’s version connected to the informal notion of a mechanical procedure. Emil Post also submitted related ideas that autumn, arriving after both Church and Turing.
A thesis, not a theorem
Because two independent formal systems, Church’s lambda calculus and Turing’s machine, turned out to define exactly the same class of computable functions, this convergence became evidence for what is now called the Church-Turing thesis: the claim that Turing machines, lambda calculus and any other similarly general formal system all capture the same, correct notion of what it means for a function to be ‘effectively computable.’ It is important that this is a thesis rather than a proven theorem, since it asserts an equivalence between a precise mathematical definition and an informal, intuitive concept that cannot itself be formalised and proven against. The thesis has held up since the 1930s in the sense that no proposed alternative model of computation has ever exceeded what a Turing machine can compute.
Not a blueprint for real computers
It is worth understanding this model precisely because it is not, and was never meant to be, a description of how to build a fast computer. A Turing machine’s tape access is sequential rather than random, which makes it, by design, too slow for practical use; real computers rely on random-access memory that lets them jump directly to any stored location, an efficiency the original model does not have and was not trying to provide. The value of the Turing machine lies entirely in what it can prove about the limits of computation in principle, chiefly the existence of well-defined problems, like the halting problem, that no computer of any design or speed will ever be able to solve in general. That distinction, between a foundational proof and an engineering blueprint, is the single most useful thing to take from this history.