Is it possible to construct a model of oracle Turing machines that correspond to $\omega_n^\text{CK}$, where $n$ is greater than $1$?

Question

I have found the following quotes. Quote $1$ ( source ):

In computability theory, Turing Machines+BB oracles correspond to the same ordinal as ordinary Turing Machines ($\omega_1^\text{CK}$). In googology, BB oracles correspond to $ \omega_1^\text{CK} \times 2 $ to the FGH.

(note that “BB oracles” here denote the oracles that can compute the Busy Beaver function for the lower-order Turing machines).

Quote $2$ ( source ):

With access to the halting oracle, you still cannot compute ordinals greater than $ \omega_1^\text{CK} $. The set of computable ordinals is, in fact, still the same. However, given an oracle for $ \omega_1^\text{CK} $, we can compute larger ordinals, and in fact the ordinals computable from $ \omega_1^\text{CK} $ are exactly the ones below $ \omega_2^\text{CK} $.

(in this quote, I don’t understand what “an oracle for $\omega_1^\text{CK}$” means).

Quote $3$ ( source ):

Adam Goucher admited he was wrong when he first wrote about strength of $\Sigma_2(n)$. It is actually $\omega_2^{CK}$, well over $\omega_1^{CK} \times 2$.

(note that $\Sigma_2(n)$ here denotes the Busy Beaver function for the second-order oracle Turing machines, that is, Turing machines equipped with an oracle that can compute the Busy Beaver function for the first-order Turing machines).

It seems like Quote $3$ contradicts Quote $1$, and the question is: is it possible (if yes, then how?) to construct a model of Turing machines that correspond to $ \omega_n^\text{CK} $ in computability theory, assuming that $n$ can be extended to any natural number greater than $1$? What function would the oracles of such machines compute?

EDIT

Quote $4$ ( source ):

The first two admissible ordinals are ω and $\omega _{1}^{\mathrm {CK} }$ (the least non-recursive ordinal, also called the Church–Kleene ordinal). Any regular uncountable cardinal is an admissible ordinal.

By a theorem of Sacks, the countable admissible ordinals are exactly those constructed in a manner similar to the Church-Kleene ordinal, but for Turing machines with oracles.

Can anyone explain how exactly such construction is done? I cannot find any accessible explanation online.

There are relatively similar questions, but they do not address the described problem:

• Is there a second Church-Kleene ordinal?
• What classification of countable ordinals above $\omega _{1}^{\mathrm {CK} }$ exists?

Answer 1

