Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-23T18:04:38.345Z Has data issue: false hasContentIssue false
  • English
  • Français

Turing Computations On Ordinals

Published online by Cambridge University Press:  15 January 2014

Peter Koepke
Peter Koepke*
Affiliation:
Mathematisches Institut, Rheinische Friedrich-Wilhelms-Universität, Beringstraße 1, D-53115 Bonn, Germany. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We define the notion of ordinal computability by generalizing standard Turing computability on tapes of length ω to computations on tapes of arbitrary ordinal length. We show that a set of ordinals is ordinal computable from a finite set of ordinal parameters if and only if it is an element of Gödel's constructible universe L. This characterization can be used to prove the generalized continuum hypothesis in L.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 11 , Issue 3 , September 2005 , pp. 377 - 397
Copyright
Copyright © Association for Symbolic Logic 2005

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Büchi, J. Richard, Weak second-order arithmetic and finite automata, Zeitschrift für Mathematische Logik und die Grundlagen der Mathematik, vol. 6 (1960), pp. 66–92.CrossRefGoogle Scholar
[2] Devlin, Keith, Constructibility, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1984.CrossRefGoogle Scholar
[3] Gödel, Kurt, The consistency of the continuum hypothesis, Annals of Mathematics Studies, vol. 3, Princeton University Press, Princeton, 1940.CrossRefGoogle Scholar
[4] Hamkins, Joel David and Lewis, Andy, Infinite time Turing machines, The Journal of Symbolic Logic, vol. 65 (2000), no. 2, pp. 567–604.CrossRefGoogle Scholar
[5] Jensen, Ronald R., The fine structure of the constructible hierarchy, Annals of Mathematical Logic, vol. 4 (1972), pp. 229–308.CrossRefGoogle Scholar
[6] Richardson, Thomas Lloyd, Silver machine approach to the constructible universe, Ph.D. thesis, University of California, Berkeley, 1979.Google Scholar
[7] Sacks, Gerald E., Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, Heidelberg, 1990.CrossRefGoogle Scholar
[8] Silver, Jack H., How to eliminate the fine structure from the work of Jensen, handwritten manuscript, 197?Google Scholar