[Overview] [Previous] [Next]

Variations on Turing Machines IV

A linear-bounded automaton is a Turing machine that has only the tape that its input is printed on. There is no additional blank tape.

Theorem. Linear-bounded automata are not equivalent to standard Turing machines.

The languages recognizable by linear-bounded automata (lbas) are called the context-sensitive languages. We will briefly touch on context-sensitive languages later in this course.

Copyright © 1996 by David Matuszek
Last modified Mar 27, 1996