TURING'S PH.D.-THESIS

TURING, A.M.

Systems of Logic based on Ordinals. [Received 31 May, 1938. - Read 16 June, 1938.]. [In: Proceedings of the London Mathematical Society. Second Series. Volume 45].

London, Hodgson & Son, 1939.

Royal8vo. In a recent nice red full cloth binding with gilt lettering to spine. Entire volume 45 of "Proceedings of the London Mathematical Society. Second Series". Small white square paper label pasted on to lower part of spine, covering year of publication stating: "A Gift / From /Anna Wheeler". A very nice and clean copy without any institutional stamps. Pp. 161-240. [Entire volume: (4), 475 pp.].

The rare first printing of Turing's Ph.D.-thesis, which "opened new fields of investigation in mathematical logic". This seminal work constitutes the first systematic attempt to deal with the Gödelian incompleteness theorem as well as the introduction to the notion of relative computing.

After having studied at King's College at Cambridge from 1931 to 1934 and having been elected a fellow here in 1935, Turing, in 1936 wrote a work that was to change the future of mathematics, namely his seminal "On Computable Numbers", in which he answered the famous "Entscheidungsproblem", came up with his "Universal Machine" and inaugurated mechanical and electronic methods in computing. This most famous theoretical paper in the history of computing caught the attention of Church, who was teaching at Princeton, and in fact he gave to the famous "Turing Machine" its name. It was during Church's work with Turing's paper that the "Church-Turing Thesis" was born. After this breakthrough work, Newman, under whom Turing had studied at Cambridge, urged him to spend a year studying with Church, and in September 1936 he went to Princeton. It is here at Princeton, under the guidance of Church, that Turing in 1938 finishes his thesis [the present paper] and later the same year is granted the Ph.D. on the basis of it. The thesis was published in "Proceedings of the London Mathematical Society" in 1939, and after the publication of it, Turing did no more on the topic, leaving the actual breakthroughs to other generations.

In his extraordinary Ph.D.-thesis Turing provides an ingenious method of proof, in which a union of systems prove their own consistency, disproving, albeit shifting the problem to even more complicated matters, Gödel's incompleteness theorem. It would be many years before the ingenious arguments and striking partial completeness result that Turing obtained in the present paper would be thoroughly investigated and his line of research continued.

The present thesis also presents other highly important proofs and hypotheses that came to influence several branches of mathematics. Most noteworthy of these is the idea that was later to change the face of the general theory of computation, namely the attempt to produce an arithmetical problem that is not number-theoretical (in his sense). Turing's result is his seminal "o-machines"; he here introduces the notion of relative computing and augments the "Turing Machines" with so-called oracles ("o"), which allowed for the study of problems that could not be solved by the Turing machine. Turing, however, made no further use of his seminal o-machine, but it is that which Emil Post used as the basis for his theory of "Degrees of Unsolvability", crediting Turing with the result that for any set of natural numbers there is another of higher degree of unsolvability. This transformed the notion of computability from an absolute notion into a relative one, which led to entirely new developments and in turn to vastly generalized forms of recursion theory. "In 1939 Turing published "Systems of Logic Based on Ordinals,"... This paper had a far-reaching influence; in 1942 E.L. Post drew upon it for one of his theories for classifying unsolvable problems, while in 1958 G. Kreisel suggested the use of ordinal logics in characterizing informal methods of proof. In the latter year S. Feferman also adapted Turing's ideas to use ordinal logics in predicative mathematics." (D.S.B. XIII:498).

A part from these groundbreaking points, which Turing never returned to himself, he here also considers intuition versus technical ingenuity in mathematical reasoning, does so in an interesting and provocative manner and comes to present himself as one of the most important thinkers of modern mathematical as well as philosophical logic.

"Turing turned to the exploration of the uncomputable for his Princeton Ph.D. thesis (1938), which then appeared as "Systems of Logic based on Ordinals" (Turing 1939).
It is generally the view, as expressed by Feferman (1988), that this work was a diversion from the main thrust of his work. But from another angle, as expressed in (Hodges 1997), one can see Turing's development as turning naturally from considering the mind when following a rule, to the action of the mind when not following a rule. In particular this 1938 work considered the mind when seeing the truth of one of Gödel's true but formally unprovable propositions, and hence going beyond rules based on the axioms of the system. As Turing expressed it (Turing 1939, p. 198), there are 'formulae, seen intuitively to be correct, but which the Gödel theorem shows are unprovable in the original system.' Turing's theory of 'ordinal logics' was an attempt to 'avoid as far as possible the effects of Gödel's theorem' by studying the effect of adding Gödel sentences as new axioms to create stronger and stronger logics. It did not reach a definitive conclusion.
In his investigation, Turing introduced the idea of an 'oracle' capable of performing, as if by magic, an uncomputable operation. Turing's oracle cannot be considered as some 'black box' component of a new class of machines, to be put on a par with the primitive operations of reading single symbols, as has been suggested by (Copeland 1998). An oracle is infinitely more powerful than anything a modern computer can do, and nothing like an elementary component of a computer. Turing defined 'oracle-machines' as Turing machines with an additional configuration in which they 'call the oracle' so as to take an uncomputable step. But these oracle-machines are not purely mechanical. They are only partially mechanical, like Turing's choice-machines. Indeed the whole point of the oracle-machine is to explore the realm of what cannot be done by purely mechanical processes...
Turing's oracle can be seen simply as a mathematical tool, useful for exploring the mathematics of the uncomputable. The idea of an oracle allows the formulation of questions of relative rather than absolute computability. Thus Turing opened new fields of investigation in mathematical logic. However, there is also a possible interpretation in terms of human cognitive capacity." (SEP).

Following an oral examination in May, in which his performance was noted as "Excellent," Turing was granted his PhD in June 1938.

Order-nr.: 54748