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


Wikipedia SHT

Question about SHT

Question' about SHT

  • $\begingroup$ What are $s,s_1,s_2$? (in the definition of $L$) $\endgroup$
    – nir shahar
    May 2 at 17:28
  • $\begingroup$ 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). $\endgroup$ May 2 at 17:37
  • $\begingroup$ Then what are $f$ and $g$? $\endgroup$
    – nir shahar
    May 2 at 17:53
  • $\begingroup$ 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$ $\endgroup$ May 2 at 18:02
  • $\begingroup$ I understood that, but what is their role in the proof if they don't represent the space needed? $\endgroup$
    – nir shahar
    May 2 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.