Turing, Alan Mathison
First edition of one of the foundational papers of theoretical computer science, introducing the universal computing machine and a precise mathematical account of effective computation, and establishing limits to what can be decided by an algorithm. Offered with Turing’s separately published correction of 1937.
Further images
-
(View a larger image of thumbnail 1
)
-
(View a larger image of thumbnail 2
)
-
(View a larger image of thumbnail 3
)
-
(View a larger image of thumbnail 4
)
-
(View a larger image of thumbnail 5
)
-
(View a larger image of thumbnail 6
)
-
(View a larger image of thumbnail 7
)
-
(View a larger image of thumbnail 8
)
-
(View a larger image of thumbnail 9
)
-
(View a larger image of thumbnail 10
)
-
(View a larger image of thumbnail 11
)
Three parts, 4to (259 × 175 mm). Original gray-green printed wrappers, rebacked; front wrapper of Part 1 repaired along the upper edge with tape on verso, four other small marginal tears repaired, and slight toning to edges; front wrapper of Part 2 with two small nicks to edges and slight toning; front wrapper of Part 3 with tape repair to upper corner and slight toning to edges; preserved in a cloth box. Interiors clean and bright, with a small spot of glue residue, a few small ink marks, and a small nick to the upper edge of the first leaf of Part 1.
Alan Turing’s (1912–1954) paper arose from one of the central questions of mathematical logic. David Hilbert and Wilhelm Ackermann had formulated the Entscheidungsproblem, asking whether there could be a general, mechanical procedure for deciding the validity of statements in a formal logical system. At Cambridge, Turing encountered the problem through lectures given by Max Newman and devised a strikingly concrete way to address it.
Rather than beginning with a particular formal calculus, Turing described an idealized computing device operating by a finite set of instructions on symbols written on a tape. These machines, subsequently known as Turing machines, supplied a rigorous model of what it means to perform a calculation by a definite procedure. His most consequential insight was the universal machine: a single machine capable, when supplied with a suitable description, of carrying out the operations of any machine of the specified kind. This conceptual separation of machine and instructions became fundamental to the theory of general-purpose computing.
Using this model, Turing demonstrated that there can be no universal algorithm for resolving every problem of the relevant logical kind, thereby giving a negative answer to the Entscheidungsproblem. His argument also established that there are well-defined numbers and mathematical questions that cannot be computed or settled by such a procedure. The paper thus described both the reach and the inherent limitations of mechanized calculation.
Alonzo Church had independently obtained a negative solution to the Entscheidungsproblem through his work on the lambda calculus, published shortly before Turing’s paper. Turing’s achievement remained distinctive: his machine model offered an unusually transparent account of computation in operational terms. The equivalence of these approaches helped give rise to what is now called the Church–Turing thesis, the proposition that effectively calculable functions are precisely those computable by a Turing machine.
The 1937 correction, included here in its original journal part, addresses a technical issue in the argument and forms an integral part of the publication history of the work. Its presence alongside the two 1936 parts makes this a particularly coherent presentation of Turing’s original contribution.
Although Turing’s abstract machine was not a blueprint for a particular computer, the concept of universal computation furnished a central theoretical foundation for the subsequent development of stored-program electronic computers. Turing himself later contributed directly to computing projects, notably the design of the Automatic Computing Engine, and went on to explore the question of machine intelligence in his influential 1950 paper.
Few twentieth-century mathematical papers have had comparable consequences across logic, mathematics, computer science and the philosophy of mind. This original publication records the moment at which computation became an object of precise mathematical investigation.
Origins of Cyberspace, no. 394.
Join our mailing list
* denotes required fields
We will process the personal data you have supplied to communicate with you in accordance with our Privacy Policy. You can unsubscribe or change your preferences at any time by clicking the link in our emails.
