Wielościeżkowa maszyna Turinga
Wielościeżkowe maszyny Turinga, szczególny typ wielościeżkowych maszyn Turinga, zawierają wiele ścieżek, ale tylko jedna głowica taśmy odczytuje i zapisuje na wszystkich ścieżkach. Tutaj pojedyncza głowica taśmy odczytuje n symboli znutworów w jednym kroku. Akceptuje rekurencyjnie wyliczalne języki, takie jak zwykła maszyna Turinga z pojedynczą taśmą.
Wielościeżkową maszynę Turinga można formalnie opisać jako 6-krotkę (Q, X, ∑, δ, q 0 , F), gdzie -
Q jest skończonym zbiorem stanów
X to alfabet taśmy
∑ jest alfabetem wejściowym
δ to relacja między stanami i symbolami, gdzie
δ (Q i , [a 1 , a 2 , a 3 , ....]) = (Q j , [b 1 , b 2 , b 3 , ....], Przesunięcie_ w lewo lub Przesunięcie_ w prawo)
q0 jest stanem początkowym
F jest zbiorem stanów końcowych
Note - Dla każdej jednotorowej maszyny Turinga S, istnieje równoważna wielościeżkowa maszyna Turinga M takie że L(S) = L(M).