Czy wiesz że...?
Automat liniowo ograniczony (ang. linear bounded automaton) to ograniczona wersja maszyny Turinga, która podczas obliczenia na słowie wejściowym długości n może wykorzystać jedynie O(n) komórek taśmy. Innymi słowy, dostępna pamięć jest funkcją liniową od długości wejścia. Można także powiedzieć, że może ona w trakcie działania wykorzystywać tylko te komórki na taśmie, w których zapisane jest słowo wejściowe.