On Computable Numbers, with an Application to the Entscheidungsproblem
Alan Turing · 1936 · Proceedings of the London Mathematical Society, 2nd series, 42, 230–265
Summary
Introduces an abstract machine that reads and writes symbols on a tape according to a finite table of rules, and uses it to show that no general procedure can decide whether an arbitrary program halts.
Why it matters
It established what computation is, in a form precise enough to prove things about, and simultaneously fixed a hard limit on it. The universal machine that can simulate any other is the conceptual ancestor of the stored-program computer, and the undecidability result remains the reason certain questions about programs can never be answered in general.