1
$\begingroup$

I'm having trouble understanding this statement: $DSPACE(s(n)) \subseteq DTIME(2^{O(s(n))})$.

The logic is that $2^{O(s(n))}$ is the total number of different configurations a Turing Machine M that runs in $s(n)$ space can have as a combination of the number of states, head positions, and contents of the tape, but I do not see how this number is arrived at.

Can someone explain?

$\endgroup$
1
$\begingroup$

Suppose that $M$ is a deterministic Turing machine that runs in space $s(n)$ and halts on all inputs. We show below that $M$ has $U(n) = 2^{O(s(n))}$ many configurations. I claim that if $M$ doesn't halt within $U(n)$ steps, then it never halts; since we assumed that $M$ always halts, this means that it always halts within $U(n)$ steps. To see the claim, let $\sigma_0,\ldots,\sigma_{U(n)}$ be the configurations after $0,\ldots,U(n)$ steps. Since there are only $U(n)$ different configurations but $U(n)+1$ many $\sigma_i$'s, there must be $i<j$ such that $\sigma_i = \sigma_j$. Therefore starting at $\sigma_i$, the machine will repeatedly go through the configurations $\sigma_i,\ldots,\sigma_{j-1}$, and in particular, will never halt.

It remains to count the number of configurations. Suppose that $M$ has $Q$ states, $C$ tapes, and tape alphabet $\Sigma$. We can describe a configuration of $M$ by specifying the state ($Q$ options), the head locations ($s(n)^C$), and the tape contents (at most $|\Sigma|^{Cs(n)}$; in these bounds we used the fact that at most $s(n)$ cells are used in each tape. In total, the number of configurations is at most $$ U(n) = Q s(n)^C |\Sigma|^{Cs(n)}. $$ You can show that $U(n) = 2^{O(s(n))}$ using standard manipulations, completing the proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.