Editing Space hierarchy theorem (section)

== Proof ==

The goal is to define a language that can be decided in space <math>O(f(n))</math> but not space <math>o(f(n))</math>.  The language is defined as {{mvar|L}}:
<blockquote>
<math>L = \{~ (\langle M \rangle, 10^k): M  \mbox{ uses space } \le f(|\langle M \rangle, 10^k|) \mbox{ and time } \le 2^{f(|\langle M \rangle, 10^k|)} \mbox{ and }  M  \mbox{ does not accept } (\langle M \rangle,
10^k) ~ \}</math>
</blockquote>

For any machine {{mvar|M}} that decides a language in space <math>o(f(n))</math>, {{mvar|L}} will differ in at least one spot from the language of {{mvar|M}}. Namely, for some large enough {{mvar|k}}, {{mvar|M}} will use space <math>\le f(|\langle M \rangle, 10^k|)</Math> on <math>(\langle M \rangle, 10^k)</Math> and will therefore differ at its value.

On the other hand, {{mvar|L}} is in <math>\mathsf{SPACE}(f(n))</math>. The algorithm for deciding the language {{mvar|L}} is as follows:

# On an input {{mvar|x}}, compute <math>f(|x|)</math> using space-constructibility, and mark off <math>f(|x|)</math> cells of tape. Whenever an attempt is made to use more than <math>f(|x|)</math> cells, ''reject''.
# If {{mvar|x}} is not of the form <math>\langle M \rangle, 10^k</math> for some TM {{mvar|M}}, ''reject''.
# Simulate {{mvar|M}} on input {{mvar|x}} for at most <math>2^{f(|x|)}</math> steps (using <math>f(|x|)</math> space).  If the simulation tries to use more than <math>f(|x|)</math> space or more than <math>2^{f(|x|)}</math> operations, then ''reject''.
# If {{mvar|M}} accepted {{mvar|x}} during this simulation, then ''reject''; otherwise, ''accept''.

Note on step 3: Execution is limited to <math>2^{f(|x|)}</math> steps in order to avoid the case where {{mvar|M}} does not halt on the input {{mvar|x}}.  That is, the case where {{mvar|M}} consumes space of only <math>O(f(x))</math> as required, but runs for infinite time.

The above proof holds for the case of PSPACE, but some changes need to be made for the case of NPSPACE. The crucial point is that while on a deterministic TM, acceptance and rejection can be inverted (crucial for step 4), this is not possible on a non-deterministic machine.<br>

For the case of NPSPACE, {{mvar|L}} needs to be redefined first:
<blockquote>
<math>L = \{~ (\langle M \rangle, 10^k): M  \mbox{ uses space } \le f(|\langle M \rangle, 10^k|)  \mbox{ and }  M  \mbox{ accepts } (\langle M \rangle,
10^k) ~ \}</math>
</blockquote>
Now, the algorithm needs to be changed to accept {{mvar|L}} by modifying step 4 to:
* If {{mvar|M}} accepted {{mvar|x}} during this simulation, then ''accept''; otherwise, ''reject''.

{{mvar|L}} can not be decided by a TM using <math>o(f(n))</math> cells. Assuming {{mvar|L}} can be decided by some TM {{mvar|M}} using <math>o(f(n))</math> cells, and following from the [[Immerman–Szelepcsényi theorem]], <math>\overline L</math> can also be determined by a TM (called <math>\overline M</math>) using <math>o(f(n))</math> cells. Here lies the contradiction, therefore the assumption must be false:
# If <math>w = (\langle \overline M \rangle, 10^k)</math> (for some large enough {{mvar|k}}) is not in <math>\overline L</math> then {{mvar|M}} will accept it, therefore <math>\overline M</math> rejects {{mvar|w}}, therefore {{mvar|w}} is in <math>\overline L</math> (contradiction).
# If <math>w = (\langle \overline M \rangle, 10^k)</math> (for some large enough {{mvar|k}}) is in <math>\overline L</math> then {{mvar|M}} will reject it, therefore <math>\overline M</math> accepts {{mvar|w}}, therefore {{mvar|w}} is not in <math>\overline L</math> (contradiction).