Basic questions on Turing degrees and the jump operator

Question

I'm trying to understand the notation $0^{(k)}$ (which is related to Turing degrees).

Here's what I understand: we have the equivalence relation on $\mathscr P(\mathbb N)$: $A$ is equivalent to $B$ iff $A\leq_T B$ and $B\leq_T A$. For a set of natural numbers $A$, let $A'=K^A=\{n\in\mathbb N: \phi_n^A(n)\downarrow\}$. (The notation $\phi_n^A(x)\downarrow$ means if we run program number $n$ on input $x$ and use $A$ as an oracle, then it halts.)

$0$ is the equivalence class of any computable set

$0'$ is the equivalence class of the set $K=\{n\in \mathbb N: \phi_n(n)\downarrow\}$

$0''$ is the equivalence class of the set $K'=K^K=\{n\in\mathbb N: \phi_n^K(n)\downarrow\}$

Is this correct so far?

Then $0'''$ should be the equivalence class of $K''=(K^K)^K=\{n\in\mathbb N:(\phi_n^K)^K(x)\downarrow\}$. Is this right? This is harder to process for me. How should I think of $(\phi_n^K)^K(x)\downarrow$? What does it mean intuitively? (Above I described $\phi_n^A(n)\downarrow$ as "if we run program number $n$ on input $n$ and use $A$ as an oracle, then it halts", how to describe $(\phi_n^K)^K(x)\downarrow$ in a similar manner?)

And in general, I guess $0^{(n)}$ is the equivalence class of $K^{(n-1)}$.

Answer 1

Is this correct so far?

Yes.

After that, it looks like you're getting thrown off by the superscript notation. Note that if we write $K^A$ for $A'$, then $A''=(A')'=K^{K^A}$, whereas the notation $(K^K)^A$ is not defined (although it might be reasonable to interpret it as $A''$).

Similarly, instead of $(\phi^K_n)^K$, you should write $\phi^{K^K}_n$, or more clearly, $\phi^{0''}_n$. Here we're considering programs that can query $0''$ as an oracle; these programs not only know which regular programs halt but also which $0'$-oracle programs halt.

We think of $A'$ as "the halting problem relative to $A$", i.e. (the equivalence class of) the set of programs that halt when run on an oracle machine with oracle $A$. In this sense, $0'''$ is the halting problem relative to $0''$. Every time we apply the jump operator we get a class of sets that is more difficult to compute.

Answer 2

$0'''$ is the equivalence class of the halting problem for computations that use oracle $K^K$. This would be written $K^{(K^K)}$, not $(K^K)^K$. (The latter notation hasn't really been defined. Your attempted definition of it uses the notation $(\phi_n^K)^K$, which hasn't been defined.)