I'm studying constrained Turing Machines.
There's a theorem that proves that both infinite and semi-infinite tape TM have the same computational power. The theorem that proves this by emulating a TM1 with infinite tape with a multi-track tape TM2, where one track emulates the right part of the TM1 tape and the other track emulates the left part TM1 tape.
Could I emulate the infinite tape machine the following way:
- Let the alphabet of TM1 be
{0,1}
- Construct a TM2 machine with semifinite tape to right with alfabet
{0,1} U {#}
- Let
w = 011101
When execution starts, the tape looks like
|011101BBB...
The first step of TM2 should be to call a subrutine TM2 that shifts
w
on the tapeN
times to the right and puts#
in the first position of the tape, so:|#BB...011101BBB...
- If during execution the control unit reads the
#
symbol, then call again the shifting subrutine.
I know this is not a formal prove, just an idea. I also know that this is not efficient nor an elegant construction but, could it work?