A machine using space s(n) has at most exponentially many configurations

By [L1], once the input $x$ is fixed a configuration of $M$ is determined by the current state, the $k$ head positions, and the symbols on the cells that have been visited so far: every unvisited work-tape cell is still blank, and every unvisited input-tape cell still carries its fixed symbol from $x$. By [L2], at most $s$ tape cells are ever visited in total.

Let $Q$ be the finite state set and let $\mathrm{\Gamma }$ be a common finite upper bound for the tape alphabets. Step 1.1 gives at most $\mathrm{\mid }Q\mathrm{\mid }$ choices for the state, at most $(s+1{)}^k$ choices for the head positions, and at most $\mathrm{\mid }\mathrm{\Gamma }{\mathrm{\mid }}^s$ choices for the symbols on the visited cells. Hence the total number of configurations that can arise on input $x$ is at most $\mathrm{\mid }Q\mathrm{\mid }(s+1{)}^k\mathrm{\mid }\mathrm{\Gamma }{\mathrm{\mid }}^s$.

Because $M$ is fixed, the constants $\mathrm{\mid }Q\mathrm{\mid }$, $k$, and $\mathrm{\mid }\mathrm{\Gamma }\mathrm{\mid }$ are fixed. For $s\ge 1$ there is therefore a constant $c_M$ with $\mathrm{\mid }Q\mathrm{\mid }(s+1{)}^k\mathrm{\mid }\mathrm{\Gamma }{\mathrm{\mid }}^s\le 2^{c_{M}s}$. This proves the claimed exponential bound.