Savitch's theorem

For any function  where 

: Let  be an NTM deciding a language  in space . We construct a deterministic TM  deciding . Machine  uses the procedure CANYIELD, which tests whether one of  's configurations can yield another within a specified number of steps. This procedure solves the yieldability problem: given two configurations of the  and  together with a number , and we test whether the NTM can get from  to  within  steps using only  space. Let  be a string considered as input to . For configurations  and  of , and integer , CANYIELD  outputs accept if  can go from configuration  to configuration  in  or fewer steps along some nondeterministic path. If not, CANYIELD outputs reject. For convenience, we assume that  is a power of 2.

CANYIELD =" On input  and 

1. If , then test directly whether  or whether  yields  in one step according to the rules of Accept if either test succeeds; reject if both fail.
2. If , then for each configuration  of  using space  :
3.  Run CANYIELD .
4.  Run CANYIELD .
5.  If steps 3 and 4 both accept, then accept.
6. If haven't yet accepted, reject."

Now we define  to simulate  as follows. We first modify  so that when it accepts, it clears its tape and moves the head to the leftmost cell-thereby entering a configuration called  We let  be the start configuration of  on  We select a constant  so that  has no more than  configurations using tape, where  is the length of . Then we know that  provides an upper bound on the running time of any branch of  on .

 "On input 

1. Output the result of CANYIELD ."

Algorithm CANYIELD obviously solves the yieldability problem, and hence  correctly simulates  We need to analyze it to verify that  works within  space. Whenever CANYIELD invokes itself recursively, it stores the current stage number and the values of  and  on a stack so that these values may be restored upon return from the recursive invocation. Each level of the recursion thus uses  additional space. Furthermore, each level of the recursion divides the size of  in half. Initially  starts out equal to  so the depth of the recursion is  or  Therefore, the total space used is  as claimed. One technical difficulty arises in this argument because algorithm  needs to know the value of  when it calls CANYIELD. We can handle this difficulty by modifying  so that it tries  For each value , the modified algorithm uses CANYIELD to determine whether the accept configuration is reachable. In addition, it uses CANYIELD to determine whether  uses at least space  by testing whether  can reach any of the configurations of length  from the start configuration. If the accept configuration is reachable, accepts; if no configuration of length  is reachable,  rejects; and otherwise,  continues with