Systems of Logic Based on Ordinals
Systems of Logic Based on Ordinals was the PhD dissertation of the mathematician Alan Turing.[1][2]
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.
- ↑ 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
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)