Linear Bounded Automaton

computation

Definition

Linear Bounded Automaton

A linear bounded automaton is a Turing machine whose available work space is bounded by a linear function of the input length.

Formally, a Turing machine $M$ is a linear bounded automaton if there are constants $c,d\in \mathbb{N}$ such that, for every input word $w$ of length $n$, $M$ uses at most $cn+d$ tape cells during the computation on $w$.