Gfilui

This may be an easy question or it may be related to a well known open problem in Computer Science.

Let $alpha>0$. We say that $alpha$ is computed in time $T(n)$ if there is a Turing machine which for every $n>0$ written in binary produces a finite binary approximation of $alpha$ with error bounded by $frac 12^n$.

Question. Is there a real number $alpha$ which can be computed in time $2^2^cn$ for some $c>1$ but cannot be computed in time $2^d2^n$ for any $d>1$?

Yes. First use the Time Hierarchy Theorem to find a problem in $DTIME(2^2cdot 3^2^n) = DTIME((2^3^2^n)^2)$ but not in $DTIME(2^3^2^n)$. Let $f(k)$ be the answer (1 for yes, 0 for no) to the k-th instance of this problem. Here the k-th instance is going to correspond to an instance of this problem of size $n=log_2(k)$. So $f(k)$ is computable in time $$2^2cdot 3^2^log__2(k) = 2^2 cdot 3^k$$ but not in time $$2^3^2^log__2(k) = 2^3^k$$ and thus also not in time $2^d2^k$ for any d > 1.

Finally let $alpha$ be the real number whose binary expansion is $sum_i=1^infty f(i)frac12^i$. In order to compute the $alpha$ within $< frac12^n$, you need to know the first n digits, which is the same as computing $f(1), f(2), ... , f(n)$.