Savitch theorem ($\mathrm{NSPACE}(s)\subseteq \mathrm{SPACE}(s^2),s\ge \log n$)

Reachability within $2^k$ steps can be tested by enumerating a midpoint and recursively testing two half-paths. Configurations have $O(s)$ bits and recursion depth $O(s)$, yielding deterministic space $O(s^2)$. The space-bound discovery by exit reachability permits this simulation without assuming that the supplied function $s$ is constructible.

For a bounded-space machine, start with a logarithmic work budget and test accepting reachability and reachability of a transition leaving the budget. Accept if acceptance is found, double the budget if an exit is reachable, and otherwise reject. If all paths use at most $Cs(n)$ space, doubling stops at $O(s(n))$. Each budget test uses the Savitch theorem recursion and the storage is reused. The method discovers a sufficient bound without computing $s(n)$.