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]