Computable domination characterizes truth-table reducibility

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.