k
-
Head
Turing Machine
21
/45
Gist:
Turing
m
achine with
k
heads
Theorem:
For every
k
-
head
TM
M
, there is an
equivalent
TM
M
.
Proof:
See page
6
67 in [Meduna: Automata and Languages]
Head 1
Head 2
Head
k
Illustration:
a
1
x
0
x
1
p
a
2
x
2
…
x
k
…
a
k
…
…