“On Computable Numbers, with an Application to the Entscheidungsproblem” is a 1936 paper by Alan Turing, published in the Proceedings of the London Mathematical Society. It is widely regarded as the paper that founded modern computer science by giving a precise mathematical account of what it means to compute.
To do this, Turing introduced the abstract device now called the Turing machine: a finite set of states, an infinite tape, a read-write head, and a program of transition rules. He used it to define the class of computable numbers, those whose digits can be produced by such a machine, and to formalize the intuitive idea of an effective procedure.
Turing’s central application was to the Entscheidungsproblem, or decision problem, posed by David Hilbert, which asked for a general procedure to decide whether any statement of first-order logic is provable. Using a diagonal argument, Turing showed that no such general procedure exists. Along the way he demonstrated that some well-defined problems are undecidable: no machine can solve them for every input.
The paper proved foundational on two fronts. It established hard mathematical limits on what machines can compute, and it supplied the model of computation that the entire field of computability theory was built upon.