In 1936, a 24-year-old Cambridge mathematician named Alan Turing published a paper that would lay the theoretical foundation for the entire field of computer science, years before a general-purpose computer had ever been built. Titled “On Computable Numbers, with an Application to the Entscheidungsproblem,” the paper set out to answer a specific question posed by David Hilbert, but in doing so, Turing invented an abstract model of computation so powerful and so clear that it remains the conceptual bedrock of computing to this day.
The Problem Turing Set Out to Solve.
The paper’s stated goal was to resolve the Entscheidungsproblem (“decision problem”), a challenge formulated by Hilbert in 1928: does there exist a definite method — an algorithm — that can determine, for any given statement in a formal logical system, whether that statement is provable? Hilbert hoped the answer would be yes, which would have meant that mathematics could, in principle, be mechanized entirely.
To even ask this question rigorously, Turing needed a precise definition of what it means to “compute” something — what counts as a mechanical, step-by-step procedure. This need for a formal definition of algorithm is what led him to his central and most enduring contribution.
The Turing Machine.
Rather than reasoning abstractly about computation, Turing imagined a simple physical device: an infinite tape divided into cells, each holding a symbol; a read/write head that can move one cell left or right; and a finite set of internal states that determine, based on the current state and the symbol being read, what symbol to write, which direction to move, and which state to enter next.
Despite its extreme simplicity, Turing argued convincingly that such a machine could carry out any process that a human “computer” — at the time, a term for a person who performed calculations by hand, following a fixed set of rules — could carry out. This claim, that his machine captures the full scope of what is mechanically calculable, is now known as the Church–Turing thesis (since the American logician Alonzo Church had independently arrived at an equivalent notion, called lambda calculus, around the same time).
Turing further introduced the idea of a universal machine: a single Turing machine that, given the encoded description of any other Turing machine along with its input, could simulate that machine’s behavior exactly. This is the theoretical ancestor of every modern computer: a general-purpose device that runs whatever program you feed it, rather than being hardwired for a single task.
Computable and Uncomputable Numbers.
Turing defined a real number as “computable” if its decimal digits could be produced by such a machine running forever, digit by digit. This let him ask a sharper question: are all real numbers computable? Using a diagonalization argument reminiscent of Cantor’s proof that the real numbers are uncountable, Turing showed that the answer is no — computable numbers, though infinite in quantity, form only a countable set, and thus almost all real numbers are, in a well-defined sense, forever beyond the reach of any algorithm.
The Halting Problem and the Answer to Hilbert.
From this machinery, Turing derived his most famous result: the halting problem is undecidable. There is no general algorithm — no Turing machine — that can determine, for every possible machine and input, whether that machine will eventually halt or run forever. The proof again uses a diagonalization trick: Turing supposes such a decision machine exists, then constructs a contradiction by having a machine feed itself its own description in a self-referential loop, echoing the same logical structure Gödel had used five years earlier in his incompleteness theorems.
This result let Turing answer Hilbert’s Entscheidungsproblem directly: no, there is no general mechanical procedure for deciding the provability of arbitrary mathematical statements. If such a procedure existed, it could be used to solve the halting problem, which Turing had just proven impossible.
Legacy.
The immediate purpose of the paper was negative — showing what could not be done — but its lasting impact was overwhelmingly generative. In defining computation with total mathematical precision, Turing gave later engineers and scientists exactly the conceptual vocabulary needed to build real machines: the distinction between hardware and software, the very possibility of a stored-program general-purpose computer, and the theoretical limits that still frame debates in computer science today about what problems are solvable at all, independent of how much time or hardware one has.
It is a striking historical irony that a paper devoted to proving the limits of mechanical computation became the founding document of the science of building computing machines. Turing did not just answer Hilbert’s question; he gave humanity a rigorous language for thinking about algorithms, and with it, the blueprint for the digital age.