Oracle Computability, the Jump, and Turing Degrees

The machine which asks its oracle whether $n$ belongs to it and returns that answer is an $A$-oracle decider for $A$.

For transitivity, simulate the $B$-oracle decider for $A$; answer each query $q\in B$ by the total $C$-oracle decider for $B$. Every inner query terminates and the outer run makes finitely many, so this is a total $C$-oracle decider for $A$.

If $A{\le }_{T}B$, then $A^{\mathrm{\prime }}{\le }_{T}A{\le }_{T}B{\le }_T{B}^{\mathrm{\prime }}$ by the two equivalences and transitivity, so $A^{\mathrm{\prime }}{\le }_T{B}^{\mathrm{\prime }}$.

Interchanging the primed and unprimed representatives gives the reverse implication. Thus either representative pair yields the same comparison.

An $(A\oplus B)$-oracle machine decides $A$ by querying $2n$, and decides $B$ by querying $2n+1$. Hence $[A{]}_T\le [A\oplus B{]}_T$ and $[B{]}_T\le [A\oplus B{]}_T$.

If $A{\le }_{T}C$ and $B{\le }_{T}C$, a $C$-oracle machine deciding $A\oplus B$ tests parity: on $2n$ it runs the decider for $A(n)$, and on $2n+1$ that for $B(n)$. Thus $A\oplus B{\le }_{T}C$.

Step 1.2 says every common upper bound lies above $[A\oplus B{]}_T$; step 1.1 says it is a common upper bound. Representative-independence makes this a statement about degrees.

Compile an $A$-oracle program $e$ into a $B$-oracle program $q(e)$ that answers each simulated $A$-query using the fixed $B$-oracle decider for $A$; $q$ is computable and preserves halting on the same input.

By parameter specialization, compute an index $r(e)$ for the program that on its own input simulates $q(e)$ on $e$. Then $e\in A^{\mathrm{\prime }}$ iff $r(e)\in B^{\mathrm{\prime }}$, so $A^{\mathrm{\prime }}{\le }_T{B}^{\mathrm{\prime }}$.

Repeat the construction of step 2.1 using $B{\le }_{T}A$ to obtain $B^{\mathrm{\prime }}{\le }_T{A}^{\mathrm{\prime }}$. Therefore $A^{\mathrm{\prime }}{\equiv }_T{B}^{\mathrm{\prime }}$.

Let $Q_n$ be the oracle program that queries $A$ at $n$ and halts exactly when the answer is yes. Inserting the numeral $n$ into this fixed program template gives, by the hardwiring compiler in The Turing jump, a total computable index map $q(n)$. Hence $n\in A⟺{\mathrm{\Phi }}_{q(n)}^A(q(n))\downarrow ⟺q(n)\in A^{\mathrm{\prime }},$ so $A{\le }_T{A}^{\mathrm{\prime }}$.

Suppose toward contradiction that an $A$-oracle program $D$ decides $A^{\mathrm{\prime }}$. Build an oracle program $Q$ that, on input $z$, runs $D^A(z)$ and halts exactly when $D$ rejects. Let $e$ be the fixed index of $Q$ in the enumeration of The Turing jump. Since $D$ is correct, $e\in A^{\mathrm{\prime }}⟺{\mathrm{\Phi }}_e^A(e)\downarrow ⟺D^A(e)=0⟺e\mathrm{\notin }{A}^{\mathrm{\prime }},$ a contradiction.

Thus $A^{\mathrm{\prime }}\mathrm{̸}{\le }_{T}A$, while step 1.1 gives $A{\le }_T{A}^{\mathrm{\prime }}$; therefore $A{<}_T{A}^{\mathrm{\prime }}$.

Uniformly compile an $A$-oracle program $e$ into a $B$-oracle program $q(e)$ by replacing each $A$-query with the given total $B$-oracle computation of that bit. Its compilation is effective.

