Multitape Turingův stroj - Multitape Turing machine
A vícepásmový Turingův stroj je varianta Turingův stroj který využívá několik pásek. Každá páska má vlastní hlavu pro čtení a zápis. Zpočátku se vstup zobrazí na pásce 1 a ostatní začnou prázdné.[1]
Tento model se intuitivně zdá být mnohem výkonnější než model s jednou páskou, ale jakýkoli vícepásový stroj - bez ohledu na to, kolik pásek - lze simulovat pomocí stroje s jednou páskou pouze pomocí kvadraticky více výpočetního času.[2] Vícepásové stroje tedy nemohou vypočítat více funkcí než jednopáskové stroje,[3] a žádný z robustních složitost třídy (např polynomiální čas ) jsou ovlivněny změnou mezi jednopáskovým a vícepáskovým strojem.
Formální definice
Turingův stroj k-tape lze popsat jako šestinu kde:
- je konečná množina států
- je konečná sada páskové abecedy
- je počáteční stav
- je prázdný symbol
- je sada konečných nebo přijímajících států
- je částečná funkce zvaná přechodová funkce, kde k je počet pásek, L je levý posun, R je pravý posun a S není žádný posun.
Dvouvrstvý Turingův stroj
Dvouvrstvé stroje Turing mají vstup jen pro čtení a dvě úložné pásky. Pokud se hlava posune doleva na kteroukoli pásku, vytiskne se na ni páska, ale lze vytisknout jeden symbol z „knihovny“.
Viz také
- Turingův stroj
- Univerzální Turingův stroj
- Střídavý Turingův stroj
- Pravděpodobný Turingův stroj
- Turingovy ekvivalenty
Reference
- ^ Sipser, Michael (2005). Úvod do teorie výpočtu. Technologie kurzu Thomson. str. 148. ISBN 0-534-95097-3.
- ^ Papadimitriou, Christos (1994). Výpočetní složitost. Addison-Wesley. str.53. ISBN 0-201-53082-1.
- ^ Martin, John (2010). Úvod do jazyků a teorie výpočtu. McGraw Hill. 243–246. ISBN 978-0071289429.