Linear constrained Turing machine

A linearly bounded Turing machine (also LBA = Linear Bounded Automaton ) in theoretical computer science is a Turing machine that does not leave the area of the tape on which the input is placed during the entire calculation.

definition

A (deterministic) linearly bounded Turing machine is a Turing machine with the following properties: ${\ displaystyle M = (Q, \ Sigma, \ Gamma, \ delta, q_ {0}, \ square, F)}$

The input alphabet contains two special symbols, a start and an end symbol, which mark the left and right ends of the input. ${\ displaystyle \ Sigma}$
The transfer function does not overwrite any of the end markers.
When the start symbol is read, the transfer function does not output, and when the end symbol is read, the transfer function does not output . ${\ displaystyle L}$ ${\ displaystyle R}$

The above definition can be extended to nondeterministic Turing machines .

A nondeterministic linearly bounded Turing machine is a nondeterministic Turing machine with the following properties ${\ displaystyle M = (Q, \ Sigma, \ Gamma, \ delta, q_ {0}, \ square, F)}$

The input alphabet contains two special symbols, a start and an end symbol, which mark the left and right ends of the input. ${\ displaystyle \ Sigma}$
The transition relation does not overwrite any of the end markers.
When the start symbol is read, there is no transition with in the transition relation, and when the end symbol is read there is no transition with in the transition relation . ${\ displaystyle L}$ ${\ displaystyle R}$

Alternative definition

An LBA can simulate a band that is a constant factor larger by including the band alphabet tuple of the input alphabet. Accordingly, a definition would be conceivable in which a band that is larger by a constant factor is provided. That is, there is a constant number so that the Turing machine uses at most the first fields of the tape, where is the length of the input word. The usable tape length is then linear in the length of the input. This explains the "linear" in the name of the LBA. ${\ displaystyle c}$ ${\ displaystyle c}$ ${\ displaystyle c}$ ${\ displaystyle c \ cdot n}$ ${\ displaystyle n}$

Relation to context-sensitive languages

As with general Turing machines, one can consider the languages accepted by LBAs . LBAs are important in the Chomsky hierarchy , a hierarchy of classes of formal grammars . The Chomsky hierarchy establishes the relationship between different classes of grammars and different classes of automata. Nondeterministic LBAs are the automaton class that corresponds to context-sensitive grammars , that is, the languages accepted by nondeterministic LBAs are precisely the context-sensitive languages .

LBA problems

There are two known problems for linearly constrained Turing machines that go back to the work of Kuroda and are often referred to as "LBA problems" in the English-language literature.

The first question is whether every language that is accepted by a nondeterministic linearly constrained Turing machine is also accepted by a deterministic linearly constrained Turing machine, that is, whether deterministic and nondeterministic LBAs accept the same language class. This question is an open problem in theoretical computer science.

The second question is whether the language class that is accepted by non-deterministic, linearly restricted Turing machines is closed with complement formation . The set of Immerman and Szelepcsényi shows that the voice class of context-sensitive languages (type 1) closed under complementation, and thus solves this problem.

Using notation from complexity theory , the first question can be formulated as “ ?” And the second question as “ ?”. ${\ displaystyle {\ text {NSPACE}} (O (n)) = {\ text {DSPACE}} (O (n))}$ ${\ displaystyle {\ text {NSPACE}} (O (n)) = {\ text {co-NSPACE}} (O (n))}$

literature

Uwe Schöning : Theoretical Computer Science - in a nutshell . 5th edition. Spectrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1 , 1.4 context-sensitive and type 0 languages.
Ingo Wegener : Theoretical Computer Science . An algorithm-oriented introduction. BG Teubner, Stuttgart 1993, ISBN 3-519-02123-4 , 5.4 Context-sensitive grammars and languages.

Individual evidence

^ Sige-Yuki Kuroda: Classes of languages and linear-bounded automata . In: Information and Control . tape 7 , no. 2 , June 1964, p. 207-223 , doi : 10.1016 / s0019-9958 (64) 90120-2 ( sciencedirect.com [PDF]).

[1] Sige-Yuki Kuroda: Classes of languages and linear-bounded automata . In: Information and Control . tape 7 , no. 2 , June 1964, p. 207-223 , doi : 10.1016 / s0019-9958 (64) 90120-2 ( sciencedirect.com [PDF]).