Infinite time extensions of Kleene’s $${\mathcal{O}}$$
Ansten Mørch Klev · Archive for Mathematical Logic · 2009
Using infinite time Turing machines we define two successive extensions of Kleene’s $${\mathcal{O}}$$ and characterize both their height and their complexity. Specifically, we first prove that the one extension—which we will call $${\mathcal{O}^{+}}$$ —has height equal to the supremum of the writable ordinals, and that the other extension—which we will call $${\mathcal{O}}^{++}$$ —has height equal to the supremum of the eventually writable ordinals. Next we prove that $${\mathcal{O}^+}$$ is Turing computably isomorphic to the halting problem of infinite time Turing computability, and that $${\mathcal{O}^{++}}$$ is Turing computably isomorphic to the halting problem of eventual computability.