2
$\begingroup$

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:

$\endgroup$
  • $\begingroup$ Just so you know, all the "strength of function in terms of ordinals" claims are almost completely unsubstantiated - there is no formal way in which they are true. For the record, I am in large part a cause for the claim in quote 3, but since then I have learnt better and can assure you $\Sigma_2$ in no sensible way reaches $\omega_2^{CK}$. $\endgroup$ – Wojowu Sep 4 '18 at 7:25
  • $\begingroup$ Regarding quote 2, "oracle for $\omega_1^{CK}$" is any oracle which encodes a well-order of order type $\omega_1^{CK}$. 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 we will no larger ordinals will be computable with this oracle. $\endgroup$ – Wojowu Sep 4 '18 at 7:27
  • $\begingroup$ Again, we run into the problem of what "[a function] reaches [an ordinal]" is supposed to mean, but for the former, there is a reasonable answer of "doesn't reach $\omega_2^{CK}$", because $\omega$-th order halting oracle doesn't let us compute ordinals greater than $\omega_1^{CK}$. For $BB_{\omega_1^{CK}}$ we reach another issue of how exactly we would define $\omega_1^{CK}$-th order oracle - there is no canonical way to do that (for recursive ordinals, we can show all (computable) choices give essentially the same oracle, but that fails for nonrecursive ordinals) $\endgroup$ – Wojowu Sep 4 '18 at 7:53
  • $\begingroup$ @Wojowu: —> we run into the problem of what "[a function] reaches [an ordinal]" is supposed to mean <— In this context, I think that this is the Busy Beaver function for Turing machines with an oracle which encodes a well-order of order type $\omega_n^\text{CK}$. But I still don't understand how to define these oracles. Even if there is no canonical way to do this, I think that any mathematically reasonable way would be enough. $\endgroup$ – lyrically wicked Sep 4 '18 at 8:29
  • $\begingroup$ @Wojowu Can you give a specific reference (or references) for the result you mentioned in the second comment below the question? Also am I right in assuming that $\omega_2^{CK}=\omega_1^{CK}(\omega_1^{CK})$ is considered as definition of $\omega_2^{CK}$? Here I am assuming the following def. for $\omega_1^{CK}(\alpha)$ from an answer in linked thread (in question): "For $\alpha$ an ordinal, we write $\omega_1^{CK}(\alpha)$ for the least ordinal $\beta$ for which there is some copy of $\alpha$ (= binary relation on $\omega$ with ordertype $\alpha$) which does not compute a copy of $\beta$." $\endgroup$ – SSequence Sep 6 '18 at 9:23
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ > the point is that nothing beyond $\omega_2^{CK}$ is necessarily computable from a copy of $\omega_1^{CK}$ < I am not sure I understand the word "beyond" here correctly. Does it mean "below" or "above"? $\endgroup$ – lyrically wicked Feb 3 '19 at 2:54
  • $\begingroup$ @lyricallywicked above. If $r$ is a real coding a copy of $\omega_1^{CK}$, then every ordinal less than $\omega_1^{CK}$ has a copy computable from $r$ (and no ordinal $\ge\omega_2^{CK}$ is guaranteed to have a copy computable from $r$). $\endgroup$ – Noah Schweber Feb 3 '19 at 3:16
  • $\begingroup$ You mentioned "every ordinal less than $\omega_1^{CK}$" and "ordinal $\ge \omega_2^{CK}$". But where are all ordinals less than $\omega_2^{CK}$? Are their copies guaranteed to be computable? $\endgroup$ – lyrically wicked Feb 3 '19 at 3:38
  • 1
    $\begingroup$ (This then makes phrases like "real coding a copy of" redundant.) In this language, what I said above would be just: "If $r$ is a copy of $\omega_1^{CK}$, then every ordinal $<\omega_2^{CK}$ has an $r$-computable copy; on the other hand, there is a copy $s$ of $\omega_1^{CK}$ which doesn't compute copies of any ordinal $\ge\omega_2^{CK}$." $\endgroup$ – Noah Schweber Feb 3 '19 at 4:32
  • 1
    $\begingroup$ @lyricallywicked I've added a bit about producing a "sufficiently simple" copy of $\omega_1^{CK}$. $\endgroup$ – Noah Schweber Feb 3 '19 at 14:59
0
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ But there is one more subtlety to it in the sense that the choice of well-order relation for $\omega_{CK}$ could change $\beta$. See the second comment by @Wojowu below the question. I am guessing that possibly the phrase "and for suitable choice of this oracle" is meant to reflect this. $\endgroup$ – SSequence Sep 5 '18 at 9:43
  • $\begingroup$ Bumped to correct somewhat misleading phrase "well-ordering of $\omega^2$ (in terms of $\mathbb{N}$)" $\endgroup$ – SSequence Sep 8 '18 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.