Alan Turing's Computing Theory
In 1936, the young British mathematician Alan Turing published a paper that defined, in precise mathematical terms, what it means to compute something. Titled "On Computable Numbers, with an Application to the Entscheidungsproblem," it introduced an abstract device now known as the Turing machine and showed that some well-posed mathematical questions can never be settled by any mechanical procedure. The paper is widely regarded as a founding document of theoretical computer science.
The background was a crisis of confidence in the foundations of mathematics. In the early twentieth century, the German mathematician David Hilbert and others hoped to show that mathematics could be placed on a complete and consistent footing. One open question, the Entscheidungsproblem or "decision problem," asked whether a general method existed that could determine, for any statement of formal logic, whether it was provable. In 1931 Kurt Gödel had already shown that any sufficiently powerful formal system contains true statements it cannot prove, shaking Hilbert's program. The decision problem remained unresolved.
Turing, then in his early twenties and a fellow at King's College, Cambridge, approached it by asking what a "definite method" actually is. He imagined a machine that reads and writes symbols on an endless tape, following a finite table of rules. Despite its simplicity, such a machine could carry out any step-by-step procedure one could describe. Turing also showed that a single "universal" machine could imitate any other when given that machine's rules as input, an idea that anticipates the stored-program computer. He then proved that certain problems, including the so-called halting problem of deciding whether an arbitrary program will ever finish, are undecidable, and from this concluded that Hilbert's decision problem has no solution.
Turing was not alone. The American logician Alonzo Church reached the same negative answer slightly earlier, using a different formalism called the lambda calculus, and Turing's paper appeared shortly afterward. The two approaches were soon shown to be equivalent, and the shared claim that they capture everything computable is known as the Church–Turing thesis. It is a thesis rather than a theorem, since it links an informal notion to a formal one, but it has held up well.
The consequences were profound. Turing's work gave a rigorous basis for the idea of an algorithm and set the limits of what computers can do, however powerful they become. Historians debate how directly it shaped the first electronic computers of the 1940s, which owed much to engineering and to figures such as John von Neumann, but the conceptual framework became central to computer science. Turing's later wartime codebreaking and his postwar work on machine intelligence built on the same outlook. Today the highest honor in the field, the Turing Award, bears his name.