An Introduction to Formal Languages and Automata, 7th Edition

10.5 LINEAR BOUNDED AUTOMATA

While it is not possible to extend the power of the standard Turing machine by complicating the tape structure, it is possible to limit it by restricting the way in which the tape can be used. We have already seen an example of this with pushdown automata. A pushdown automaton can be regarded as a nondeterministic Turing machine with a tape that is restricted to being used like a stack. We can also restrict the tape usage in other ways; for example, we might permit only a finite part of the tape to be used as work space. It can be shown that this leads us back to finite automata, so we need not pursue this. But there is a way of limiting tape use that leads to a more interesting situation: We allow the machine to ...