Systems of Logic Based on Ordinals.

London: C.F. Hodgson & Son, 1939.

First edition, the incredibly rare offprint issue, and the copy of Robin Gandy, of Turing’s PhD thesis, “one of the key documents in the history of mathematics and computer science” (Appel), and perhaps Turing’s most formidable paper. “Systems of logic based on ordinals is a profound work of first rank importance. Among its achievements are the exploration of a means of circumventing Gödel’s incompleteness theorems; the introduction of the concept of an ‘oracle machine,’ thereby opening the field of relative computability; and, in the wake of the demolition of the Hilbert programme (by Gödel, Turing and Church), an analysis of the place of intuition in mathematics and logic” (Copeland, p. 126).

“Turing’s 1938 Princeton PhD thesis, Systems of logic based on ordinals, which includes his notion of an oracle machine, has had a lasting influence on computer science and mathematics... A work of philosophy as well as mathematics, Turing’s thesis envisions a practical goal – a logical system to formalize mathematical proofs so that they can be checked mechanically. If every step of a theorem could be verified mechanically, the burden on intuition would be limited to the axioms... Turing’s vision of ‘constructive systems of logic for practical use’ has become reality: in the twenty-first century, automated ‘formal methods’ are now routine” (Appel).

Turing studied at King’s College, Cambridge, becoming a Fellow in 1935. In that year he attended the logic lectures of the topologist M. H. A. Newman, from which he learned of the Entscheidungsproblem: Could there exist, at least in principle, a definite method or process by which it could be decided whether any given mathematical assertion was provable? His negative answer to this question was published in 1936 as On computable numbers, with an application to the Entscheidungsproblem,’ shortly after Alonzo Church at Princeton had published his own solution. Turing’s paper, containing the description of his ‘universal machine,’ is now recognized as the founding theoretical work of modern computer science. “It was only natural that the mathematician M. H. A. Newman should suggest that Turing come to Princeton to work with Church. Some of the greatest logicians in the world, thinking about the issues that in later decades became the foundation of computer science, were in Princeton’s (old) Fine Hall in the 1930s: Gödel, Church, Stephen Kleene, Barkley Rosser, John von Neumann, and others. In fact, it is hard to imagine a more appropriate place for Turing to have pursued graduate study. After publishing his great result on computability, Turing spent two years (1936–38) at Princeton, writing his PhD thesis on ‘ordinal logics’ with Church as his adviser...

“[In his PhD thesis], Turing turns his attention from computation to logic. Gödel and Church would not have called themselves computer scientists: they were mathematical logicians; and even Turing, when he got his big 1936 result ‘On computable numbers,’ was answering a question in logic posed by Hilbert in 1928. Turing’s thesis, Systems of Logic Based on Ordinals, takes Gödel’s stunning incompleteness theorems as its point of departure. Gödel had shown that if a formal axiomatic system (of at least minimal expressive power) is consistent, then it cannot be complete. And not only is the system incomplete, but the formal statement of the consistency of the system is true and unprovable if the system is consistent. Thus if we already have informal or intuitive reasons for accepting the axioms of the system as true, then we ought to accept the statement of its consistency as a new axiom. And then we can apply the same considerations to the new system; that is, we can iterate the process of adding consistency statements as new axioms. In his thesis, Turing investigated that process systematically by iterating it into the constructive transfinite, taking unions of logical systems at limit ordinal notations. His main result was that one can thereby overcome incompleteness for an important class of arithmetical statements (though not for all)...

“Just as one of the strengths of Turing’s great 1936 paper was its philosophical component—in which he explains the motivation for the Turing machine as a model of computation—here in the PhD thesis he is also motivated by philosophical concerns, as in section 9: ‘We might hope to obtain some intellectually satisfying system of logical inference (for the proof of number theoretic theorems) with some ordinal logic. Gödel’s theorem shows that such a system cannot be wholly mechanical, but with a complete ordinal logic we should be able to confine the non-mechanical steps entirely to verifications that particular formulae are ordinal formulae.’

“Turing greatly expands on these philosophical motivations in section 11 of the thesis. His program, then, is this: We wish to reason in some logic, so that our proofs can be mechanically checked (for example, by a Turing machine). Thus we don’t need to trust our students and journal-referees to check our proofs. But no (sufficiently expressive) logic can be complete, as Gödel showed. If we are using a given logic, sometimes we may want to reason about statements unprovable in that logic. Turing’s proposal is to use an ordinal logic sufficiently high in the hierarchy; checking proofs in that logic will be completely mechanical, but the one ‘intuitive’ step remains of verifying ordinal formulas...

“But the PhD thesis contains, almost as an aside, an enormously influential mathematical insight. Turing invented the notion of oracles, in which one kind of computer consults from time to time, in an explicitly axiomatized way, a more powerful kind. Oracle computations are now an important part of the tool kit of both mathematicians and computer scientists working in computability theory and computational complexity theory. This method may actually be the most significant result in Turing’s PhD thesis” (Appel, Chapter 1: The Birth of Computer Science at Princeton in the 1930s).

