patternMinor
Computational Irreducibility
Viewed 0 times
irreducibilitycomputationalstackoverflow
Problem
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.
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.
Solution
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$.
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$.
Context
StackExchange Computer Science Q#85392, answer score: 3
Revisions (0)
No revisions yet.