''Systems of Logic Based on Ordinals'' was the PhD dissertation of the

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...

Alan Turing Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical co ...

. Turing's thesis is not about a new type of formal logic, nor was he interested in so-called ‘ranked logic’ systems derived from ordinal or relative numbering, in which comparisons can be made between truth-states on the basis of relative veracity. Instead, Turing investigated the possibility of resolving the Godelian incompleteness condition using

Cantor A cantor or chanter is a person who leads people in singing or sometimes in prayer. In formal Jewish worship, a cantor is a person who sings solo verses or passages to which the choir or congregation responds. In Judaism, a cantor sings and lead ...

's method of infinites. This condition can be stated thus—in all systems with finite sets of axioms, an exclusive-or condition applies to expressive power and provability; i.e. one can have power and no proof, or proof and no power, but not both. The thesis is an exploration of formal mathematical systems after Gödel's theorem. Gödel showed that for any formal system S powerful enough to represent arithmetic, there is a theorem G which is true but the system is unable to prove. G could be added as an additional axiom to the system in place of a proof. However this would create a new system S' with its own unprovable true theorem G', and so on. Turing's thesis looks at what happens if you simply iterate this process repeatedly, generating an infinite set of new axioms to add to the original theory, and even goes one step further in using

transfinite recursion Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Its correctness is a theorem of ZFC. Induction by cases Let P(\alpha) be a property defined for a ...

to go "past infinity," yielding a set of new theories G_n, one for each ordinal number n. The thesis was completed at Princeton under

Alonzo Church Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician, computer scientist, logician, philosopher, professor and editor who made major contributions to mathematical logic and the foundations of theoretical computer scien ...

and was a classic work in mathematics which introduced the concept of

ordinal logic In mathematics, ordinal logic is a logic associated with an ordinal number by recursively adding elements to a sequence of previous logics.Solomon Feferman, ''Turing in the Land of O(z)'' in "The universal Turing machine: a half-century survey" by R ...

. Martin Davis states that although Turing's use of a computing oracle is not a major focus of the dissertation, it has proven to be highly influential in

theoretical computer science computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the ...

, e.g. in the

polynomial time hierarchy In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. T ...

. Martin Davis "Computability, Computation and the Real World", in ''Imagination and Rigor'' edited by Settimo Termini 2006 pages 63-6

/ref>

References

External links

* https://rauterberg.employee.id.tue.nl/lecturenotes/DDM110%20CAS/Turing/Turing-1939%20Sysyems%20of%20logic%20based%20on%20ordinals.pdf * https://www.dcc.fc.up.pt/~acm/turing-phd.pdf * https://web.archive.org/web/20121023103503/https://webspace.princeton.edu/users/jedwards/Turing%20Centennial%202012/Mudd%20Archive%20files/12285_AC100_Turing_1938.pdf * * History of logic Systems of formal logic Alan Turing Ordinal numbers Mathematics papers {{mathematics-lit-stub