How Do Linear Bounded Automata Model Bounded Memory?

Linear bounded automata model computation with memory proportional to input length by restricting a Turing machine's tape to the exact cells occupied by the input string. Unlike standard Turing machines that can expand onto an infinite tape, a linear bounded automaton must perform all its read and write operations within fixed boundaries marked at the ends of the input. This simple constraint captures the class of context-sensitive languages and corresponds directly to linear-space computation in classical complexity theory.

Formal Structure of a Linear Bounded Automaton

A linear bounded automaton (LBA) is a restricted nondeterministic Turing machine. Formally, it is defined as a tuple \(M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})\), where:

  • \(Q\) is a finite set of states.
  • \(\Sigma\) is the input alphabet, which includes two special end-marker symbols, \(\triangleleft\) (left end-marker) and \(\triangleright\) (right end-marker).
  • \(\Gamma\) is the tape alphabet, with \(\Sigma \subseteq \Gamma\).
  • \(\delta : Q \times \Gamma \rightarrow \mathcal{P}(Q \times \Gamma \times \{L, R\})\) is the transition function.
  • \(q_0 \in Q\) is the start state, while \(q_{\text{accept}}\) and \(q_{\text{reject}}\) are the halting states.

For an input string \(w\) of length \(n\), the tape initially contains \(\triangleleft w \triangleright\), occupying \(n + 2\) cells. The transition function is restricted so that the machine cannot overwrite \(\triangleleft\) or \(\triangleright\), nor can it move its read/write head past \(\triangleleft\) to the left or past \(\triangleright\) to the right.

How Tape Compression Achieves Linear Memory

At first glance, restricting the tape to \(n + 2\) cells appears to limit memory strictly to \(n\) cells rather than any constant multiple \(c \cdot n\). However, an LBA can simulate \(c \cdot n\) memory cells by expanding its tape alphabet \(\Gamma\).

If a machine requires \(c\) tracks of memory of length \(n\), it can group \(c\) symbols from a base alphabet into a single compound symbol in \(\Gamma\). The size of the new tape alphabet becomes \(|\Gamma|^c\). Since \(c\) is a constant independent of the input length \(n\), this alphabet expansion is finite and valid within the formal definition. Through this technique, known as tape compression, an LBA with \(n + 2\) tape cells can model any computation that uses \(O(n)\) space.

Computational Power and Complexity Classes

Because LBAs are restricted to linear space, their computational power sits strictly between pushdown automata and unrestricted Turing machines:

  • Context-Sensitive Languages: A language is context-sensitive if and only if it is recognized by a nondeterministic linear bounded automaton.
  • Deterministic vs. Nondeterministic LBAs: A deterministic LBA (DLBA) recognizes languages in \(\text{DSPACE}(n)\), while a nondeterministic LBA (NLBA) recognizes languages in \(\text{NSPACE}(n)\). Whether \(\text{DSPACE}(n) = \text{NSPACE}(n)\) remains an open problem in theoretical computer science, known as the LBA problem.
  • Closure Properties: The class of languages recognized by NLBAs is closed under complementation, a result proven by the Immerman–Szelepcsényi theorem, which showed that \(\text{NSPACE}(s(n)) = \text{co-NSPACE}(s(n))\) for space-constructible functions \(s(n) \ge \log n\).

Decidability Under Linear Space Bounds

Unlike general Turing machines, where the halting problem is undecidable, the halting problem for an LBA is decidable. For a fixed LBA \(M\) and an input of length \(n\), the total number of distinct configurations is finite:

\[|Q| \cdot (n + 2) \cdot |\Gamma|^{n+2}\]

If an LBA runs for more steps than this bound without halting, it must have repeated a configuration and entered an infinite loop. By simulating \(M\) and tracking whether it exceeds this configuration bound, a standard Turing machine can decide whether \(M\) accepts or rejects a given input. However, the emptiness problem—determining whether an arbitrary LBA accepts at least one string—remains undecidable.