The Turing jump $0^{(\alpha)}$ is defined for ordinals $\alpha<\omega_1^{\mathit{CK}}$ with
- $0^{(0)} = \varnothing$,
- $0^{(\alpha+1)}$ is the diagonal halting problem using $0^{(\alpha)}$ as an oracle,
- $0^{(\lambda)}$ for a limit $\lambda$ is the effective join of the $0^{(\lambda_n)}$ for a computable sequence $\lambda_n$ of ordinals with computable notations and $\lambda_n\rightarrow\lambda$.
The set of natural numbers corresponding to ordinal notations in this scheme is denoted by $\mathcal O$ and $\omega_1^\mathit{CK}$ is the supremum of the ordinals encoded in $\mathcal O$. The hyperjump $X\mapsto\mathcal O^X$ allows the sequence in the limit case of the above definition to be $X$-computable.
This suggests the following extension of the Turing jump beyond $\omega_1^\mathit{CK}$:
- $0^{(\omega_1^\mathit{CK})}=\mathcal O$
- $0^{(\omega_{\alpha+1}^\mathit{CK})} = \mathcal O^{0^{(\omega_{\alpha}^\mathit{CK})}}$
- $0^{(\omega_\lambda^\mathit{CK})}$ for a limit $\lambda$ is the effective join of the $0^{(\omega_{\lambda_n}^\mathit{CK})}$ for a $0^{(\omega_{\alpha}^\mathit{CK})}$-computable sequence of ordinals with $0^{(\omega_{\alpha}^\mathit{CK})}$-computable notations for some $\alpha<\lambda$ and $\lambda_n\rightarrow\lambda$.
- Is this construction well-defined? In particular, is it true that the hyperjump of each admissible $\omega_\alpha^\mathit{CK}$ allows us to denote ordinals up to $\omega_{\alpha+1}^\mathit{CK}$, and the definition for the limit case up to $\omega_{\lambda}^\mathit{CK}$?
- What can we say about the ordinals that obtain notations this way? What is their supremum?
The second part of my question is less rigorous and assumes that there are meaningful answers to the above questions. It seems natural to further abstract from the construction described above: Whenever the process we have defined so far reaches a limit, we can take the set of natural numbers corresponding to notations in the scheme defined so far as an oracle for the next ordinal, define another jump operator and enumerate its applications using the already-defined ordinals. If we manage to formalize this creation of new jump operators and their limits in a systematic way, we will again have ordinal stages and this process will have a supremum. At this point we could devise a scheme for creating jump operator schemes, and so on. My question is: Can this abstraction process be formalized in a way that cannot be extended meaningfully beyond its supremum? What would that supremum look like? I've found this paper1 on mastercodes thanks to this site but I don't understand the notation in it and I'm not sure the idea is the same.
Another perspective on this hyper-abstraction process could be a computational one: I might very well be mistaken, but it seems to me that at each individual stage I would be able to find a canonical way to generalize the abstraction to an abstraction on an even higher level. I could write a Turing machine (using oracles) not only computing ordinal notations, but also one computing codes of Turing machines computing ordinal notations, and so on. But could there be a "final" such Turing machine able to carry out all the work I would be doing there?
1Harold T. Hodes: Jumping Through the Transfinite: The Master Code Hierarchy of Turing Degrees, The Journal of Symbolic Logic, Vol. 45, No. 2 (Jun., 1980), pp. 204-220; DOI: 10.2307/2273183, JSTOR
The process you have in mind can be formalized as follows. We define a sequence of Turing degrees (not individual sets of natural numbers) as follows. I'm going to talk about (hyper)jump sequences along well-orderings rather than families of fundamental sequences of ordinals, since the former is ultimately much easier to work with.
I'll use the following definition (although there are many equivalent ones out there). Suppose I have a map $\mathfrak{m}:\mathcal{P}(\omega)\rightarrow\mathcal{P}(\omega)$, which below will be either the jump or hyperjump operator. Given a set $A$ and a well-ordering $R$ of $\omega$ (not just an ordinal, a literal relation on the natural numbers) we let the $\mathfrak{m}$ sequence along $R$ starting with $A$ be the unique set $U$ such that
$$U_k=\begin{cases} A &\mbox{ if $k$ is the $R$-least element},\\ A\oplus \mathfrak{m}(U_l) & \mbox{ if $l$ is the immediate predecessor of $k$ in $R$, and}\\ A\oplus \{\langle i,j\rangle: j<_Rk, i\in U_j\} & \mbox{ if $k$ is an $R$-limit point.}\\ \end{cases}$$
where "$X_n$" is the $n$th column of $X$, namely $\{m: \langle m,n\rangle\in X\}$. Folding $A$ in at each level isn't something we ever have to do, but it cleans things up a bit in my opinion.
It's a good exercise to prove that a unique such $U$ indeed exists. (HINT: transfinite recursion/induction.)
We let $r_0=\bf 0$ be the degree of the computable sets.
Having defined $r_\alpha$, we let $r_{\alpha+1}={r_\alpha}'$.
Now suppose $\lambda$ is a limit and we've defined $r_\alpha$ for all $\alpha<\lambda$. There are now four cases:
Small $\lambda$. suppose there is some $\alpha<\lambda$ such that there is a well-ordering $R$ of $\omega$ which has ordertype $\lambda$ is computable from $r_\alpha$. Fixing some such $\alpha$, some representative $A\in r_\alpha$, and some $R$ as above, we let $r_{\lambda}$ be the degree of the jump sequence starting with $A$ along $R$.
Medium $\lambda$. Suppose the case above doesn't hold, but there is some $\alpha<\lambda$ such that $\lambda=\omega_1^{CK}(\alpha)$. Fixing the least such $\alpha$, we let $r_\lambda=\mathcal{O}^{r_\alpha}$.
Large $\lambda$. Suppose $\lambda$ is neither small nor medium, but there is some $\alpha<\lambda$ and some $r_\alpha$-computable well-ordering $R$ of $\omega$ such that the set of admissible ordinals $<\lambda$ has ordertype $R$. In this case we follow the "small $\lambda$" approach above with hyperjump in place of jump; and as there, we have a crucial - and nontrivial - well-definedness result.
Ginormous $\lambda$. Suppose $\lambda$ is neither small, medium, or large. Then this process ends.
It turns out that the stopping point of this construction - that is, the first ginormous ordinal - is exactly the first recursively inaccessible ordinal, that is, the first ordinal which is both admissible and a limit of admissibles. The proof is basically unwinding the definitions and applying Sacks' connection between computability and admissibility. It's worth noting that the first recursively inaccessible ordinal is galactically larger than the first limit of admissibles, but is in turn cosmically smaller than the first $2$-admissible; see this survey of Madore for some useful information.
More generally, if we replace ${\bf 0}$ with $deg(A)$ for some $A$ in the start of the construction, the stopping point is the least $\kappa$ such that there is an admissible set $\mathbb{M}$ of height $\kappa$ with $A\in \mathbb{M}$ and $\mathbb{M}\models$ "Every set is contained in an admissible set."
Finally, let me end by saying a bit about how "long jump sequences" can be created:
The approach you've taken is in some sense the most direct: we keep writing down concrete operators which get us a bit further each time, and take the sup of what we can get along them as above.
The "mastercodes" approach is more model-theoretic: rather than thinking of operators on reals we think of operators on structures, and the degrees we look at are the degrees of the theories of those structures (or similar objects). This has a surprising advantage of providing canonical representatives of those degrees, namely the actual reals coding the relevant theories themselves.
Finally, there's the "higher type oracle" approach. We can define "$\omega_1^{CK}(\mathfrak{F})$" for a higher type function $\mathfrak{F}$ as the least ordinal with no $\mathfrak{F}$-computable copy via Kleene's theory of computability in higher types. Even relatively concrete choices of $\mathfrak{F}$ get us far beyond the first recursively inaccessible ordinal. Madore's survey I linked to above refers to these frequently.