Simple ordinal question Sorry I asked this question as a comment on other thread. I thought I would better ask it as a separate question since I have seen this notation more than few times now and I am not quite certain what it means (I would just like to be "sure" of whether it corresponds with what I describe below or not .... which I had thought of separately before). Since I have had this confusion for some months now after seeing this notation, I would appreciate an answer and be pretty happy to have it cleared.
First the definition .... for any (countable) ordinal $\alpha$ define $PS[\alpha]$ to be the minimal among the following: "smallest ordinal that can't be computed using an (ordinary) program which has access to some arbitrary well-ordering of $\mathbb{N}$ with order-type $\alpha$."
What I mean is that if you take some specific bijection between $\alpha$ and $\mathbb{N}$ (denote the bijection as $f$).Then if you denote $PS_f[\alpha]$ as the smallest ordinal that can't be computed using an (ordinary) program that has access to well-order relation corresponding to the bijection, we define:
$PS[\alpha]=$minimal value $PS_f[\alpha]$ among all possible bijections $f$
Now define:
$\beta_0=\omega_{CK}$
$\beta_{\alpha+1}=PS[\beta_\alpha]$
When $\alpha$ is a limit, $\beta_\alpha$ is defined as supremum of all smallers $\beta_x$'s (where $x<\beta$).
I hope this wasn't too long-winded.Now my question simply is how does $\beta_n$ correspond to notation $\omega^{CK}_n$. I mean obviously $\beta_0=\omega^{CK}_1$, what about beyond this?
 A: Let me first rephrase your question a bit more clearly (if this isn't what you're asking, let me know). It sounds like you are asking about Muchnik (weak) reducibility of ordinals: if $\alpha,\beta$ are countable ordinals, we say $\alpha\le_w\beta$ if any copy of $\beta$ computes a copy of $\alpha$, where by "copy" we mean a relation on the naturals which is isomorphic to $\beta$ (resp. $\alpha$). 
It's a theorem of Sacks that the following are equivalent, for a countable ordinal $\theta$:


*

*$\theta$ is admissible.

*For some real $r$, $\theta$ is the least ordinal with no $r$-computable copy.
This immediately shows that $\beta_n=\omega_{n+1}^{CK}$ for finite $n$. At transfinite levels, though, interesting things happen: your $\beta_\omega$ is just $\sup_{n\in\omega}(\omega_n^{CK})$, but this ordinal is not admissible (being an admissible limit of admissibles is stronger than just being admissible) -  this is because the map sending $\eta$ to the $\eta$th admissible is $\Sigma_1$, and in particular any admissible limit of admissibles $\alpha$ satisfies $\alpha=\omega_\alpha^{CK}$. So in fact we get the opposite pattern: $$\beta_\omega<\beta_{\omega+1}=\omega_\omega^{CK}<\beta_{\omega+2}=\omega_{\omega+1}^{CK}<...$$ Basically, what we're seeing here is that the "obvious" limit stage definition actually plays badly with the concepts at hand.
EDIT: Addressing the comments below:


*

*The definition of $\omega_\alpha^{CK}$ that I'm using is "the $\alpha$th admissible" - that is, the unique ordinal $\gamma$ such that $L_\gamma\models KP$ and $\{\beta<\gamma: L_\beta\models KP\}$ has ordertype $\alpha$. Note that $L_\omega\models KP$, so $\omega_0^{CK}=\omega$ and $\omega_1^{CK}$ is what it should be under this definition.

*The "higher off-by-one" pattern above goes always thus, except at admissible limits of admissibles (also called "recursively inaccessibles"). When $\theta$ is an admissible limit of admissibles, we get $\beta_\theta=\omega_\theta^{CK}$.

Let me end by mentioning a couple hopefully interesting facts. In the interest of full disclosure, this is part of my work - see respectively this paper (which was partly motivated by this work of Hamkins and Li) and this paper.


*

*Muchnik reducibility is nonuniform - this is really what "weak" is referring to. We could also ask about Medvedev (strong) reducibility, $\le_s$: for countable ordinals $\alpha,\beta$ we write $\alpha\le_s\beta$ iff there is some single Turing functional $\Phi_e$ such that whenever $B$ is a copy of $\beta$, $\Phi_e^B$ is a copy of $\alpha$. This is extremely different; for example, we always have $\alpha\le\beta\implies\alpha\le_w\beta$, so Muchnik reducibility linearly (pre)orders the countable ordinals, but there is a club of countable ordinals which are pairwise $\le_s$-incomparable! Similarly, in general the set of ordinals Medvedev reducible to a given one is not closed downwards.

*Muchnik (and Medvedev) reducibility makes sense in a broader context: it's really about countable structures, not just ordinals per se, and as such is part of computable structure theory. And even the countability restriction can be dropped, by looking at computations in generic extensions. While on the face of things this looks like a horrible intrusion of set theory, Shoenfield's absoluteness theorem then implies that we actually get something not too terrible; in particular, for all countable structures $\mathcal{A},\mathcal{B}$, the following are equivalent:


*

*There is a generic extension of the universe in which $\mathcal{A}\le_w\mathcal{B}$.

*In every generic extension of the universe in which $\mathcal{A},\mathcal{B}$ are each countable, we have $\mathcal{A}\le_w\mathcal{B}$.
This lets us continue Sacks' theorem into the uncountable: an ordinal $\alpha$ is admissible iff there is some real $r$ in some generic extension of the universe such that $\alpha$ is the least ordinal with no $r$-computable copy. And in fact the Medvedev version of this picture - which, by Shoenfield again, is similarly well-behaved - is a necessary (so far as I know) tool in proving the result mentioned in the previous bulletpoint.
