k-hlavý Turingův stroj
21/45
 Myšlenka: Turingův stroj s „k“ hlavami
Hlava 1
Hlava 2
Hlava k
Ilustrace:
a1
x0
x1
p
a2
x2
…
xk
…
ak
Textové pole: …
…
…
Tvrzení: Pro každý TS M existuje ekvivalentní k-hlavý TS M.
Důkaz: Viz. str. 667 v knize [Meduna: Automata and Languages]