Throughout, by "structure" I mean "countable structure in a computable language." I'm also assuming you're comfortable both with Turing reducibility $\le_T$ - which lets us avoid unnecessary verbiage about machines and oracles - and with the idea of reals coding copies of structures (see SSequence's answer, specifically the $\omega\cdot2$ example).

---

• We begin with the computability side. For $r$ a real, we let $\omega_1^{CK}(r)$ be the smallest ordinal with no $r$-computable copy; equivalently, the supremum of the ordinals which do have $r$-computable copies. For a structure $\mathcal{A}$ we let $\omega_1^{CK}(\mathcal{A})$ be the smallest ordinal not computed by some$^1$ copy of $\mathcal{A}$; precisely, $$\omega_1^{CK}(\mathcal{A})=\min\{\omega_1^{CK}(r):r\mbox{ codes a copy of $\mathcal{A}$}\}.$$

  • "$\omega_1^{CK}(r)$" is not how that appears in the literature - rather, you'll see "$\omega_1^r$" - but I strongly prefer it, since it avoids clashing with set-theoretic notation. Note also that we can conflate a real $r\subseteq\omega$ with the structure $\hat{r}$ consisting of the natural numbers with successor and a unary predicate for $r$, and it's easy to check that $\omega_1^{CK}(r)=\omega_1^{CK}(\hat{r})$, so everything lines up nicely.

• Next, we look at the admissibility side. For $\alpha$ an arbitrary ordinal, we let $\omega_\alpha^{ad}$ denote the $\alpha$th admissible ordinal: that is, the $\alpha$th ordinal whose corresponding level of $L$ satisfies KP. Note that this definition has nothing to do with computability theory on the face of it (and in fact, doesn't even require $\alpha$ to be countable!). We'll also write "$\omega_1^{ad}(\beta)$" for the first admissible ordinal $>\beta$; in particular, $\omega_1^{ad}(\omega_\alpha^{ad})=\omega_{\alpha+1}^{ad}$.

  • Nobody uses this notation, since by Sacks' result it's completely redundant. However, distinguishing at this stage in the game between admissibility concerns and computability concerns is I think very helpful, so I hope you'll forgive me the introduction of soon-to-be-stupid notation.

• Now Sacks' result (plus a bit of thought) shows that $$\omega_1^{CK}(\alpha)=\omega_1^{ad}(\alpha)\mbox{ for every countable ordinal $\alpha$}.$$ This is why you never see the "$ad$" notation: it's made completely irrelevant! In particular, "$\omega_\alpha^{CK}$" is just our "$\omega_\alpha^{ad}$."

  • Moreover, Sacks' result immediately implies that $\omega_1^{CK}(\mathcal{A})$, being the minimum of a set of admissible ordinals,is itself admissible.

  • Also, via forcing we can make sense of this for even uncountable $\alpha$. But that's really a side issue.

---

$^1$Note the careful quantification over copies here (and the implicit focus on "optimally simple" copies) in our definition of $\omega_1^{CK}(\mathcal{A})$. This is fundamental: different copies of the same structure can behave very differently, and we need to address this if our definitions are to be interesting at all.

Specifically, we can have very simple structures coded by very complicated reals: e.g. "swapping" $2n$ and $2n+1$ whenever $n\in 0'$ gives a copy of $\omega$ which computes $0'$, and more generally we can get copies of $\omega$ of arbitrarily high complexity. In fact, this (almost) always happens. So in order to say anything interesting, we need to talk about what all copies of a given structure can do.

• Note: this is what Wojowu's comment "Results due to Sacks imply that with such an oracle we can compute all ordinals below $\omega_2^{CK}$, and for suitable choice of this oracle [typo removed] no larger ordinals will be computable with this oracle." Obviously some copies of $\omega_2^{CK}$, when used as oracles, will let us compute a ton of extra junk; the point is that nothing beyond $\omega_2^{CK}$ is necessarily computable from a copy of $\omega_1^{CK}$.

What we're ultimately getting at here is the idea of reducibilities between structures. Here we're looking just at Muchnik (weak) reducibility: $\mathcal{A}\le_w\mathcal{B}$ if every real coding a copy of $\mathcal{B}$ computes some real coding a copy of $\mathcal{A}$. There are other reducibilities too - most immediately, Medvedev (strong) reducibility - but for these sorts of questions we're really in the Muchnik realm, at least for now.

EDIT: An important point here which I think will substantially clarify things is that Muchnik reducibility extends $\le$ - if $\mathcal{A}\ge_w\alpha$ and $\beta<\alpha$ then $\mathcal{A}\ge_w\beta$. In particular this means that $\omega_1^{CK}(\mathcal{A})$ is both the least ordinal without a copy computable from every copy of $\mathcal{A}$, and the supremum of the ordinals which do have copies computable from every copy of $\mathcal{A}$.

EDIT THE SECOND: And here's a way of constructing such a "sufficiently simple" copy of $\omega_1^{CK}$: a copy of $\omega_1^{CK}$ can be computed straightforwardly from Kleene's $\mathcal{O}$, but$^2$ $\mathcal{O}$ is in $L_{\omega_2^{CK}}$ and so every ordinal with a copy computable from $\mathcal{O}$ is $<\omega_2^{CK}$. All of this requires a bit of familiarity with admissible sets and $L_{\omega_1^{CK}}$ in particular; Sacks' book is as usual a good source on the topic.

Answer 2

This really should be a comment, but probably too long for it. Regarding [Quote2], I think it follows from a general and rather well-known result. Let $A \subseteq \mathbb{N}$ be any set such that $A\in HA$ (HA=hyperarithmethic). Then you can't generate $\omega_{CK}$ with a program that has access to the set $A$. If you denote $H$ as halt-set then because $H \in HYP$, one gets the result mentioned in the first half of [Quote2].

I do not have any familiarity with the result personally though (it was mentioned in the first question I asked an year ago).

Also regarding the second half of [Quote2], since you mentioned you don't understand what an "oracle for $\omega_{CK}$ means", here are few comments that might help. I am not good with formal stuff so I hope there isn't an issue in the wording. But formally I think it means having an access to function(or an equivalent set basically) which represents the well-order relation ...... corresponding to the well-ordering of $\omega_{CK}$ in terms of $\mathbb{N}$.

For example, if you defined a function $LE:\mathbb{N}^2 \rightarrow \mathbb{N}$ so that:

$LE(x,y)=1$ if and only if $x \le y$

then $LE$ represent the well-order relation ..... corresponding to well-ordering of $\mathbb{N}$ with order-type $\omega$.

Another example is:

$LE(x,y)=1$ if $x=y$

If $x \ne y$ then:

$LE(x,y)=$ truth value of $x<y$ ---- if $x$ is even and $y$ is even

$LE(x,y)=1$ ---- if $x$ is even and $y$ is odd

$LE(x,y)=0$ ---- if $x$ is odd and $y$ is even

$LE(x,y)=$ truth value of $x<y$ ---- if $x$ is odd and $y$ is odd

If you look at it carefully enough, $LE$ here represents the well-order relation corresponding to well-ordering of $\mathbb{N}$ with order-type $\omega \cdot 2$.

Similarly you can also describe a well-ordering of $\mathbb{N}$ with order-type $\omega^2$ using a pairing function (a function describing a 1-1 correspondence between $\mathbb{N}^2$ and $\mathbb{N}$).

---

Now coming back to the comment in second half of [Quote2]. If you denote $\alpha=\omega_{CK}=\omega^{CK}_1$ and denote, for example, $\beta$ as the smallest ordinal that can't be generated using a program that has access to the well-order relation describing the well-ordering of $\omega_{CK}$ in terms of $\mathbb{N}$. Then I hope you can easily see why the following should all be true (via a positive demonstration of a program that does it):

$\beta > \alpha \cdot 2$

$\beta > \alpha ^ 2$

$\beta > \alpha ^ \alpha$

$\beta > \gamma=sup\{\alpha, \alpha^\alpha, \alpha^{\alpha^\alpha},..... \}$

this goes on...