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

In this proof of the Space Hierarchy Theorem the following langugae 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 TM.

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 constradiction 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...

• "[...] and similar for the case if it is not accepted." Can you spell out the contradiction to $(\langle M' \rangle, 10^k) \not\in L$? – dkaeae Mar 1 at 14:55
• @dkaeae I added an additional explanatory sentence. – StefanH Mar 1 at 15:00
• If $g(n) = o(f(n))$ then $g(n) = o(cf(n))$ for all constant $c > 0$. – Yuval Filmus Mar 1 at 15:08
• @YuvalFilmus How is this related to my question? In my argument I never use little-o, both $M'$ and $M$ are related by $O$ in their space demands, $M'$ used less then half of that of $M$ by construction. – StefanH Mar 1 at 15:11
• I am starting to suspect the Wikipedia proof is bogus. It bases on a proof on Sipser's book (see the article's references), but in the book the description for $L$ is given only indirectly; that is, one constructs a TM $D$ and then sets $L = L(D)$. The Wikipedia proof apparently tries to cuts corners and give an explicit description of $L$, but ends up running into trouble. – dkaeae Mar 1 at 15:31

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

• I am not quite clear where and how you address the $M'$ from my question? Are you saying that $M'$ applied on $(\langle M' \rangle, 10^k)$ takes too much time? – StefanH Mar 1 at 16:11
• I do not address $M'$ because your argument regarding $M'$ is correct, that is, $L$ should not be defined the way it is in the Wikipedia article. Incidentally, the way the construction goes, you can also derive $(\langle M' \rangle, 10^k) \not\in L$ is impossible (because it would imply $(\langle M' \rangle, 10^k) \in L$ due to the definition of $L$). Hence, $M'$ necessarily takes more than $2^{f(|(\langle M' \rangle, 10^k)|)}$ time when given $(\langle M' \rangle, 10^k)$ as input and $(\langle M' \rangle, 10^k) \in L(M')$ (though this is no contradiction to the theorem nor to its proof). – dkaeae Mar 1 at 16:23
• Thanks for your answer, but I doubt that this fixes the proof. If we know something takes $f(\ldots )$ space, after at most $c^{f(\ldots )}$ steps for some $c > 1$ (they choose $c = 2$ in the article to have some concrete value I guess) we know it must run forever because it has entered a loop ($c^{f(\ldots)}$ comes from counting the distinct configurations of the space bounded TM). Hence cannot accept anything after this many steps opposite to what you say in your last sentence of the first paragraph... (and look just at time $\le 2^{f(\ldots)}$ hence is no restriction at all here)... – StefanH Mar 1 at 18:01
• Only it is not required for $M$ to use exactly $f(n)$ space! For the theorem, we require only $O(f(n))$, say $2f(n)$. Thus, $M$ can still run in time $2^{2f(n)} > 2^{f(n)}$ without looping. which should be enough for it to do everything it needs to do (calculate $f(n)$, initialize counters, etc.) besides the actual simulation for $2^{f(n)}$ steps. – dkaeae Mar 1 at 18:21

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.