In 1936 Alan Turing wrote “On Computable Numbers, with an Application to the Entscheidungsproblem.” The paper was received by the London Mathematical Society on 28 May 1936 and read on 12 November 1936, and it appeared in the Proceedings of the London Mathematical Society, second series, volume 42, beginning on page 230. The version cited here is the copy hosted in the Oxford computing department e-library.
To attack the question, Turing invented an idealized device, now called a Turing machine, that reads and writes symbols on an infinite tape according to a fixed table of rules. He defined a number as computable if such a machine can write out its digits, and he showed that a single “universal computing machine” could simulate any other machine when given a description of it on its tape. This universal machine is the theoretical ancestor of the stored program computer, the insight that one general device can run any program rather than being wired for one task.
The application named in the title was Hilbert’s Entscheidungsproblem, the question of whether there is a mechanical procedure that can decide the truth of any statement in formal logic. Using a diagonal argument, Turing proved there is no such general procedure. There are well defined problems that no machine can ever solve, no matter how much time it is given.
The paper drew the boundary of what computation can and cannot do, and it did so by giving a precise definition of “machine” in the first place. That definition underlies all later work in computer science and supplied the conceptual frame for Turing’s own later writing on whether machines can think.