Max number of configurations of a Turing Machine

Question

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.

Answer 1

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.