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




…
…
Tvrzení: Pro každý TS M existuje
ekvivalentní k-hlavý
TS M.
Důkaz: Viz. str. 667 v knize [Meduna: Automata and Languages]