Editing Space hierarchy theorem (section)

== Refinement of space hierarchy ==

If space is measured as the number of cells used regardless of alphabet size, then {{tmath|1=\mathsf{SPACE}(f(n)) = \mathsf{SPACE}(O(f(n)))}} because one can achieve any linear compression by switching to a larger alphabet.  However, by measuring space in bits, a much sharper separation is achievable for deterministic space. Instead of being defined up to a multiplicative constant, space is now defined up to an additive constant. However, because any constant amount of external space can be saved by storing the contents into the internal state, we still have {{tmath|1=\mathsf{SPACE}(f(n)) = \mathsf{SPACE}(f(n)+O(1))}}.

Assume that f is space-constructible.  SPACE is deterministic.
* For a wide variety of sequential computational models, including for Turing machines, SPACE(''f''(''n'')-[[Big O Notation|ω]](log(''f''(''n'')+''n''))) ⊊ SPACE(''f''(''n'')).  This holds even if SPACE(''f''(''n'')-''ω''(log(''f''(''n'')+''n''))) is defined using a different computational model than {{tmath|\mathsf{SPACE}(f(n))}} because the different models can simulate each other with {{tmath|O(\log(f(n)+n))}} space overhead. 
* For certain computational models, we even have SPACE(''f''(''n'')-''ω''(1)) ⊊ SPACE(''f''(''n'')).  In particular, this holds for Turing machines if we fix the alphabet, the number of heads on the input tape, the number of heads on the worktape (using a single worktape), and add delimiters for the visited portion of the worktape (that can be checked without increasing space usage).  SPACE(''f''(''n'')) does not depend on whether the worktape is infinite or semi-infinite.  We can also have a fixed number of worktapes if ''f''(''n'') is either a SPACE constructible tuple giving the per-tape space usage, or a SPACE(''f''(''n'')-''ω''(log(''f''(''n'')))-constructible number giving the total space usage (not counting the overhead for storing the length of each tape).

The proof is similar to the proof of the space hierarchy theorem, but with two complications: The universal Turing machine has to be space-efficient, and the reversal has to be space-efficient. One can generally construct universal Turing machines with {{tmath|O(\log(space))}} space overhead, and under appropriate assumptions, just {{tmath|O(1)}} space overhead (which may depend on the machine being simulated). For the reversal, the key issue is how to detect if the simulated machine rejects by entering an infinite (space-constrained) loop.  Simply counting the number of steps taken would increase space consumption by about {{tmath|f(n)}}.  At the cost of a potentially exponential time increase, loops can be detected space-efficiently as follows:<ref>{{cite conference | first = Michael | last = Sipser | title = Halting Space-Bounded Computations | book-title = Proceedings of the 19th Annual Symposium on Foundations of Computer Science | date = 1978}}</ref>

Modify the machine to erase everything and go to a specific configuration A on success. Use [[depth-first search]] to determine whether A is reachable in the space bound from the starting configuration. The search starts at A and goes over configurations that lead to A. Because of determinism, this can be done in place and without going into a loop.

It can also be determined whether the machine exceeds a space bound (as opposed to looping within the space bound) by iterating over all configurations about to exceed the space bound and checking (again using depth-first search) whether the initial configuration leads to any of them.