Proof of Space Hierarchy Theorem incompatible with Linear Speed Up Theorem for time

Question

In this proof of the Space Hierarchy Theorem the following language is defined $$ L = \{ (\langle M \rangle, 10^k) : M \mbox{ does not accept } (\langle M \rangle, 10^k) \mbox{ using space } \le f(|\langle M \rangle, 10^k|) \}. $$ And then stated:

Now, for any machine $M$ that decides a language in space $o(f(n))$, $L$ will differ in at least one spot from the language of $M$. Namely, for some large enough $k$, $M$ will use space $\le f(|\langle M \rangle|, 10^k|)$ on $(\langle M \rangle, 10^k)$ and will therefore differ at its value.

I get the diagonalization argument, but what makes me wonder according to the linear speed up theorem for space we have [see for example Hopcroft/Ullman, 71]:

If $L$ is accepted by an $S(n)$ space-bounded Turing machine with $k$ storage tapes, then for any $c > 0$, $L$ is accepted by a $cS(n)$ space-bounded Turing machine.

As shown in the linked wikipedia article $L$ is accepted by a Turing machine using $f(n)$-bounded space, then by linear speed up $L$ is also accepted by some machine $M'$ using at most $\frac{f(n)}{2}$ tape cells. But then we get a contradiction on the inputs $(\langle M' \rangle, 10^k)$, as $M'$ accepts $L$ if $(\langle M' \rangle, 10^k)$ is accepted, then $(\langle M' \rangle, 10^k) \notin L$, contradiction, and similar for the case if it is not accepted. If $(\langle M' \rangle, 10^k)$ is not accepted by $M'$ then $(\langle M' \rangle, 10^k) \in L$ by definition of $L$, but $(\langle M' \rangle, 10^k) \notin L(M') = L$, a contradiction.

My reasoning seems to be fine, but it should not be... what am I missing here? In my argument, the problem is with the speed up and essentially it derives that if speed up is possible, then we can separate $f$ and $cf$ for $0 < c < 1$, i.e., speed up is not possible. The only valid conclusion would be that linear speed up is not possible, but that is certainly not true...

Answer 1

The Wikipedia proof is bogus.

As you have proven, the description for $L$ is incomplete. It should read: $$ L = \{ (\langle M \rangle, 10^k) : M \mbox{ does not accept } x = (\langle M \rangle, 10^k) \mbox{ using space } \le f(|x|) \; \textbf{and time} \; \le 2^{f(|x|)} \} $$

