Eventually Infinite Time Turing Machine Degrees: Infinite Time Decidable Reals
Welch, P. D.
J. Symbolic Logic, Tome 65 (2000) no. 1, p. 1193-1203 / Harvested from Project Euclid
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 $\zeta$, 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$_\zeta$-stables. It also implies that the machines devised are "$\Sigma_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.
Publié le : 2000-09-14
Classification: 
@article{1183746176,
     author = {Welch, P. D.},
     title = {Eventually Infinite Time Turing Machine Degrees: Infinite Time Decidable Reals},
     journal = {J. Symbolic Logic},
     volume = {65},
     number = {1},
     year = {2000},
     pages = { 1193-1203},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183746176}
}
Welch, P. D. Eventually Infinite Time Turing Machine Degrees: Infinite Time Decidable Reals. J. Symbolic Logic, Tome 65 (2000) no. 1, pp.  1193-1203. http://gdmltest.u-ga.fr/item/1183746176/