## 1936-37 · London

by Turing, Alan M

London, 1936-37. The Most Famous Theoretical Paper in the History of Computing Turing, Alan Mathison (1912–54). (1) On computable numbers, with an application to the Entscheidungsproblem. In Proceedings of the London Mathematical Society, 2d series, 42, pt. 3 (November 30, 1936): 230–40; pt. 4 (December 23, 1936): 241–65. (2) On computable numbers, with an application to the Entscheidungsproblem. A correction. In Proceedings of the London Mathematical Society, 2d series, 43 (1937): 544–46. Together three journal numbers. 259 x 175 mm. Original printed wrappers, rebacked, small chip in back cover of third number; preserved in a cloth drop-back box. Very good set. First Edition, with Turing’s Correction Published the Following Year. Alan Turing’s theoretical paper On Computable Numbers is undoubtedly the most famous theoretical paper in the history of computing. It is a mathematical description of what Turing called a universal machine—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 definite 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 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.” 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. Turing’s idea of a “universal machine” was given the name “Turing machine” by Alonzo Church. Turing’s concept of the “universal machine” was adapted to theories of brain function by McCulloch and Pitts, whose ideas in turn exerted a considerable influence on von Neumann’s First Draft of a Report on the EDVAC, a theoretical description of the stored-program machine that was read by all the designers of first-generation computers. In showing that a universal machine was possible, Turing’s paper was highly influential in the theory of computation, and it remained a powerful expression of the virtually unlimited adaptability of electronic digital computers. From Gutenberg to the Internet, reading 7.1. Origins of Cyberspace 394. Randell, The Origins of Digital Computers: Selected Papers, 519. (Inventory #: 43745)