A linear bounded automaton is a Turing machine that is restricted by memory.
How would augmenting the tape alphabet of a linear bounded automaton increase its memory? While the memory that the automata can use is as size of the input?


1 Answer 1


If you consider an input, hence a tape, of size $n$ and a tape alphabet of $b$ symbols, you get $b^n$ configurations possible on your tape. If you measure memory in bits, the memory size is the base 2 logarithm of the number of configurations, very simply because that is the number of bits required to have the same number of configurations (rounding up to the next integer, because half-bits have not been invented yet).

So the tape memory of your linear bounded automaton (LBA) is $\log_2 b^n$, which is equal to $n\log_2 b$.

Augmenting your tape alphabet does not increase your memory very fast. Doubling the size of the alphabet is equivalent to a single extra bit per cell, i.e. adding $n$ bits total. The positive side of it is that it does not take many bits per cell of the tape to have a huge alphabet.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.