Lineárně ohraničený Turingův stroj: Porovnání verzí

Pojem '''lineárně ohraničený Turingův stroj''' označuje v [[informatika|informatice]] [[Turingův stroj]], který má omezení při zápisu na pásku. NarozdílNa 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í [[funkce (matematika)|funkcí]] vzhledem k délce vstupního slova. V určitém smyslu je tak tento stroj bližší běžným [[počítač]]ům.