13
$\begingroup$

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$?

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

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)$.

$\endgroup$
0

Your Answer

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