My homework assignment is to show that the Space Hierarchy Theorem's proof (as stated in Sipser's Introduction to the Theory of Computation) is invalidated by removing some part of the algorithm -- let's call it a "safeguard".
Sisper's proof goes over the algorithm $D$, stage by stage, showing what's the rationale behind every stage. Finally, he proves that $D$ (which decides language $A$) is not in space $g(n)$ (where $g(n)=o(f(n))$). He does this by assuming for contradiction there exists $M$ in space $g(n)$ that decides language $A$, then showing such $M$ would end up deciding a different language than $D$.
I'm stuck at picking a proof technique. Sipser's proof just covers all bases, but actually constructing such a TM $M$ is a different kind of task he doesn't tackle. When I modify the proof to remove one of his "safeguards", I'm having a hard time showing there actually exists that thing he safeguarded against. I guess it's one of those cases where proving is easier than finding a counterexample?...
P.S. Looking for a hint, not to cheat :)
