4
$\begingroup$

The Space Hierarchy Theorem states that

If $f(n)$ is space contructible, then for any $g(n) \in o(f(n))$ we have $SPACE(f(n)) \neq SPACE(g(n))$

An example of a SHT proof can be found here or here but they are generally based on the same idea differing only in technical details. We would like to find a language $L$ such that $$L \in SPACE(f(n))$$ and $$\forall{g \in o(f(n))}: L \notin SPACE(g(n)).$$ So the proof claims that a language that fulfills these constraints is the following (for the sake of this post we do not care about $M$s whose description is too short for the asymptotic behavior of their space complexity to kick in) $$ L = \{ \langle M \rangle: M\text{ rejects }\langle M \rangle\text{ using }\leq f(|\langle M \rangle|)\text{ space}\} $$ and it describes a TM that accepts this language in $f(n)$ space. Then it tries to prove the second constraint using diagonalization argument in the following way:

Suppose there is $M'$ such that $L(M') = L$ and $M'$ is of $g(n) \in o(f(n))$ space complexity. Then

  • If $M'$ accepts $\langle M' \rangle$ then (from assumption) $\langle M'\rangle \in L$ then (from definition of $L$) $M'$ rejects $\langle M' \rangle$
  • If $M'$ rejects $\langle M' \rangle$ then (from assumption) it does so in $o(f(n))$ space then (from definition of $L$) $\langle M'\rangle \in L$ then (from assumption) $M'$ accepts $\langle M' \rangle$

Contradiction. Therefore such $M'$ does not exist.

So what bothers me is that in the argument above we could just as well take a TM $M''$ that runs in $f(n)$ space and the argument would still hold, therefore breaking the first constraint.

$\endgroup$
1
$\begingroup$

Apparently, there is a misunderstanding of the original proof from Sipser's book Introduction to the Theory of Computation that's been erroneously duplicated in a couple of sources including Wikipedia and Berkeley's CS172 lecture notes.

Namely, Sipser defines the language in terms of a TM $M$ that

  • takes an encoded machine description $\langle M' \rangle$
  • simulates $M'$ on input $\langle M' \rangle$ on a tape bounded by $f(|\langle M' \rangle|)$
  • inverts the answer, if the machine stops.

The resulting $L(M)$ is different from

$$ L = \{ \langle M \rangle: M\text{ rejects }\langle M \rangle\text{ using }\leq f(|\langle M \rangle|)\text{ space}\} $$

because $M$ rejects $\langle M \rangle$ due to recurrent simulation that requires infinite space and therefore $\langle M \rangle \notin L(M)$ and $\langle M \rangle \in L$ from the definition of $L$.

As a result, in the diagonalization argument we should replace references to the definition of $L$ with references to the acceptance of $M$, which breaks the argument for $M$ itself.

$\endgroup$
  • $\begingroup$ Had a similar issue with the wikipedia article, see my question here: cs.stackexchange.com/questions/104982/… your answer is somehow similar to the answer by dkaeae. I also gave an argument, implying that what you refer to as "recurrent simulation requires infinite space" states as, when simulating on itself we have an logarithmic blow up in the tape symbols, hence needing more and more space in this recurrent simulation. $\endgroup$ – StefanH Mar 7 at 15:25

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.