Systems of Logic Based on Ordinals was the PhD dissertation of the mathematician Alan Turing.[1][2]
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’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; ie 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 for that 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 considers iterating the process to infinity, creating a system with an infinite set of axioms.
The thesis was completed at Princeton under Alonzo Church and was a classic work in mathematics which introduced the concept of ordinal logic.[3]
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, e.g. in the polynomial time hierarchy.[4]
References
Turing, Alan (1938). Systems of Logic Based on Ordinals (PhD thesis). Princeton University. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3. ProQuest 301792588.
Turing, A. M. (1939). "Systems of Logic Based on Ordinals". Proceedings of the London Mathematical Society: 161–228. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3.
Solomon Feferman, Turing in the Land of O(z) in "The universal Turing machine: a half-century survey" by Rolf Herken 1995 ISBN 3-211-82637-8 page 111
Martin Davis "Computability, Computation and the Real World", in Imagination and Rigor edited by Settimo Termini 2006 ISBN 88-470-0320-2 pages 63-66 [1]
External links
"Turing's Princeton Dissertation". Princeton University Press. Retrieved January 10, 2012.
Solomon Feferman (November 2006), "Turing's Thesis" (PDF), Notices of the AMS, 53 (10)
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
