Computably dominated degrees

The nodes $T(0)$ and $T(1)$ are incompatible, so they differ at some position $i$. If $\Phi_e(i)\converge = T(0)(i)$, let $S$ be the full subtree above $T(1)$; otherwise, the full subtree above $T(0)$. In the first case, every $X \in [S]$ extends $T(1)$, so $X(i) = T(1)(i) \neq \Phi_e(i)$. In the second case, every $X \in [S]$ has $X(i) = T(0)(i)$, which differs from $\Phi_e(i)$ or $\Phi_e(i)$ diverges.

Case 1: there are a node $\sigma = T(\rho)$ and an input $x$ such that $\Phi^\tau_e(x)\diverge$ for every node $\tau \succeq \sigma$ of $T$. Let $S$ be the full subtree above $\sigma$. If $X \in [S]$ had $\Phi^X_e(x)\converge$, with use $u$, then a node $\tau$ of $S$ that is a prefix of $X$ of length at least $u$ would satisfy $\Phi^\tau_e(x)\converge$, and $\tau \succeq \sigma$ is a node of $T$. So $\Phi^X_e(x)\diverge$ for all $X \in [S]$.

Case 2: for every node $\sigma$ of $T$ and every input $x$, there is a node $\tau \succeq \sigma$ of $T$ with $\Phi^\tau_e(x)\converge$. Define $S(\rho) = T(\mu_\rho)$ by induction on $\rho$. Let $\mu_\varepsilon$ be the first string found, in a computable search, with $\Phi^{T(\mu_\varepsilon)}_e(0)\converge$. Given $\mu_\rho$, for $i \in \{0, 1\}$, let $\mu_{\rho i}$ be the first string $\mu \succeq \mu_\rho\, i$ found with $\Phi^{T(\mu)}_e(|\rho| + 1)\converge$. The searches terminate by the hypothesis of Case 2, applied to the nodes $T(\varepsilon)$ and $T(\mu_\rho\, i)$, and the nodes $\tau \succeq T(\mu_\rho\, i)$ of $T$ are of the form $T(\mu)$ with $\mu \succeq \mu_\rho\, i$. So $S$ is computable. Since $\mu_{\rho i} \succeq \mu_\rho\, i$, the map $\rho \mapsto \mu_\rho$ preserves both the prefix relation and incompatibility, so $S$ is an f-tree, and it is a subtree of $T$.

By construction, $\Phi^{S(\rho)}_e(|\rho|)\converge$ for every $\rho$. Let $g(n) = \max \{ \Phi^{S(\rho)}_e(n) : |\rho| = n \}$, a computable function. Let $X \in [S]$ and $n \in \nat$. Some $\rho$ of length $n$ has $S(\rho) \prec X$, so $\Phi^X_e(n) = \Phi^{S(\rho)}_e(n) \leq g(n)$. Hence $\Phi^X_e$ is total and dominated by $g$.

Build computable f-trees $T_0, T_1, \dots$, each a subtree of the previous one. Let $T_0$ be the identity. Given $T_{2e}$, let $T_{2e+1}$ be given by Lemma 2.2 for $T_{2e}$ and $e$. Given $T_{2e+1}$, let $T'$ be given by Lemma 2.3 for $T_{2e+1}$ and $e$, and let $T_{2e+2}$ be the full subtree of $T'$ above $T'(0)$. Each step replaces the tree by a subtree whose root $T_{k+1}(\varepsilon)$ strictly extends $T_k(\varepsilon)$: this holds for the full subtrees used at the odd steps, and is enforced at the even steps by passing to $T'(0)$.

