Turing Machines
The simplest possible model of computation that captures all of computation. A tape, a head, a state table — and that's enough to compute anything computable.
In 1936, Alan Turing imagined the simplest machine that could perform any calculation: an infinite tape of cells, a read/write head, and a finite table of rules. Despite its simplicity, a Turing machine can compute anything that any computer can compute — from rendering 3D graphics to training neural networks. This universality is the Church-Turing thesis. The Universal Turing Machine takes this further: a single machine that can simulate any other Turing machine, given its description as input. This is the theoretical foundation of the stored-program computer — the idea that data and programs are the same kind of thing. Turing's proof that the halting problem is undecidable (you cannot write a program that determines whether any arbitrary program will halt) established the first fundamental limit of computation and connected directly to Godel's incompleteness theorems. Both reveal that formal systems cannot fully analyze themselves.