Savitch's theorem: NSPACE(s(n)) is contained in DSPACE(s(n)^2)

Let $M$ be the machine from [L1], and fix an input $x$ of length $n$. Form the directed configuration graph $G_x$: its vertices are the configurations of $M$ on $x$, and there is an arc $C\to C^{\mathrm{\prime }}$ exactly when one legal transition of $M$ moves from $C$ to $C^{\mathrm{\prime }}$. Let $C_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}(x)$ be the start configuration. Then $x\in L$ if and only if some accepting configuration is reachable from $C_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}(x)$ in $G_x$.

By [L2], $G_x$ has at most $N_x\le 2^{cs(n)}$ vertices for some constant $c$ depending only on $M$. Any directed path with repeated vertices can be shortened by deleting directed cycles, so $x\in L$ if and only if $C_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}(x)$ reaches some accepting configuration by a path of length at most $N_x-1$.

A deterministic simulator can enumerate candidate accepting configurations $C$ one at a time and run the bounded reachability procedure on the triple $(G_x,C_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}(x),C)$ with an index large enough to cover $N_x-1$. By [L3], that test answers the reachability question correctly for each candidate $C$.

By [L4], each such reachability test uses $O(s(n{)}^2)$ space. The simulator never stores the whole graph: it keeps only the current input, one or two configurations, the midpoint candidate, and the recursion stack; adjacency in $G_x$ is recomputed from the transition function of $M$ when needed. The outer loop over candidate accepting configurations adds only $O(s(n))$ more space. Hence the overall deterministic decider uses $O(s(n{)}^2)$ space.

Since the input $x$ was arbitrary, $L\in \mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(s(n{)}^2)$. This proves $\mathrm{N}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(s(n))\subseteq \mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(s(n{)}^2)$.