The roots form a chain $T_0(\varepsilon) \prec T_1(\varepsilon) \prec \cdots$ of increasing lengths; let $X$ be their union. For each $k$, the roots $T_j(\varepsilon)$, $j \geq k$, are nodes of $T_k$ and prefixes of $X$, so $X \in [T_k]$. Since $X \in [T_{2e+1}]$, $X \neq \Phi_e$; so $X$ is not computable. Since $X \in [T_{2e+2}] \subseteq [T']$, either $\Phi^X_e$ is partial or it is dominated by a computable function. So $X$ is computably dominated.

For the bound, the construction makes two kinds of choices. At odd steps, it asks whether $\Phi_e(i)\converge = T(0)(i)$, a $\Sigma^0_1$ question. At even steps, it asks whether Case 1 holds, a $\Sigma^0_2$ question about an index of the computable tree; if so, a witness $(\rho, x)$ is found with $\emptyset''$ by asking, for each candidate, the $\Pi^0_1$ question that defines Case 1. Each new tree is then computable from these answers, uniformly. So the sequence of indices of the trees, and $X$, are computable in $\emptyset''$.

($\Rightarrow$) The functional that, on input $n$ and with any oracle $Z$, computes $\ell(n)$ and $\theta(n)$, reads $Z \uh \ell(n)$ and outputs $\theta(n)(Z \uh \ell(n))$, is total on every oracle.

($\Leftarrow$) Fix $n$. The set $T_n = \{ \sigma : \Phi^\sigma_e(n)[|\sigma|]\diverge \}$ is a computable tree. A path $Z$ of $T_n$ would satisfy $\Phi^Z_e(n)\diverge$ by Proposition 1.5 of “Computation relative to an oracle”, which is excluded. By Weak König's lemma, $T_n$ is finite, so there is a length $\ell$ such that every string $\sigma$ of length $\ell$ has $\Phi^\sigma_e(n)[\ell]\converge$. Let $\ell(n)$ be the least such $\ell$, found by a computable search, and let $\theta(n)(\sigma) = \Phi^\sigma_e(n)[\ell(n)]$ for $|\sigma| = \ell(n)$, with value replaced by $0$ if it is not in $\{0, 1\}$. Then $Y(n) = \Phi^X_e(n) = \theta(n)(X \uh \ell(n))$.

($\Rightarrow$) Let $Y = \Phi^X_e$, and let $t(n)$ be the least $s$ such that $\Phi^{X \uh s}_e(n)[s]\converge$. It is an $X$-computable total function, so a computable function $g$ dominates it. Let $\ell = g$ and let $\theta(n)(\sigma) = \Phi^\sigma_e(n)[g(n)]$ for $|\sigma| = g(n)$, replaced by $0$ if it diverges or is not in $\{0, 1\}$. Since $t(n) \leq g(n)$, the computation with oracle $X \uh g(n)$ converges within $g(n)$ steps to $Y(n)$, so $Y(n) = \theta(n)(X \uh g(n))$.

($\Leftarrow$) Suppose that $X$ is not computably dominated, and let $f \leq_T X$ be a function dominated by no computable function. Let $F(n) = \max_{m \leq n} f(m)$. Fix an enumeration of the pairs $(\ell_e, \theta_e)$ of partial computable functions. Define $Y$ on inputs $n = \langle e, k \rangle$ as follows. If $\ell_e(n)$ and $\theta_e(n)$ converge within $F(n)$ steps, and $\theta_e(n)$ codes a function on $\{0, 1\}^{\ell_e(n)}$, let $Y(n) = 1 - \theta_e(n)(X \uh \ell_e(n))$; otherwise let $Y(n) = 0$. Then $Y \leq_T X$. Suppose $Y \leq_{tt} X$ via total $(\ell_e, \theta_e)$. Let $c(n)$ be the number of steps after which both $\ell_e(n)$ and $\theta_e(n)$ have converged; $c$ is computable. If $F(\langle e, k \rangle) \geq c(\langle e, k \rangle)$ for some $k$, then $Y(\langle e, k \rangle) = 1 - \theta_e(\langle e, k \rangle)(X \uh \ell_e(\langle e, k \rangle))$, contradicting the reduction. So $F(\langle e, k \rangle) < c(\langle e, k \rangle)$ for every $k$. For each $m$, let $k(m)$ be the least $k$ with $\langle e, k \rangle \geq m$, and $G(m) = c(\langle e, k(m) \rangle)$. Then $G$ is computable and $G(m) > F(\langle e, k(m) \rangle) \geq f(m)$ for every $m$, so $G$ dominates $f$, a contradiction.