k-Head Turing Machine
21/45
 Gist: Turing machine with k heads
Theorem: For every k-head TM M, there is an   equivalent TM M.
Proof: See page 667 in [Meduna: Automata and Languages]
Head 1
Head 2
Head k
Illustration:
a1
x0
x1
p
a2
x2
…
xk
…
ak
Textové pole: …
…
…