Parameter specialization produces an index $r(e)$ which halts with oracle $B$ on input $r(e)$ exactly when program $e$ halts with oracle $A$ on input $e$. Hence $e\in A^{\mathrm{\prime }}$ iff $r(e)\in B^{\mathrm{\prime }}$.

An oracle machine with oracle $B^{\mathrm{\prime }}$ computes $r(e)$ and queries its membership, deciding $A^{\mathrm{\prime }}$.

Dovetailing the computations ${\mathrm{\Phi }}_i^A(i)$ enumerates exactly $A^{\mathrm{\prime }}$, so $A^{\mathrm{\prime }}$ is $A$-c.e.

Insert the numerals $e,n$ into the fixed oracle-program template which ignores its own input and simulates ${\mathrm{\Phi }}_e^A(n)$. The hardwiring compiler of The Turing jump gives its index $s(e,n)$ by a total computable map, uniformly in $e,n$ and independently of $A$. Therefore $n\in W⟺{\mathrm{\Phi }}_e^A(n)\downarrow ⟺{\mathrm{\Phi }}_{s(e,n)}^A(s(e,n))\downarrow ⟺s(e,n)\in A^{\mathrm{\prime }}\mathrm{.}$

Thus $n\mapsto s(e,n)$ is a total $A$-computable many-one reduction $W{\le }_m^A{A}^{\mathrm{\prime }}$. Since $W$ was arbitrary, the definition of completeness applies.

The recursively defined $0^{(n+1)}$ is precisely the relative halting oracle for $0^{(n)}$, because the local jump convention is diagonal relative halting.

Apply Post's theorem at level $n$ with the identification in step 1.1. Its two equivalences give exactly the displayed claims.

For fixed $n$, effectively search for length $m$ and time $t$ such that every binary string $\sigma$ of length $m$ makes ${\mathrm{\Gamma }}^{\sigma }(n)$ halt by $t$ without querying outside $m$.

If this search never succeeded, the finitely branching tree of strings whose finite-oracle simulation has not supplied such a transcript would have nodes at every length. König's lemma yields an infinite oracle on which $\mathrm{\Gamma }(n)$ never halts, contradicting totality.

Therefore the search halts; let $b(n)$ be its first successful length. The finite exhaustive test makes $b$ computable, and its defining property forces every oracle computation on $n$ to use only positions below $b(n)$.

By definition, ${\mathrm{\Gamma }}^X(n)$ halts on every $n$ and equals ${\chi }_Y(n)$.

The same machine, run with oracle $X$, is consequently a total oracle decider for $Y$. This is exactly $Y{\le }_{T}X$.

Using $0^{\mathrm{\prime }}$, define $h(e)$ to be $0$ if program $e$ does not halt on $e$, and otherwise its least halting stage on $e$. This is total $0^{\mathrm{\prime }}$-computable.

The recursion theorem supplies an index $e$ for a program which on its own input computes $g(e)$ and then performs $g(e)+1$ dummy steps before halting. Hence $h(e)\ge g(e)+1$.

Thus arbitrary computable $g$ fails to dominate $h$. No computable function dominates every total $0^{\mathrm{\prime }}$-computable function, so $0^{\mathrm{\prime }}$ is not computably dominated.

Assume $X$ is computably dominated. For ${\mathrm{\Phi }}^X(n)={\chi }_Y(n)$, let $t(n)$ be the running time of this halting computation. Then $t$ is total and $X$-computable, hence has a computable dominator $b$.

Conversely, suppose every $Y{\le }_{T}X$ is truth-table reducible to $X$. Toward a contradiction, let $f{\le }_{T}X$ be total and not dominated by any total computable function. Fix an effective enumeration $({\mathrm{\Theta }}_e{)}_{e\in \mathbb{N}}$ of the bit-output oracle functionals and a computable pairing function $⟨e,k⟩$.

