Turing machine - infinite tape in one or two directions

Problem Detail: 

I have seen turing machines beeing represented with tapes infinite in one, and in two directions. Is there any difference in the power of such turing machines, or are they basically equivalent? In my head I think they are equivalent, since I guess that there must be some way to represent the two-way infinite tape as a one-way infinite tape, but I can't seem to find a proof or example.

Asked By : user2795095

Answered By : babou

They are equivalent in computational power. Anything computable by one of these two kinds of Turing machines, is computable by the other kind. Let's look at how to simulate a Turing machine with a doubly infinite machine, on a Turing machine with a singly infinite machine.

The idea is to cut your doubly infinite tape in two, so that you have two singly infinite tapes, a left one and a right one, which you will ultimately merge. You may mark the ends with a tape location containing a special EOF symbol. You also duplicate your finite control, so that you have two identical finite state controls. You assume that you have a control passing device (see below), so that, when the left machine tries to go beyong the right end of its tape, it passes the control to the right machine, on its leftmost tape position (just before the left end of the right tape). And conversely, when attempting to pass the left end of the right tape.

Now, in order to distinguish the left and the right machines, we change the names of the states and the tape symbols, by indexing them with $R$ and $L$ respectively for the left and the right machine. And we change accordingly the transitions of the two machines so that they work as before.

Now we are ready to merge the two half-tapes, for example by folding the right one onto the left one. For that you flip over the right half tape, and you are careful to modify accordingly the transitions, exchanging right for left and left for right. Then you fuse the two half tapes into a single tape containing pairs of symbols, a left one and a right one, each component being possibly blank.

You modify again the transitions of both machines, so that the left (resp. right) transitions use and modify only the left (resp. right) parts of the pairs on the tape. Then you merge the control of the two machines by simple set union respectively for states, and for transitions.

You add a set of transitions for each existing state, so that when the tape symbol is EOF, it goes back to the previous tape location (the first non-EOF location) and the state changes to its chiral counterpart: if it is a left (resp. right) state, it changes to its right (resp. left) counterpart. That is the control passing device.

I may have forgotten a detail, but this is the general idea of the construction. The proof is left as an execise.

Of course, the initial tape (input) must be modified accordingly. But that can be made simple by placing the input (if finite) fully on the left side (the one that is not flipped over) of the tape cut.

Then you put away the screw driver as it may be dangerous for the kids.

PS I only showed that the doubly infinite tape can be simulated with a singly infinite tape. The converse seems too obvious.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22863