Cover of the offprint of Turing's On Computable Numbers inscribed to R. B. Braithwaite.

# Alan Turing Publishes "On Computable Numbers," Describing What Came to be Called the "Turing Machine"

11/30/1936

Alan Turing, aged 16. Turing published On Computable Numbers when he was 24 years old.

In issues dated November 30 and December 23, 1936 of the Proceedings of the London Mathematical Society English mathematician Alan Turing published "On Computable Numbers", a mathematical description of what he called a universal machine— an abstraction that could, in principle, solve any mathematical problem that could be presented to it in symbolic form. Turing modeled the universal machine processes after the functional processes of a human carrying out mathematical computation. In the following issue of the same journal Turing published a two page correction to his paper.

Undoubtedly the most famous theoretical paper in the history of computing, "On Computable Numbers" is a mathematical description an imaginary computing device designed to replicate the mathematical "states of mind" and symbol-manipulating abilities of a human computer. Turing conceived of the universal machine as a means of answering the last of the three questions about mathematics posed by David Hilbert in 1928: (1) is mathematics complete; (2) is mathematics consistent; and (3) is mathematics decidable.

Hilbert's final question, known as the Entscheidungsproblem, concerns whether there exists a defiinite method—or, in the suggestive words of Turing's teacher Max Newman, a "mechanical process"—that can be applied to any mathematical assertion, and which is guaranteed to produce a correct decision as to whether that assertion is true. The Czech logician Kurt Gödel had already shown that arithmetic (and by extension mathematics) was both inconsistent and incomplete. Turing showed, by means of his universal machine, that mathematics was also undecidable.

To demonstrate this, Turing came up with the concept of "computable numbers," which are numbers defined by some definite rule, and thus calculable on the universal machine. These computable numbers, "would include every number that could be arrived at through arithmetical operations, finding roots of equations, and using mathematical functions like sines and logarithms—every number that could possibly arise in computational mathematics" (Hodges, Alan Turing: The Enigma [1983] 100). Turing then showed that these computable numbers could give rise to uncomputable ones—ones that could not be calculated using a definite rule—and that therefore there could be no "mechanical process" for solving all mathematical questions, since an uncomputable number was an example of an unsolvable problem.

From 1936 to 1938 Mathematician Alan Turing spent more than a year at Princeton University studying mathematical logic with Alonzo Church, who was pursuing research in recursion theory. In August 1936 Church gave Turing's idea of a "universal machine" the name "Turing machine." Church coined the term in his relatively brief review of "On Computable Numbers." With regard to Turing's proof of the unsolvability of Hilbert's Entscheidungsproblem, Church acknowledged that "computability by a Turing machine. . . has the advantage of making the identification with effectiveness in the ordinary (not explicitly defined) sense evident immediately—i.e. without the necessity of proving elementary theorems." Church working independently of Turing, had arrived at his own answer to the Entscheidungsproblem a few months earlier. Norman, From Gutenberg to the Internet, Reading 7.2.

Independently of Alan Turing, mathematician and logician Emil Post of the City College of New York developed, and published in October 1936, a mathematical model of computation that was essentially equivalent to the Turing machine. Intending this as the first of a series of models of equivalent power but increasing complexity, he titled his paper Formulation 1. This model is sometime's called "Post's machine" or a Post-Turing machine.

In 1937 Turing and John von Neumann had their first discussions about computing and what would later be called “artificial intelligence” (AI). Always interested in practical applications of computing as well as theory, also while at Princeton, in 1937, believing that war with Germany was inevitable, Turing built in an experimental electromechanical cryptanalysis machine capable of binary multiplication in a university machine shop. After returning to England, on September 4, 1939, the day after Britain and France declared war on Germany, Turing reported to the Government Code and Cypher SchoolBletchley Park, in the town of Bletchley, England.

♦ In June 2013 it was my pleasure to purchase the famous copy of the offprint of "On Computable Numbers" along with the offprint of "On Computable Numbers . . . A Correction" that Turing presented to the English philosopher R. B. Braithwaite. One of very few copies in existence of the offprint, and possibly the only copy in private hands, the offprint sold for £205,250.  It was then a price record for any offprint on a scientific or medical subject, for any publication in the history of computing, and probably the highest price paid at that time for any scientific publication issued in the twentieth century.

Norman, From Gutenberg to the Internet, Reading 7.1. Hook & Norman, Origins of Cyberspace (2002) No. 394.