Eventually infinite time Turing machine degrees: Infinite time decidable reals

Authors
Citation
Pd. Welch, Eventually infinite time Turing machine degrees: Infinite time decidable reals, J SYMB LOG, 65(3), 2000, pp. 1193-1203
Citations number
7
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF SYMBOLIC LOGIC
ISSN journal
00224812 → ACNP
Volume
65
Issue
3
Year of publication
2000
Pages
1193 - 1203
Database
ISI
SICI code
0022-4812(200009)65:3<1193:EITTMD>2.0.ZU;2-T
Abstract
We characterise explicitly the decidable predicates on integers of Infinite Time Turing-machines, in terms of admissibility theory and the constructib le hierarchy. We do this by pinning down zeta, the least ordinal not the le ngth 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 masterc odes for the constructible hierarchy: further that the natural ordinals ass ociated 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 le ast upper bounds of an "eventual jump" hierarchy exist on an initial segmen t.