Lineárně ohraničený Turingův stroj

Pojem lineárně ohraničený Turingův stroj označuje v informatice Turingův stroj, který má omezení při zápisu na pásku. Na rozdíl od běžného Turingova stroje totiž nesmí zapisovat na neomezeně mnoho buněk pásky, ale pouze na prvních n buněk, kde n je omezeno lineární funkcí vzhledem k délce vstupního slova. V určitém smyslu je tak tento stroj bližší běžným počítačům.

Lineárně ohraničené Turingovy stroje umí akceptovat jazyky ze třídy kontextových jazyků. Lze dokázat, že pro každý lineárně ohraničený Turingův stroj lze sestrojit Turingův stroj, který nepotřebuje pásku delší než je délka vstupního slova.

Kategorie:Výpočetní modely