# Understanding the Space Hierarchy Theorem and its proof

This is what I've learned from the SHT and the sketch of its proof. I would appreciate pointing out any mistake.

• The intuition behind the Space Hierarchy Theorem is that

"there are Turing Machines using s1 space that can perform computations not posible using s2 < s1 space"

s2 < s1 means that s1 uses O(f(n)) space and s2 uses O(g(n)) space and g = o(f) (the magnitude of g is less than the magnitude of f)

• Following the sketch of the proof in wikipedia (claimed to be bogus):

Define language L

L = { T | T(T) = "reject" using O( f|T| ) space and less than $$2^s$$ steps }

// Note: f(n) is space constructible, $$s = f(|T|)$$

Define the following Turing Machine M1 that computes L

M1( T ) =

1. compute s = f( |T| ) the limit of usable space (this calculation can be done, by assumption, also in O( s ) space )
2. simulate T(T) watching that no more of s space and $$2^s$$ steps are used
3. If 2. is violated: return "reject T" (and stop).
4. return the opposite of T(T) (and stop).

By construction language(M1) = L.

M1( M1 ) = "reject" because M1 emulates its input in step 2. and M1(M1) will result in an infinite recursive call that eventually will consume space s.

Since M1( M1 ) = "reject", then M1 $$\not\in$$ L since language(M1) = L (1)

Does M1 uses only O( f(|M1|) ) space? No, or otherwise M1 $$\in$$ L because it would satisfy L conditions (M1(M1)="reject" and M1 uses O((f(|M1|)) space). This would contradict (1).

// Caution: wikipedia says "L is in SPACE( f(n) )"


Thus M1 or any other TM recognizing L uses MORE than O(f(|M1|) space. MORE is k(n) where f(n) = o(k(n)).

In sum, M1 is a TM able to compute a language, using O(k(n)) space, that no machine can compute in f(n) = o(k(n)).

References

Wikipedia SHT

• What are $s,s_1,s_2$? (in the definition of $L$) May 2 at 17:28
• The amount of space needed, but not as a concrete number but as an upper bound. For instance, O(n) space is less space than $O(n^2)$ space. I understand that the SHT says that a TM limited to $O(n^2)$, is more powerful than those limited to $O(n)$. (Seems obvious, but not so obvious is the proof). May 2 at 17:37
• Then what are $f$ and $g$? May 2 at 17:53
• Two functions, as well as k, of "different order of magnitude" This is expressed by the "little o notation": $g(n) = o(f(n))$ == $lim \frac{g(n)}{f(n)} = 0$ May 2 at 18:02