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 1{2^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$?

  • $\begingroup$ I guess you also intend that the Turing machine take at most $T(n)$ steps on input $n$. $\endgroup$ – Joel David Hamkins Aug 4 '18 at 11:43
  • $\begingroup$ Yes, at most $T(n)$ steps on input $n$. $\endgroup$ – Mark Sapir Aug 4 '18 at 11:57

Yes. First use the Time Hierarchy Theorem to find a problem in $DTIME(2^{2\cdot 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^{2\cdot 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)\frac{1}{2^i}$. In order to compute the $\alpha$ within $< \frac{1}{2^n}$, you need to know the first n digits, which is the same as computing $f(1), f(2), ... , f(n)$.


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.