In "Introduction to the Theory of Computation" by Sipser, Savitch's theorem is explained as an improvement to a naive storage scheme for simulating non-deterministic Turing machines (NTM). I am going to quote the text verbatim, because quite frankly I don't fully understand it (which is why I was unable to really ask my question in enough detail):
We need to simulate an $f(n)$ space NTM deterministically. A naive approach is to proceed by trying all the branches of the NTM’s computation, one by one. The simulation needs to keep track of which branch it is currently trying so that it is able to go on to the next one. But a branch that uses $f(n)$ space may run for $2^{O(f(n))}$ steps and each step may be a nondeterministic choice. Exploring the branches sequentially would require recording all the choices used on a particular branch in order to be able to find the next branch. Therefore, this approach may use $2^{O(f(n))}$ space, exceeding our goal of $O(f^2(n))$ space. (Sipser, "Introduction to the Theory of Computation" 334)
He goes on to describe Savitch's use of a subroutine called $CANYIELD$, a TM that decides whether some configuration $c_2$ is reachable from some other configuration $c_1$ in $t$ steps. It is recursively defined, so that $CANYIELD(c_1, c_n, t)$ results in two recursive calls $CANYIELD(c_1, c_m, t/2)$ and $CANYIELD(c_m, c_n, t/2)$, and so on until the "distance" between configurations is $0$ or $1$, or it is deemed unreachable. I think this can also be described as $STCON$ on a configuration graph of the TM in question.
So, there are two questions I have.
- I understand how the size of each level and the depth of $CANYIELD$ results in no more than $O(f^2(n))$ use of space, but I don't understand how the intermediate configuration $c_m$ is found. Is this just not important given that all we care about is space? How do we know that the space used to obtain $c_m$ is negligible?
- I don't understand why we need $2^{O(f(n))}$ space in the naive approach. Why can't we "forget" about branches we've executed, so that we are still using at most the space required to go all the way down one branch?