TM with Two-way Infinite Tapes
22/45
Gist: Turing machine with tape infinite both to the right and to the left
Theorem: For every TM with two-way infinite tapes M, there is an equivalent TM M.
Proof: See page 673 in
[Meduna: Automata and Languages]
Illustration:
p
a1
x1
y1
…
…
