Problem with understanding proof of the Space Hierarchy Theorem

Question

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.

Answer 1

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.