Eine nicht-deterministische Turing-Maschine heißt linear beschränkt (linear bounded automation, LBA), wenn für alle
Siehe auch
Bedeutung von
bedeutet in diesem Fall, dass wir den Buchstaben markiert haben. Wir markieren den ersten und den letzten Buchstaben, damit wir der Maschine in irgend einer Weise sagen können dass wir über diese Grenzen nicht weiter hinaus dürfen.
Einfach gesagt
Das Band einer linear beschränkten Turing-Maschine ist genau so lang wie das Eingabewort.