Turing Machines

In 1936, a 23-year-old Cambridge mathematician named Alan Turing published a paper titled On Computable Numbers. To answer the Entscheidungsproblem — David Hilbert's challenge to find a procedure that could decide the truth of any mathematical statement — Turing did something no one had done before: he gave a precise mathematical definition of what it means to compute anything. The model — an infinite paper tape divided into cells, a head that reads and writes one symbol at a time and shuffles left or right, and a finite table of rules keyed to the machine's internal state — was deliberately austere. It was also sufficient. Every computation any physical machine could ever perform could, in principle, be performed by such a machine. The conceptual machine that would underlie the digital age was sketched in a paper read by perhaps two dozen people.

A computation, on this picture, is nothing more than a sequence of configurations — the tape's contents, the head's position, the current state — each succeeding the last by a single lookup in the rule table; thinking, mechanized into bookkeeping. From that spare beginning, Turing's paper proved three results of permanent importance. First, the universal Turing machine: a single Turing machine could simulate any other Turing machine, given the latter's description, written on the tape, as input. Hardware and software became separable — one fixed machine plus an interchangeable program — and the universal machine is, in essence, the stored-program computer a decade before any was built. This is the core abstraction of every modern computer; the engineering came later, with the ENIAC and von Neumann's architecture, but the idea was already complete on paper. Second, the halting problem: there is no algorithm that, given an arbitrary program and input, can decide whether the program will halt or run forever. The proof uses a diagonal argument identical in spirit to Gödel's incompleteness theorem, and establishes a hard limit on what any computational system can determine about itself — a formal undecidability baked into computation, not a temporary gap in our cleverness. Third, the Church-Turing thesis (jointly with Alonzo Church, who had independently arrived at the lambda calculus): any function that can be effectively calculated at all can be calculated by a Turing machine. The thesis is not a theorem (effective calculation is not formally defined) but has resisted every attempted counter-example for nearly a century, quantum computers included. Its quiet power is that every plausible model of computation turns out to be equivalent — Church's lambda calculus, Gödel's recursive functions, register machines, modern programming languages all compute exactly the same class of functions, no more and no less. That convergence is why “computable” can be treated as a single, absolute notion rather than an artifact of one particular machine.