The preparation of the thesis was somewhat protracted, partly because of the clash of styles between Church and Turing. Turing found Church’s lectures “ponderous and excessively precise; by contrast, Turing’s native style was rough-and-ready and prone to minor errors” (Feferman, p. 4). “[Turing] ended up with a draft containing the main results by Christmas of 1937. But then he wrote Philip Hall [who had been his undergraduate tutor at Cambridge] in March 1938 that the work on his thesis was ‘proving rather intractable, and I am always rewriting parts of it.’ Later he wrote that ‘Church made a number of suggestions which resulted in the thesis being expanded to an appalling length’.” (ibid., p. 5). Church’s influence may have also been partly responsible for the rather muted reception of the thesis. “One reason that the reception of Turing’s [PhD thesis] may have been so limited is that (no doubt at Church’s behest) it was formulated in terms of the λ-calculus, which makes expressions for the ordinals and formal systems very hard to understand” (Appel, loc.cit., p. 4). Following an oral examination in May, on which his performance was noted as ‘Excellent,’ Turing was granted his PhD in June 1938.

Provenance: From the library of Robin Oliver Gandy (1919-95). “[Gandy’s] interest in [mathematical logic] commenced through his wartime acquaintance with Alan Turing as far back as 1944. His twin interests in the foundations of science and mathematics were fostered by Turing. These interests moulded a career which always seemed larger than his publication list, although that grew in diversity with the years to include some seminal papers. Initially, he read widely and published little, but around 1960 he started to produce the major results which made him an international figure in the theory of abstract recursion and in effective, descriptive set theory. There were also major conceptual innovations such as the theory of inductive definitions, and a plethora of ingenious intricate proofs in different corners of the subject. He wrote papers on many areas of logic and was much in demand as a reviewer of books on the foundations of mathematics and science. He remained active and productive and was a familiar figure at international conferences until his sad and unexpected death (from an aortic rupture) on November 20th, 1995.

“He was born on September 22nd, 1919, in Peppard, Oxfordshire, where his father, Thomas Gandy, was in general practice. His mother Ida Gandy earned a reputation for a sequence of books based on her early life in Wiltshire. Educated at Abbotsholme, a progressive public school, he went on to join that special elite at King’s College, Cambridge, intellectual home of such famous names as E. M. Forster the novelist, J. Maynard Keynes the economist – and Alan Turing. He met Turing at a party in 1940 (Gandy’s graduation year) but their early wartime careers were separate. Gandy was commissioned in the Royal Electrical and Mechanical Engineers and became an expert on military radio and radar, whilst Turing joined the cryptanalysts at Bletchley Park. They were brought together at Hanslope Park in 1944 to work on a speech decipherment system, christened ‘Delilah’ at Gandy’s suggestion because it was intended to be a ‘deceiver of men’.

“Their friendship continued after the war, back at King’s College where Turing had resumed his fellowship. Gandy took Part III of the Mathematical Tripos with distinction, then began studying for a PhD under Turing’s supervision; his successful thesis on the logical foundation of physics (On axiomatic systems in mathematics and theories in physics) was presented in 1953 and can now be seen as a bridge between his wartime expertise and later career. When Turing died in 1954 he left his mathematical books and papers to Gandy, who, in 1963, took over from Max Newman the task of editing the papers for publication” (Moschovakis & Yates, pp. 367-8).

Offprints of Turing’s papers are extremely rare in institutional holdings, and even more so in commerce. We have located only two copies: one in the Alan Turing Archive at King’s College Cambridge (AMT/B/15), one at St. Andrew’s, and then one in the Max Newman collection at Bletchley Park.

Andrew W. Appel (ed.), Alan Turing’s Systems of Logic: The Princeton Thesis, Princeton University Press, 2012; B. J. Copeland, The Essential Turing, Clarendon Press, 2004; Solomon Feferman, ‘Turing’s Thesis,’ Notices of the American Mathematical Society, Vol. 53, 2006, pp. 1-8; Andrew Hodges, Alan Turing: The Enigma, 1983, pp. 142-3; Yiannis Moschovakis & Mike Yates, ‘In Memoriam: Robin Oliver Gandy 1919-1995’, Bulletin of Symbolic Logic, Vol. 2, 1996, pp. 367-370.

Offprint from: Proceedings of the London Mathematical Society, Second Series, Vol. 45, pp. 161-228. 8vo (258 x 178 mm), original printed wrappers (plain rear wrapper replaced from another similar issue of the journal, spine worn with loss at head and foot, some light soiling, pencil inscription ‘With corrections by ROG’ on upper wrapper and some corrections and annotations in pencil by Gandy in text).

Item #4537

Price: $28,500.00