The Tape, the Head, the Rules
Alan Turing's 1936 paper introduced the simplest possible model of a general-purpose computer: an infinite tape of cells, a read/write head, and a finite table of rules. At each step, the machine reads the current cell, consults the transition table based on its current state and the symbol read, writes a new symbol, moves left or right, and enters a new state. This austere mechanism captures the full power of computation.
Universal Computation
Turing's most profound insight was that a single machine can simulate any other. By encoding a Turing machine's transition table as data on the tape, a universal Turing machine reads and executes that program step by step. This is the theoretical foundation of the stored-program computer — the architecture underlying every laptop, phone, and server today.
The Limits of Computation
Not everything is computable. Turing proved that no algorithm can determine, in general, whether an arbitrary Turing machine will halt or loop forever. This halting problem is the first in a vast landscape of undecidable problems. The Busy Beaver function — which asks how many steps the longest-halting n-state machine takes — grows faster than any computable function, illustrating the staggering complexity hiding inside tiny programs.
From Theory to Practice
Every programming language, every compiler, every operating system is ultimately a realization of Turing's model. Complexity classes like P and NP are defined in terms of Turing machine running times. The model remains the gold standard for reasoning about what is computable, what is efficient, and what is fundamentally impossible, making it as relevant today as it was in 1936.