Systems of logic based on ordinals.

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

First edition, journal issue in original printed wrappers, 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). Rare on the market in unrestored original printed wrappers (we know of only one copy at auction, in the Weinreb Computer Collection, Bloomsbury Book Auctions, 28 October 1999).

“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.

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.

Pp. 161-228 in: Proceedings of the London Mathematical Society, Second Series, Vol. 45, No. 3, 21 March, 1939. Large 8vo (260 x 172 mm), pp. 161-240. Original printed wrappers (three chips from edges of front wrapper, one tiny chip from rear wrapper, spine ends worn and with a few letters of spine title rubbed away).

Item #4425

Price: $9,500.00