k-páskový Turingův stroj
20/45
 Myšlenka: Turingův stroj s „k“ páskami
Ilustrace:
a1
x1
y1
p
a2
x2
y2
ak
xk
yk
…
Páska 1
Páska 2
Páska k
…
…
…
…
Tvrzení: Pro každý TS M existuje ekvivalentní k-páskový TS M.
Důkaz: Viz. str. 662 v knize [Meduna: Automata and Languages]