Mehrspurige Turingmaschine
Mehrspur-Turing-Maschinen, ein bestimmter Typ von Mehrband-Turing-Maschinen, enthalten mehrere Spuren, aber nur ein Bandkopf liest und schreibt auf allen Spuren. Hier liest ein einzelner Bandkopf n Symbole ausnSpuren in einem Schritt. Es akzeptiert rekursiv aufzählbare Sprachen wie eine normale einspurige Single-Tape-Turing-Maschine.
Eine mehrspurige Turingmaschine kann formal als 6-Tupel (Q, X, ∑, δ, q 0 , F) beschrieben werden, wobei -
Q ist eine endliche Menge von Zuständen
X ist das Bandalphabet
∑ ist das Eingabealphabet
δ ist eine Beziehung zu Zuständen und Symbolen, in denen
δ (Q i , [a 1 , a 2 , a 3 , ....]) = (Q j , [b 1 , b 2 , b 3 , ....], Linksverschiebung oder Rechtsverschiebung)
q0 ist der Ausgangszustand
F ist die Menge der Endzustände
Note - Für jede einspurige Turingmaschine Sgibt es eine gleichwertige mehrspurige Turingmaschine M so dass L(S) = L(M).