The lemma is:

Let $M$ be an LBA with $q$ states and $g$ symbols in the tape alphabet. There are exactly $qng^n$ distinct configurations of $M$ for a tape of length $n$.

I want know why LBA has $qng^n$ configurations.

Following is the proof:

A configuration of $M$ is like a snapshot in the middle of its computation. A configuration consists of the state of the control, position of the head, and contents of the tape. Here, $M$ has $q$ states. The length of its tape is $n$, so the head can be in one of $n$ positions, and $g^n$ possible strings of tape symbols appear on the tape. The product of these three quantities is the total number of different configurations of $M$ with a tape of length $n$.

  • $\begingroup$ The proof you posted is OK, what is the question then? $\endgroup$ – diplodoc Aug 25 '19 at 10:05
  • $\begingroup$ I can understand why there are g^n possible strings of tape. I cannot figure out the reasoning behind it $\endgroup$ – lemniscate Aug 25 '19 at 10:08

If you have $g$ symbols (including a blank) and a tape of size $n$ then there are $g^n$ words of length $n$. This is really basic combinatorics: The reasoning is that you have $g$ options for the first symbol, $g$ options for the second symbol, i.e. $g^2$ options for the first two symbols. Then again $g$ options for the third symbol, giving you $g^3$ options for the first three symbols and so on. If you are not convinced, try it with for example a $3$-symbol alphabet.

Since your tape has length $n$ there are $n$ possible head positions, so you multiply the number of strings on the tape with $n$.

Finally, there are $q$ states, so for every possible string on tape and every possible head position, we can be in either of the $q$ states, making $qng^n$ configurations of the Turing machine.


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.