Define $Tape_M(t, i)$ as the symbol in the $i$-th cell of the tape of Turing machine $M$ with empty input at step $t$.

Does there exist a Turing machine $M$ such that no algorithm can compute $Tape_M(t, i)$ within $o(t)$ (or $o(t/\log(t))$ ) time?

Actually, it is inspired by the celebrated time hierarchy theorem. I believe that it is true but I have trouble proving it. I think diagonalization may be a right direction (like what we do for time hierarchy theorem), but I am not certain how to diagonalize.

  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Dec 12 '17 at 16:58
  • $\begingroup$ @Raphael Edited. I hope it is OK now. $\endgroup$ – Lwins Dec 12 '17 at 17:20

I will assume that the alphabet is binary (not really important), and show that $Tape_M(t,i)$ cannot be computed in $o(t/\log t)$ time for every $M$.

Consider a Turing machine $M$, which on the empty input, loops for all integers $i$ and does the following:

Simulate the $i$'th Turing machine $M_i$ on the input $\left(g(i),i\right)$ for $\frac{g(i)}{\log g(i)}$ steps (the function $g$ will be determined later). If it produced output $r$, then write $\overline{r}$ in the $i$'th cell and never change that cell again (you can move forward on the tape and preform the next iterations on the rest of the tape).

Suppose for the purpose of contradiction that there exists a Turing machine $A$ which computes $Tape_M(t,i)$ in $f(t)=o(t/\log t)$ time. Let $j$ be a large enough index of $A$, i.e. $M_j=A$, such that for $t\ge j$ : $f(t)<t/\log t$ (one can encode Turing machines in such a way that every machine has infinitely many representations, e.g. by allowing redundant zeros at the end). When $M$'s loop reaches $j$, it executes $Tape_M(g(j),j)$, which according to our assumption, halts within $\frac{g(j)}{\log g(j)}$ steps with some symbol $r\in\{0,1\}$. $M$ then writes $\overline{r}$ in the $j$'th cell, and it is never changed again. Now suppose that up until the $j$'th iteration, $M$ used less than $g(j)$ time, then after $g(j)$ steps, $M$ has $\overline{r}$ written in the $j$'th cell, which contradicts the fact that $Tape_M(g(j),j)=r$.

It remains to pick $g$ in such a way that until the $j$'th iteration, $M$ uses less than $g(j)$ time. The time required for $j$ iterations is $T_j=\sum\limits_{i=1}^j \frac{g(i)}{\log g(i)}\le j\frac{g(j)}{\log g(j)}$, assuming $\frac{g(i)}{\log g(i)}$ is monotonically non decreasing. Now, we want to pick $j$ such that $T_j\le g(j)$, which is satisfied when $\frac{jg(j)}{\log g(j)}\le g(j)$, or equivalently $g(j)\ge 2^j$.

| cite | improve this answer | |
  • $\begingroup$ Excellent! However, does allowing an unary representation make the time bound meaningless since reading the input takes at least linear time? Your proof seems to work for binary representation too. $\endgroup$ – Lwins Dec 12 '17 at 23:49
  • $\begingroup$ Good point. The proof does work for the binary case, for some reason I thought that the unary case is the interesting one. $\endgroup$ – Ariel Dec 13 '17 at 6:07

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.