# Turing machine with semi infinite tape - Prove by construction

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 tape N 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?

• While I can see how the emulation avoid going to the left of #, some explicit explanation on how to emulate the computation that is supposed to happen to the left of # should be given since that is the crux the emulation, even if it could be very simple. Missing that, it can hardly be called a working idea. – Apass.Jack Dec 8 '18 at 11:33
• I get what you say. I imagine that the transition to the shifting subrutine is possible from every state of the TM, but that is very complex because if it's in the "middle" of a computation and a # is read, then when the shifting subrutine is finished, the last rutine should continue. Can something like a return statement be implemented? I'm new to this topics, I need some more reading – Francisco Hanna Dec 9 '18 at 2:13

The two track solution enlarges the alphabet $$\Sigma$$ to at least an alphabet $$\Sigma\times \Sigma$$ to store two symbols on each tape cell. That is quadratic. Your solution perhaps is more efficient in the number of symbols, since we merely have to move them into a new position.