Maszyna Turinga z wieloma taśmami
Maszyny Turinga z wieloma taśmami mają wiele taśm, z których każda jest dostępna za pomocą oddzielnej głowicy. Każda głowa może poruszać się niezależnie od innych głów. Początkowo wejście znajduje się na taśmie 1, a inne są puste. Początkowo pierwsza taśma jest zajęta przez wejście, a pozostałe taśmy są puste. Następnie maszyna odczytuje pod głowami kolejne symbole, a TM drukuje symbol na każdej taśmie i porusza głowicami.
Wielotasmową maszynę Turinga można formalnie opisać jako 6-krotkę (Q, X, B, δ, q 0 , F), gdzie -
Q jest skończonym zbiorem stanów
X to alfabet taśmy
B jest pustym symbolem
δ to relacja między stanami i symbolami, gdzie
δ: Q × X k → Q × (X × {Przesunięcie_ w lewo, Przesunięcie_ w prawo, Bez_przestawienia}) k
gdzie jest k liczba taśm
q0 jest stanem początkowym
F jest zbiorem stanów końcowych
Note - Każda maszyna Turinga z wieloma taśmami ma równoważną maszynę Turinga z pojedynczą taśmą.