Limit computability

We prove the unrelativized statement; the proof relativizes. Fix a c.e. approximation $(\emptyset'_s)$ of $\emptyset'$, for instance $\emptyset'_s = \{ e : \Phi_e(e)[s]\converge \}$.

($\Rightarrow$) Let $A = \Phi^{\emptyset'}_e$. Define $A_s(x) = \Phi^{\emptyset'_s}_e(x)[s]$ if this computation converges with a value in $\{0, 1\}$, and $A_s(x) = 0$ otherwise. The sequence $(A_s)$ is uniformly computable, by Proposition 1.5. Fix $x$, and let $u$ be the use of the computation $\Phi^{\emptyset'}_e(x)$ and $t$ a stage at which it converges. Since only finitely many elements below $u$ enter $\emptyset'$, there is $s_0$ with $\emptyset'_s \uh u = \emptyset' \uh u$ for all $s \geq s_0$. For $s \geq \max(s_0, t)$, the computation with oracle $\emptyset'_s$ agrees with the computation with oracle $\emptyset'$ on all the cells it reads, so by monotonicity and the use principle $\Phi^{\emptyset'_s}_e(x)[s]\converge = A(x)$, and $A_s(x) = A(x)$.

($\Leftarrow$) Let $(A_s)$ be a $\Delta^0_2$ approximation of $A$. The relation

is c.e., hence computable in $\emptyset'$ (Proposition 2.7). To compute $A(x)$ with oracle $\emptyset'$, search for the least $y$ with $\neg C(x, y)$, that is, such that the approximation of $x$ does not change after stage $y$, and output $A_y(x)$. Such a $y$ exists since the approximation of $x$ eventually stabilizes, and then $A_y(x) = \lim_s A_s(x) = A(x)$.

1. An $X$-c.e. approximation of $Y$ is an $X$-computable $\Delta^0_2$ approximation; apply the relativized limit lemma.
2. If $\emptyset''$ were c.e., it would be computable in $\emptyset'$ by item 1, contradicting $\emptyset' <_T \emptyset''$.

1. $A(x) = A_{f(x+1)}(x)$, since $f(x+1) \geq m(x+1)$ and the bits below $x + 1$ do not change after stage $m(x+1)$.
2. For a c.e. approximation, once $A_s \uh x = A \uh x$, no element below $x$ enters later, since all elements of $A$ below $x$ are already in $A_s$ and elements never leave. So $m(x)$ is the least $s$ with $A_s \uh x = A \uh x$, which is found with oracle $A$ by testing $s = 0, 1, \dots$. Conversely $A \leq_T m$ by item 1.

If $X \geq_T \emptyset'$, then $X$ computes $m$ by Proposition 4.5. Conversely, a function dominating $m$ computes $\emptyset'$ by the same proposition, and if $X$ computes it, so does $X$.

To compute $c(x)$ from $A$, read $A \uh x$ and search for the least $s \geq x$ with $A_s \uh x = A \uh x$.

Let $f$ dominate $c$. For each $x$, let $M(x)$ be the largest $y \leq x$ such that $A_t \uh y = A_x \uh y$ for every $t$ with $x \leq t \leq f(x)$. The function $M$ is $f$-computable: it only involves the finitely many sets $A_t$, $x \leq t \leq f(x)$.

Claim 1: $A_x \uh M(x) = A \uh M(x)$. Since $x \leq c(x) \leq f(x)$, the stage $t = c(x)$ is among those considered, and $A_{c(x)} \uh x = A \uh x$. With $y = M(x) \leq x$, we get $A_x \uh y = A_{c(x)} \uh y = A \uh y$.

Claim 2: $M(x) \to \infty$. Fix $n$, and let $s_n$ be such that $A_t \uh n = A \uh n$ for all $t \geq s_n$. For $x \geq \max(n, s_n)$, all $A_t$ with $t \geq x$ agree with $A$ below $n$, so $M(x) \geq n$.

To decide whether $n \in A$ with oracle $f$, search for $x$ with $M(x) > n$, which exists by Claim 2, and answer $A_x(n)$, which is correct by Claim 1.