Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-28T18:23:51.398Z Has data issue: false hasContentIssue false
  • English
  • Français

Eventually infinite time Turing machine degrees: infinite time decidable reals

Published online by Cambridge University Press:  12 March 2014

P.D. Welch
P.D. Welch*
Affiliation:
Graduate School of Science and Technology, Kobe University, Rokko-Dai, Nada-Ku Kobe 657-8501, Japan School of Mathematics, University of Bristol, Bristol BS8 1TW, England E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We characterise explicitly the decidable predicates on integers of Infinite Time Turing machines, in terms of admissibility theory and the constructible hierarchy. We do this by pinning down ζ, the least ordinal not the length of any eventual output of an Infinite Time Turing machine (halting or otherwise); using this the Infinite Time Turing Degrees are considered, and it is shown how the jump operator coincides with the production of mastercodes for the constructible hierarchy; further that the natural ordinals associated with the jump operator satisfy a Spector criterion, and correspond to the Lζ-stables. It also implies that the machines devised are “Σ2 Complete” amongst all such other possible machines. It is shown that least upper bounds of an “eventual jump” hierarchy exist on an initial segment.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 65 , Issue 3 , September 2000 , pp. 1193 - 1203
Copyright
Copyright © Association for Symbolic Logic 2000

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]Barwise, K.J., Admissible sets and structures, Perspectives in Mathematical Logic, Springer Verlag, Berlin, Heidelberg, 1975.CrossRefGoogle Scholar
[2]Boolos, G. and Jeffrey, R., Computability and logic, Cambridge University Press, 1980.Google Scholar
[3]Devlin, K., Constructibility, Perspectives in Mathematical Logic, Springer Verlag, Berlin, Heidelberg, 1984.CrossRefGoogle Scholar
[4]Hamkins, J.D. and Lewis, A., Infinite time Turing machines, this Journal, to appear.Google Scholar
[5]Hamkins, J.D. and Lewis, A., Post's problem has both positive and negative solutions in the infinite time Turing degrees, submitted to the Archive for Mathematical Logic.Google Scholar
[6]Kechris, A.S., The theory of countable analytic sets, Transactions of the American Mathematical Society, vol. 202 (1975), pp. 259–297.CrossRefGoogle Scholar
[7]Welch, P.D., The length of infinite time Turing degree computations, Bulletin of the London Mathematical Society, vol. 32 (2000), no. 2, pp. 129–136.CrossRefGoogle Scholar
[8]Welch, P.D., Minimality arguments in the infinite time Turing degrees, Sets and proofs, Proceedings of the ASL European Meeting 1997 (Cooper, S.B. and Truss, J.K., editors), London Mathematical Society Lecture Notes in Mathematics, vol. 258, Cambridge University Press, April 1999, pp. 425–436.Google Scholar