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.

  • $\begingroup$ I'd be thankful for the downvoter to explain the reason behind their downvote so that I could improve my question. $\endgroup$ – Wojowu Dec 24 '15 at 9:15

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.