Weak and strong computability of real numbers

161 Views Asked by At

Let me adopt the following definitions:

A real number $x$ is weakly computable if it satisfies one of equivalent definitions given here.

A real number $x$ is strongly computable if the binary expansion of $x$ is a computable string (we don't need to worry about nonuniqueness of expansion for dyadics, since then both expansion are computable).

As it was explained to me in comments to this answer, these two notions are not equivalent, at least not in an obvious way, because if $x$ had some extremely good dyadic rational approximations, then we couldn't decide whether the binary expansion will contain $0111...$ or $1000...$. Here is my question:

Are there any known weakly computable reals which aren't strongly computable?

A possible, but unlikely, example is $\gamma$, for which we don't have any estimates on well-approximability (at least I don't know of any) of it. Of course many numbers are known to be strongly computable, and we know this because we can show that rational approximations can't be too good. To name a few examples: $\pi$, $e$, any algebraic number and actually any non-Liouville number.

I was thinking of constructing an example using Busy Beaver sequence to get long trails of ones and zeroes, but I didn't manage to get a number which would be weakly but not strongly computable.

Thanks in advance.

1

There are 1 best solutions below

0
On BEST ANSWER

The notions are equivalent; say we have a real number $x$ that is not a terminating decimal number (a terminating decimal is both strongly and weakly computable), but is weakly computable. Then there is a function $f(n)$ such that for every positive integer $n$, $\frac{f(n)}{n}$ is within $\frac{1}{n}$ of $x$. Let's say that $x$ has a binary expansion of $. d_1 d_2 \ldots d_m 0 0 \ldots 0 1 \ldots$, where the 1 is in the $n$th place. To determine that the first $m$ digits of $x$ are $d_1 d_2 \ldots d_m$, we merely need to evaluate the function $f(j)$ for $j \ge 2^{n+1}$, since then we will have $x < \frac{f(j)+1}{j}$, so $\frac{f(j)}{j} > x - \frac{1}{j} > x - \frac{1}{2^{n+1}} > .d_1 d_2 \ldots d_m + \frac{1}{2^{n+1}}$. So, we will know that $x$ is at least $\frac{f(j)}{j} - \frac{1}{j} > \frac{f(j)}{j} - \frac{1}{2^{n+1}} > .d_1 d_2 \ldots d_m$. A similar argument works if $x$ is of the form $. d_1 d_2 \ldots d_m 1 1 \ldots 1 0 \ldots$.

The problem is, we don't know in advance what value of $j$ to choose. So our algorithm is to choose a $j$, and if it doesn't determine the first $m$ decimal digits, keep increasing $j$ until it does.