# Max number of configurations of a Turing Machine

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.

## 1 Answer

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.

• 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! – Johnny Pandeleo Feb 20 at 11:44
• @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. – D.W. Feb 20 at 19:43