Systems of Logic Based on Ordinals
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.
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.
- Turing, Alan (1938). Systems of Logic Based on Ordinals (PhD thesis). Princeton University. doi:10.1112/plms/s2-45.1.161.
- 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.
- 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 
- "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)
|This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.|
|This article about a mathematical publication is a stub. You can help Wikipedia by expanding it.|