Truncate ${\mathrm{\Phi }}^Z(n)$ after $b(n)$ steps for every oracle $Z$, returning $0$ if it has not halted with a bit. This is total on every oracle and agrees with ${\mathrm{\Phi }}^X$ because $t(n)\le b(n)$; hence $Y{\le }_{tt}X$.

Let $D(e,k,s)$ mean that, for every $\sigma \in 2^s$, the finite-oracle computation ${\mathrm{\Theta }}_e^{\sigma }(⟨e,k⟩)$ halts within $s$ steps with a bit and without querying a position at least $s$. This is decidable. Define $Y{\le }_{T}X$ by first computing $s=f(k)$ and then setting ${\chi }_Y(⟨e,k⟩)=\{\begin{array}{ll}1-{\mathrm{\Theta }}_e^X(⟨e,k⟩),& D(e,k,s),\\ 0,& \mathrm{\neg }D(e,k,s)\mathrm{.}\end{array}$ When $D(e,k,s)$ holds, the displayed oracle computation halts within the tested bound, so this definition gives a total $X$-computable set.

If ${\mathrm{\Theta }}_e$ is total on every oracle, the compactness search in An everywhere-total functional has a computable use bound yields, for each $k$, some $s$ satisfying $D(e,k,s)$. Thus the least such value $q_e(k)$ is a total computable function. Since $f$ has no computable dominator, some $k$ satisfies $f(k)>q_e(k)$. The predicate $D$ persists at larger bounds, so step 2.2 gives ${\chi }_Y(⟨e,k⟩)=1-{\mathrm{\Theta }}_e^X(⟨e,k⟩)\mathrm{.}$ Hence no everywhere-total bit functional ${\mathrm{\Theta }}_e$ computes $Y$ from $X$.

By Truth-table reduction, step 3.1 says $Y\mathrm{̸}{\le }_{tt}X$, contradicting the assumed universal property because $Y{\le }_{T}X$. Therefore every total $f{\le }_{T}X$ has a computable dominator, so $X$ is computably dominated.

This argument also justifies the function-valued shorthand in the cited source theorem without upgrading the set-valued hypothesis by fiat. Once step 4.1 gives domination, the running time of any natural-valued computation of $f{\le }_{T}X$ has a computable bound $b(n)$. Truncating at that bound gives an everywhere-total natural-valued functional $\mathrm{\Psi }$. Apply An everywhere-total functional has a computable use bound to obtain a computable use bound $u(n)$; then the finite maximum of ${\mathrm{\Psi }}^{\sigma }(n)+1$ over $\sigma \in 2^{u(n)}$ is a computable strict dominator of $f$.

Steps 2.1 and 4.1 establish the two implications.

Let $X=0^{\mathrm{\prime }}$. It is not computably dominated by The halting oracle is not computably dominated.

If every $Y{\le }_{T}X$ were truth-table reducible to $X$, the reverse direction of Computable domination characterizes truth-table reducibility would make $X$ computably dominated.

This contradiction supplies a set $Y{\le }_{T}X$ with $Y\mathrm{̸}{\le }_{tt}X$.

A halting oracle-machine run has finitely many transitions and therefore only finitely many query instructions.

More precisely, An oracle computation has a finite query witness supplies a finite set of queried bits which fixes the whole run and output. Thus no halting computation reads the entire infinite oracle.

Take $A=0^{\mathrm{\prime }}$ and $B=\mathbb{N}\setminus 0^{\mathrm{\prime }}$. Since complementation is computable, $[A{]}_T=[B{]}_T=[0^{\mathrm{\prime }}{]}_T$, and their degree join is $[0^{\mathrm{\prime }}{]}_T$.

But $A\cup B=\mathbb{N}$ is computable, so $[A\cup B{]}_T=[\mathrm{\varnothing }{]}_T$, which cannot equal $[0^{\mathrm{\prime }}{]}_T$. Hence ordinary union does not compute the degree join in general; tagged join is relevant.