Systems of Logic Based on Ordinals

Short description: 1938 doctoral thesis by Alan Turing

Systems of Logic Based on Ordinals was the PhD dissertation of the mathematician Alan Turing.[1]

The thesis was completed at Princeton under Alonzo Church and was a classic work in mathematics that introduced the concept of ordinal logic.[2]

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 that 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 to go "past infinity", yielding a set of new theories Gα, one for each ordinal number α.

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 Gödelian incompleteness condition using Cantor's method of infinites.

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.[3]

## References

1. ↑ Turing, Alan (May 1938). Systems of Logic Based on Ordinals (PDF) (Doctor of Philosophy thesis). Seeley G. Mudd Manuscript Library Princeton, NJ: webspace.princeton.edu - via archive.org.
2. ↑ 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
3. ↑ 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]

## Versions

"Facsimile". Seeley G. Mudd Manuscript Library Princeton, NJ: webspace.princeton.edu. https://web.archive.org/web/20121023103503/https://webspace.princeton.edu/users/jedwards/Turing Centennial 2012/Mudd Archive files/12285_AC100_Turing_1938.pdf.
"Transcribed". www.dcc.fc.up.pt - Departamento de Ciência de Computadores Faculdade de Ciências da Universidade do Porto: University of Porto. https://www.dcc.fc.up.pt/~acm/turing-phd.pdf.

## External links

* https://rauterberg.employee.id.tue.nl/lecturenotes/DDM110 CAS/Turing/Turing-1939 Sysyems of logic based on ordinals.pdf
* "Turing's Princeton Dissertation". Princeton University Press. http://www.princeton.edu/turing/alan/dissertation/.
* Solomon Feferman (November 2006), "Turing's Thesis", Notices of the AMS 53 (10), http://math.stanford.edu/~feferman/papers/turingnotices.pdf
* Turing, Alan (1938). "Systems of Logic Based on Ordinals". Proceedings of the London Mathematical Society (Princeton University) s2-45 (1). doi:10.1112/plms/s2-45.1.161. ProQuest 301792588.

Template:Alan Turing

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Systems of Logic Based on Ordinals. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Systems_of_Logic_Based_on_Ordinals&oldid=4346387"