# Why are there only 2^i configurations?

In the proof of TQBF-complete, it says if the input size is i, then the TM for the input has at most 2^i numbers of configuration. Can someone explain why? The proof is from: http://zoo.cs.yale.edu/classes/cs468/fall12/TQBF-complete.pdf

• Where did you read that? What was the surrounding context? We're more likely to be able to answer questions about some proof if you can provide excerpts from the proof to give us the relevant context (so we don't have to guess what the reasoning in the proof might be).
– D.W.
Commented Mar 24, 2017 at 0:15

Let $s(n)$ be the space used by Turing machine, $\Sigma$ is a input alphabet, $Γ$ is tape alphabet ( $Σ ⊆ Γ$ ) and $Q$ is a finite set of states. Then maximum number of different configuration bounded by $|Q| \times| Γ|^{s(n)}\times s(n)$. You have $s(n)$ many places and in each place you have choices and then you can derive the expression very easily.
That's not what the proof says. Nowhere does the proof claim there are only $2^i$ configurations, where $i$ is the length of the input. In particular, in the proof you link to, $i$ is not the length of the input.
Rather, the proof says that every configuration can be encoded as a bitstring of length $c \cdot s(n)$, and consequently there are at most $2^{c \cdot s(n)}$ possible configurations. Then it goes on to consider a value of $i$ that is $c \cdot s(n)$.