2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – John L.
    Dec 8, 2018 at 11:33
  • $\begingroup$ 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 $\endgroup$
    – Francisco Hanna
    Dec 9, 2018 at 2:13

1 Answer 1

Reset to default
1
$\begingroup$

You are right. It is possible to shift the contents of the tape when needed.

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.

A third proof might be to store the left and right cells of the tape (from an imaginary "middle") in the even and odd cells. That means the simulation would usually fins the next cell in two steps rather than one.

It is not always clear how to measure elegance of proofs :) sometimes a solution comes from a certain intuition, making it appealing.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Hi Hendrik. Coming back to this after sometime. I never tried to develop my proof. But now reading your comment, I got goosebumps knowing that it could work. I'l give it a try! $\endgroup$
    – Francisco Hanna
    May 15, 2019 at 4:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.