Linear Bounded Automaton - Wikipedia - Immerman–Szelepcsényi theorem  ## Metadata - Author: **Immerman–Szelepcsényi theorem** - Full Title: Linear Bounded Automaton - Wikipedia - Category: #articles - URL: https://en.wikipedia.org/wiki/Linear_bounded_automaton ## Highlights - A linear bounded automaton is a nondeterministic Turing machine that satisfies the following three conditions: Its input alphabet includes two special symbols, serving as left and right endmarkers. Its transitions may not print other symbols over the endmarkers. Its transitions may neither move to the left of the left endmarker nor to the right of the right endmarker.[1]: 225  In other words: instead of having potentially infinite tape on which to compute, computation is restricted to the portion of the tape containing the input plus the two tape squares holding the endmarkers.