k-Tape Turing Machine
20/45
 Gist: Turing machine with k tapes
Illustration:
a1
x1
y1
p
a2
x2
y2
ak
xk
yk
…
Theorem: For every k-tape TM M, there is an   equivalent TM M.
Proof: See page 662 in [Meduna: Automata and Languages]
Tape 1
Tape 2
Tape k
…
…
…
…