0

I have always worked in 2 way infinite tape and most probably I think that was the first represented as Turing Machine. How can I emulate One-way Turing Machine to Two way Turing Machine.

Harshal Carpenter
  • 115
  • Is the position of the head at the beginning free ? Or must it be at the leftmost / rightmost place ? – Peter Feb 05 '15 at 22:59
  • If it is free, I can fold it. I want it for the leftmost position. The starting position. – Harshal Carpenter Feb 05 '15 at 23:00
  • What about moving the head far away from the end of the tape. In this way, you have as much place for the left / right side as you need. – Peter Feb 05 '15 at 23:02
  • I can do that, but what if the head reaches the head and falls of ? should i put a Turnstile symbol ? so whenever I encounter that symbol, the head MUST change the direction? – Harshal Carpenter Feb 05 '15 at 23:08
  • I do not quite understand. If the head is at the leftmost place, we can move it to the right as far as we want. But we have to know how many places are sufficient. If this is known, there should be no problem. – Peter Feb 05 '15 at 23:10
  • Yes, right side is infinite. Left side is not infinite. It has a end from which a head can fall off.. – Harshal Carpenter Feb 05 '15 at 23:12
  • Every halting machine only needs a finite amount of the "left" side of the tape in the double-infinite case. We only have to know this amount or at least an upper bound. If we move to the right this amount before the calculation, nothing can happen. – Peter Feb 05 '15 at 23:14
  • Yep, I understand but I have learned with 2 way infinite tape ..so its like

    .....BBB10000110BBB....

    I have to prove that it can be emulated in this:

    L1011010BBB... where L is left end..

     – Harshal Carpenter Feb 05 '15 at 23:17
  • The procedure should be : Move the head to the right until enough space is on the left side. Then copy the initial tape (assuming only a finite number of places are not blank), move the head to the position, it would have in the "normal" tape and run the original turing machine. Have I overlooked something ? – Peter Feb 05 '15 at 23:30
  • i was thinking the same thing, but in Limits Of Computation, they have implemented something like this T 1 B 1 B 0 B 0 B 1 B B B ...to emulate two way infinite, thats why i am not able to understand .. – Harshal Carpenter Feb 05 '15 at 23:33
  • So, are there infinite many non-blanc places at both sides of the head ? – Peter Feb 05 '15 at 23:35

1 Answers1

1

As you know, the procedure cannot be to somehow specify at the start how many leftward squares you will need. You know that is impossible. Rather the procedure is to treat just the actually-even-numbered squares to the right as if they were all the squares on the right, while you treat actually-odd-numbered squares to the right as if they were to the left. Is that what you meant by "folding"?

Colin McLarty
  • 1,956