On computable numbers, with an application to the Entscheidungsproblem.
London: C.F. Hodgson and Son, 1936-1937. First edition, journal issue, of the founding paper of the modern science of computing — the paper in which the twenty-two-year-old Alan Turing, setting out to settle an abstract question in mathematical logic, instead defined the machine the rest of the century would build. To decide whether a mechanical procedure could in principle determine the truth of any mathematical statement, Turing had first to say precisely what a mechanical procedure is: a finite device reading and writing symbols along an unbounded paper tape. Within eleven pages he had shown that a single such device, given on its tape the coded description of any other, could carry out its computation exactly — the universal Turing machine, the direct conceptual ancestor of every stored-programme computer ever built. The present copy is the paper as the London Mathematical Society first issued it in 1936, in the two original consecutive parts of its Proceedings, in their original printed wrappers. Turing began the work in the spring of 1935, newly elected a fellow of King’s College Cambridge, while attending Max Newman’s lectures on the foundations of mathematics. David Hilbert had posed the Entscheidungsproblem — the ‘decision problem’ — in 1928: is there a definite method that, given any statement in a formal logical system, decides in a finite number of steps whether it is provable? Turing’s instinct was that no such method could exist, and that proving it required pinning down, with complete precision, what a ‘definite method’ could be. He began with the image of a human computer — in 1936 the word still meant a person, supplied with pencil, paper, and time — and pared away everything inessential until only a formal skeleton remained: a machine able to occupy any one of a finite number of internal states (Turing’s ‘m-configurations’), to read and write a finite alphabet of symbols on a tape divided into squares, and to shift the tape one square to the left or right. The restriction to a finite number of states he justified directly: were infinitely many states of mind admitted, ‘some of them will be arbitrarily close and will be confused’ — and in any case more elaborate states could always be traded for more symbols written on the tape. ‘One of the facets of extreme originality’, his wartime colleague Irving Good recalled, ‘is not to regard as obvious the things that lesser minds call obvious’ (quoted in Dyson, Turing’s Cathedral, p. 247). Where Alonzo Church at Princeton and Emil Post in New York approached the same ground through formal logical calculi, Turing’s machine was concrete enough that its claim to capture every possible mechanical procedure was, as Church himself would shortly concede, immediately convincing. The decisive construction occupies eleven pages. Turing shows that the complete instruction-table of any of his machines can itself be written out as a finite string of symbols — that a machine can be encoded as a number — and then that a single machine can be built which, given on its tape the coded description of any other, proceeds to do exactly what that other machine would have done. This is the universal machine, and it is the whole of modern computing in embryo: a device whose behaviour is fixed not by rebuilding it for each new task but by feeding it a different sequence of coded instructions, held in the same memory as its data and read one symbol at a time. The machine itself, Turing was at pains to show, need be no more intelligent than a typewriter: at any moment it does nothing more than read a symbol, write or erase a symbol, shift the tape one square, and change its state — and yet behaviour of unlimited complexity can be obtained, the complexity residing either in the machine’s states or, equivalently, in the symbols on its tape. ‘In the long view of intellectual history’, Stephen Wolfram has written, ‘I believe universal computation will stand as the single most important idea to emerge in the twentieth century. And this paper is where it first appeared with clarity’ (in Cooper & van Leeuwen, p. 44). The title Turing chose — ‘On Computable Numbers’ rather than the more natural ‘On Computable Functions’ — marks the shift the paper accomplished. Before Turing, as George Dyson observes, things were done to numbers; after Turing, by showing that a machine could be encoded as a number and a number decoded as a machine, numbers began to do things — the inversion the next half-century would learn to call software (Dyson, pp. 246–250). The same construction, turned against itself, yields the result Turing had set out to find. By a diagonal argument structurally akin to Gödel’s incompleteness proof of 1931 — which Turing cites at the foot of his opening page — he shows that no machine can decide, of an arbitrary machine and input, whether the computation will ever halt or run on forever. From the unsolvability of this halting problem the unsolvability of Hilbert’s Entscheidungsproblem follows directly: there can be no definite method for deciding the provability of an arbitrary mathematical statement. Hilbert’s programme, which had sought to set all of mathematics on a mechanically decidable footing, could not be carried through; and the boundary Turing drew between what a machine can and cannot do has held, unmoved, for ninety years. Turing handed Newman a draft in April 1936. Newman pressed the London Mathematical Society to publish it and arranged for Turing to cross to Princeton on his King’s fellowship to work with Church, writing in his letter of introduction that the contact mattered so that Turing ‘should not develop into a confirmed solitary’ (quoted in Dyson, p. 248). The reception on publication was quiet: engineers found the paper too abstract, logicians were put off by its talk of paper tape and machines, and Turing reported to his mother in February 1937 that only two requests for reprints had come in (Hodges, p. 154). Recognition came through Church, who reviewed the paper in the Journal of Symbolic Logic in 1937, coined the term ‘Turing machine’, and noted that computability by such a machine made the identification with effective calculability ‘evident immediately’. What had been Church’s thesis became, from then on, the Church-Turing thesis. Even Gödel, who had little patience for attempts to strengthen his own results, judged that with Turing’s analysis ‘one has for the first time succeeded in giving an absolute definition’ of mechanical procedure, one not depending on the formalism chosen. A year later Turing published a separate three-page Correction, repairing errors the logician Paul Bernays had found in the most intricate stretch of the proof — the construction by which the Entscheidungsproblem result is reached. It was issued on its own, after the paper. The present copy is the paper as first published in 1936, the two parts of the Proceedings that carry the argument itself, without that separately-printed Correction — a distinction that bears on the market for the paper (below) but not on its substance, since the universal machine and the unsolvability proof are complete and entire in these pages. The paper went out, in the form offered here, to the London Mathematical Society’s membership and to the world’s subscribing libraries: the two consecutive parts of the journal in which it begins and concludes. The first part carries, loosely inserted as issued, the Society’s printed announcement of its meeting of 10 December 1936 on the algebraic geometry of surfaces — a small contemporary witness to the ordinary mathematical week into which the most consequential paper of the century was quietly released. Copies of the paper in the original journal parts, in untouched wrappers, are scarce, and the trade record divides sharply according to whether the separately-issued Correction is present. ABPC and RBH between them record, among copies with the Correction, the Richard Green copy at Christie’s New York on 17 June 2013 ($182,500) and a Baltimore copy in 2003 ($13,800); among copies of the paper alone, the Origins of Cyberspace copy from the Norman Library at Christie’s New York on 23 February 2005 ($22,800) and a Christie’s London copy on 13 December 2006 (£13,200), with a Bloomsbury copy of 24 October 2007 ($57,120) of unspecified state. The wide gap between the with-Correction and paper-alone tiers is the market’s own measure of how much the three-page sequel adds to a set. The rarer self-wrappered author’s offprint — a physically distinct artefact from the journal-issue parts — sets the ceiling for the paper in any form: the offprint from Sara Turing’s 1956 gift to Norman Routledge realised £208,000 at Rare Book Auctions in Lichfield in June 2025. The paper is catalogued as Hook & Norman, Origins of Cyberspace 394 (the entry, like the present copy, for the paper without the Correction), and as Tomash and Williams T61 and T62 (rebacked copies). The standard editions are P. T. Saunders’s Collected Works of A. M. Turing (North-Holland, 1992), B. J. Copeland’s The Essential Turing (Clarendon, 2004), and Charles Petzold’s line-by-line The Annotated Turing (Wiley, 2008); the standard life remains Andrew Hodges’s Alan Turing: The Enigma (1983). That the paper still generates new mathematics is plain from a striking recent return to it: in 2024 the quantum-information theorist Gilles Brassard and two colleagues published ‘On computable numbers, with an application to the Druckproblem’ — the title deliberately Turing’s — proving that the numbers Turing defined as computable, those a machine can print digit by digit, are not closed under addition in the constructive sense. Ninety years on, the precise sense in which Turing’s numbers are computable is still yielding theorems. The universal machine waited a decade for its embodiment in hardware. When John von Neumann set down the logical design of the stored-programme computer in his First Draft of a Report on the EDVAC in 1945 — the architecture nearly every computer since has followed — he was building in electronics the machine Turing had defined on paper: one device whose behaviour is fixed not by its wiring but by a program of coded instructions held in its own memory. Von Neumann had known the paper since Turing’s Princeton years of 1936–38, and had tried to keep him on as his assistant; George Dyson took the title of his 2012 history Turing’s Cathedral from precisely this line of descent — from the universal Turing machine of these eleven pages to the machine room at the Institute for Advanced Study where the first stored-programme computers were built. Ninety years after Hodgson set the type, the universal Turing machine is the thing on which these words were written, and on which they are now being read. Two parts of Proceedings of the London Mathematical Society, series 2, volume 42 (1936–37), large 8vo (275 × 184 mm): Part 3 (pp. 161–240) and Part 4 (pp. 241–320), in which Turing’s paper occupies pp. 230–265, beginning in Part 3 (received 28 May 1936, read 12 November 1936) and concluding in Part 4 (issued 23 December 1936). Each part in its original pale-green printed wrapper, the front carrying the Society’s contents list and the rear the imprint of C. F. Hodgson & Son, Ltd., 2 Newton Street, Kingsway, W.C.2. Part 3 with the printed London Mathematical Society meeting-announcement card of 10 December 1936 loosely inserted at the front wrapper as issued. Spines a little rubbed and discoloured with minor loss; internally clean and unrestored. The present set comprises the two parts of volume 42 that carry the paper itself; the Correction (Proc. LMS series 2, vol. 43, part 7, pp. 544–546), issued separately in 1937, is not included.
Item #6577
Price: $195,000.00
