Example of a non-recursive approximable number

Question

A real number $r$ is recursive approximable if there is a computable sequence of rational numbers converging to it. It is a weaker condition than computability, because we don't have control on the speed of convergence. For example, Chaitin's constant is not computable, but is recursive approximable: for the n'th rational numbers, we just take the $n$ first programs, run them for $n$ steps, and look at what we got. In general, for any recursive enumerable set $S$, the number $c_S := \sum_{n \in S} 2^{-n}$ is recursive approximable, but it is computable if and only if $S$ is computable. So do we have an explicit example of non-recursive approximable number? Is a number encoding $0''$ non-recursive approximable?

I don't know a lot about computability theory, so I have no idea how to answer that.

Answer 1

Sorry, I had a sudden illumination. Any number which is recursive approximable is computable with an oracle for the halting problem. Let $P$ the program approximating some number $x$. Then, for some $n \in \mathbb{N}$, to know if $|P(n) - P(m)| < \epsilon$ for all $m \geq n$, we can take the program which will compute $P(n)$, $P(n+1)$, etc, until it arrives at some number whose absolute difference with $P(n)$ is at least $\epsilon$. Because we have the oracle, we can know if this program will stop at some point or not, hence we can know if $|P(n) - P(m)| < \epsilon$ for all $m \geq n$. Therefore, we can check all $n \in \mathbb{N}$ until we obtain such $n$, and then we know that $|P(n)-x| \leq \epsilon$.

From this, we conclude that any number corresponding to a Turing degree which is not smaller than or equal to $0'$ cannot be recursive approximable. In particular, a number encoding $0''$ is not recursive approximable.

Edit: Even better, for a set $S \subseteq \mathbb{N}$, the constant $c_S := \sum_{i \in S} 2^{-i}$ is recursive approximable if and only if the Turing degree corresponding to $S$ is smaller or equal to $0'$. We already proved that it is necessary, so let's show that it is sufficient. Suppose that we have a program $P$ such that $P(n)$ gives us the $n$ first binary digits of $c_S$, if it has access to an oracle for the halting problem. Because to compute $P(n)$ we can only use finitely many instances of the halting problem, we can do the following: let $S$ the program such that $S(n,k) = 0$ if $k > n$ or if $k \leq n$ and the $k$'th instance of the halting problem doesn't stop before the $n+1$'th step. So $S(n,-)$ is an approximation of the oracle. Let $P_n$ be the program obtained when $P$ calls $S(n,-)$ instead of the oracle. Now, for any integers $m,n$, there is some $N > n$ such that $P_N(m)$ stops, because there is some $N$ such that $S(N,-)$ will give the right values for all the instances asked by $P_N(m)$, and so $P_N(m) = P(m)$. Hence, we can take some program $Q$ such that $Q(m,n)$ gives the $m$'th binary digit given by $P_N(m)$, where $N > n$ is such that $P_N(m)$ stops. Finally, we define $R$ such that $R(n)$ gives the concatenation $Q(1,n)Q(2,n)Q(3,n)\ldots Q(n,n)$. Each binary digit will be eventually correct, hence the number converges to $c_S$.