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

Suppose the search never succeeds. Call a string $\sigma$ of length $m$ bad if the computation with that finite oracle never halts without a query outside $m$. At every length $m$ there is a bad string: otherwise each of the finitely many length-$m$ strings would halt within $m$, and the maximum of their finite running times would make the search succeed. Every prefix of a bad string is bad, since a halting run using only queries below the prefix length would be the same on every extension. Thus the bad strings form a binary tree with nodes at every level. The empty string has bad extensions at arbitrarily large lengths. Whenever a bad string has bad extensions at arbitrarily large lengths, at least one of its two children does too; otherwise the two finite height bounds would bound all its extensions. Recursively take the child labelled $0$ if it has this property, and otherwise the child labelled $1$. This fixed rule yields an infinite path $X$ of bad strings without any choice principle. If ${\mathrm{\Gamma }}^X(n)$ halted, its finite query witness would be contained below some $m$; then the length-$m$ prefix of $X$ would not be bad, a contradiction. This violates everywhere-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$.

With an oracle query to $0^{\mathrm{\prime }}$, define $h(e)=0$ when ${\mathrm{\Phi }}_e^{\mathrm{\varnothing }}(e)$ diverges. Otherwise simulate that program, answering every empty-oracle query negatively, and let $h(e)$ be its least halting stage, counted from its initial configuration. The query guarantees that this simulation terminates when it is undertaken. Thus $h$ is total and $0^{\mathrm{\prime }}$-computable.

If a total computable function $g$ satisfies $h(e)\le g(e)$ for every $e$, an ordinary machine decides $0^{\mathrm{\prime }}$ as follows: compute $g(e)$, simulate ${\mathrm{\Phi }}_e^{\mathrm{\varnothing }}(e)$ through that many transitions (also checking the initial configuration), and answer yes exactly if it halts. Every halting computation is detected because its halting stage is at most $g(e)$; every nonhalting computation is answered no. This would make $0^{\mathrm{\prime }}$ computable from the empty oracle, contrary to [F2].

Therefore this particular total $0^{\mathrm{\prime }}$-computable function $h$ has no total computable pointwise upper bound. By [F3], $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$ by [F1]. Hence ordinary union does not compute the degree join in general; tagged join is relevant.