2
$\begingroup$

This page contains the following text (see the section “Higher-order busy beaver functions”):

At least, under any reasonable formulation of the notion of a higher-order Turing machine, well-orderings of ordinal type $\omega_1^{\text{CK}}$ are uncomputable even with respect to an $x$-th oracle Turing machine for any recursive ordinal $x$.

What about the other direction? That is, assuming that $\alpha$ is an arbitrarily large ordinal less than $\omega_1^{\text{CK}}$ and we know what it means for a Turing machine to have an oracle for a copy of some ordinal, is it necessarily true that for any copy $T$ of $\omega_1^{\text{CK}}$ the halting problem for the family of $\alpha$-th-order Turing machines is computable by some Turing machine that has access to an oracle for $T$?

I am inclined to think that the answer is “no, it is not true” (if the answer is “yes, it is true”, I would be surprised by how strong $\omega_1^{\text{CK}}$ is), but I cannot find the proof.

$\endgroup$

1 Answer 1

2
$\begingroup$

Your guess is right. In fact, much more is true:

For any countable linear order $\mathcal{L}$ whatsoever and any noncomputable set $X$, there is an isomorphic copy of $\mathcal{L}$ with domain $\mathbb{N}$ which does not compute $X$ (or, if you prefer, whose atomic diagram does not compute $X$).

This was proved by Linda Richter (Theorem 3.3 in Degrees of structures). In particular, there are copies of $\omega_1^{CK}$ which don't even compute $\emptyset'$. See Knight, Degrees coded in jumps of orderings for further results along these lines.

$\endgroup$
3
  • $\begingroup$ Is there some copy of δ1 = ω1^CK that does compute the k-th jump for any k < δ1? $\endgroup$
    – user21820
    Commented May 9 at 8:48
  • $\begingroup$ @user21820 Yes, but this has nothing to do with $\omega_1^{CK}$: any nontrivial (in a particular sense) structure has copies computing arbitrarily complicated reals. In fact, Julia Knight showed (in the last section of the linked paper) a stronger result, that if $\mathcal{A}$ is nontrivial then the set degrees of copies of $\mathcal{A}$ is closed upwards under Turing reducibility. $\endgroup$ Commented May 9 at 14:40
  • $\begingroup$ Hmm I see, thanks! $\endgroup$
    – user21820
    Commented May 9 at 14:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .