1
$\begingroup$

I was wondering about a result in the Sipser book which states that any $f(n)$ space bounded Turing machine also runs in time $2^{O(f(n))}$.

Is this because a configuration consists of a state, a position of the head and the contents of the work tape, which is $\vert Q \vert \cdot f(n) \cdot \vert \Gamma \vert ^{f(n)}$. To be honest I'm not quite sure why this is equal to $2^{O(f(n))}$. Wouldn't this only be the case when your work tape alphabet consists of 2 symbols?

Probably a silly question, but thanks anyway.

Also, I did not quite understand if this result changes when we consider logspace bound Turing machines.

$\endgroup$
2
$\begingroup$

Yes, that's right. If there are $k$ possible configurations, then any such Turing machine either runs in time at most $k$, or it loops forever. That's because if it runs for at least $k+1$ time steps, some configuration must be repeated; and if a configuration is repeated, it will continue repeating forever.

Let $|\Gamma|=2^c$, i.e., $c = \lg |\Gamma|$. Then $|\Gamma|^{f(n)} = (2^c)^{f(n)} = 2^{c f(n)} = 2^{O(f(n)}$. For similar reasons, $\vert Q \vert \cdot f(n) \cdot \vert \Gamma \vert ^{f(n)} = 2^{O(f(n)}$. So, the number of possible configurations of a $f(n)$-space-bounded Turing machine is $2^{O(f(n)}$, and thus any such machine must either halt in time at most $2^{O(f(n)}$ or loop forever.

$\endgroup$
  • $\begingroup$ Oh ok, this makes sense. So we can essentially represent an arbitrary tape alphabet size, $\vert \Gamma \vert$ with some constant so that $2^c = \vert \Gamma \vert$. thank you! $\endgroup$ – Johnny Pandeleo Feb 20 at 11:44
  • $\begingroup$ @JohnnyPandeleo, yup! You got it. The tape alphabet is fixed and doesn't vary depending on the length of the input, which is why $|\Gamma|$ is a constant. $\endgroup$ – D.W. Feb 20 at 19:43

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.