This corrects the proof because now $M$ (or $M'$) can still accept $x = (\langle M \rangle, 10^k)$ and take space $\le f(|x|)$. Actually, $(\langle M \rangle, 10^k) \in L$ has a quite reasonable explanation in that $M$ attempts to simulate $M$, which (as a subroutine) attempts to simulate $M$ again, and so forth and so on, until eventually $2^{f(|x|)}$ steps elapse and the whole procedure is interrupted. Hence, $M$ does not accept $x$ using space $\le f(|x|)$ and time $\le 2^{f(|x|)}$, although it does accept it taking space $\le f(|x|)$ (well, perhaps actually $O(f(|x|))$) and time $> 2^{f(|x|)}$.

As a matter of fact, the purported algorithm for $L$ in the article explicitly states it runs its simulation with a $2^{f(|x|)}$ stopwatch. This is precisely the detail that is missing from the definition of $L$.

Answer 2

First the other answer by dkaeae seems to be perfectly fine regarding that every machine using $o(f)$ space also can get by with $o(2^{o(f)})$ time in the limit (by assumption the machines considered are deciders, hence halt, hence by counting configurations we have no configuration twice). And as we have an infinite of inputs $10^k$ for each machine, we can conclude that no such machine could accept the thus modified $L$. Also the modifications seems to suggest that if $M$ accepts $L$, on input $(\langle M \rangle, 10^k)$ it will need more than $2^{f(|(\langle M \rangle, 10^k)|)}$ time, or even for the machine $M'$ we got by the speed up theorem.

But still this seems somehow nebulous in the sense that why we surely need this blow up in time. The intuition "M applied to itself, applied to itself ..." seems to suggest this time blow up, and that the machine stops and reject inputs $(\langle M \rangle, 10^k)$ as written by dkaeae.

In this post I try to give a more formal reason by employing how machines simulate each other. It helped me in understanding the problem apart from the abstract reasoning as given above and so it might be worthwile to share it here.

Essentially it boilds down to the fact that Turing machines have no restriction on the working tape alphabet, and from this essentially the speed up theorem is derived. But in simulating other machines we always have a logarithmic blow up in the working size alphabet, and as we always have bigger working alphabet by the blank symbol as the input alphabet, if we code machines to be processed by other machines (or simulated) we have to code also the blank symbol by input symbols. This is inherent in the definition of machines we cannot get by with. For example also if we just restrict to the working tape symbols $\{0,1,b\}$ and input $\{0,1\}$ then we have to code the blank symbol $b$ by $\{0,1\}$ to code a machine as input for another. Note that if we restrict our machines to $\{0,1,b\}$ we do not have a speed up theorem anymore.

I might help to look at other proof's. I took one from the classic Ullmann/Hopcroft (1979).

Theorem If $S_2(n)$ is a fully space-constructible function, $$ \inf_{n\to \infty} \frac{S_1(n)}{S_2(n)} = 0, $$
and $S_1(n)$ and $S_2(n)$ are each at least $\log_2 n$ then there is a language in $DSPACE(S_2(n))$ not in $DPSACE(S_1(n))$.

Proof The theorem is proved by diagonalization. Consider an enumeration of off-line Turing machinees with input alphabet $\{0,1\}$ and one storage tape, based on the binary encoding of Section 8.3, but with a prefix of $1$'s permitted, so each TM has arbitrary long encodings. We contruct a TM $M$ that uses $S_2(n)$ space and disagrees on at least one input with any $S_1(n)$ space bounded TM. On input $w$, $M$ begins by marking $S_2(n)$ cells on a tape, where $n$ is the length of $w$. Since $S_2(n)$ is fully space-constructible, this can be done by simulating a TM that uses exactly $S_2(n)$ cells on each input of length $n$. In what follows, if $M$ attempts to leave the marked cells, $M$ halts and rejects $w$ This guarantees that $M$ is $S_2(n)$ space bounded. Next $M$ begins a simulation on input $w$ of TM $M_w$, the TM encoded by binary string $w$. If $M_w$ is $S_1(n)$ space bounded and has $t$ tape symbols, then the simulation requires space $\lceil \log t \rceil S_1(n)$. $M$ accepts $w$ only if $M$ can complete the simulation in $S_2(n)$ space and $M_w$ halts without accepting $x$. Since $M$ is $S_2(n)$ space bounded, $L(M)$ is in $DPSACE(S_2(n))$. $L(M)$ is not in $DSPACE(S_1(n))$. For suppse there were an $S_1(n)$ space-bounded $TM \hat M$ with $t$ tape symbols accepting $L(M)$. By Lemma 12.1 we may assume that $\hat M$ halts on all inputs. Since $\hat M$ appears infinitely often in the enumeration, and $$ \inf_{n\to \infty} \frac{S_1(n)}{S_2(n)} = 0, $$ there exists a sufficiently long $w$, $|w| = n$, such that $\lceil \log t \rceil S_1(n) < S_2(n)$ and $M_w$ is $\hat M$, $M$ has sufficient space to simulate $M_w$ and accept if and only if $M_w$ rejects. Thus $L(M_w) \ne L(M)$, a contradiction.

The bold part tells everything. Even to simulate $M$ on itself we have a blowup in space, and just for $S_1 \in o(S_2)$ we can compensate this blowup in the limit, but we cannot compensate for running times of $c\cdot \dot S_2(n)$, $c > 1$ in particular not for $M$ itself. More space can also lead to more time (or at least the time bound is bigger, this is the base $2^{\ldots}$), hence this is where the time blow up mentioned by dkaeae might come from. Also if we apply space compression, in the simulation we have more tape symbols, hence the compression effect is ''reversed'' by the factor $\lceil \log t\rceil$ in the simulation and the reasoning in the question breaks down; same for $M$ simulating itself.