11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You duplicate the states and the tape symbols, so that you have a version for the right part and another for the left part. On the tape, you store pairs of symbols, a left one and a right one. You adjust the transition function so that it changes only the part of the pair corresponding to the half tape you are currently working with. And add a bit of management when you have to change the half tape you are considering. Do not forget that if you fold the right half-tape onto the left, the head motions are reversed. So change your transitions for right states accordingly. $\endgroup$ – babou Mar 20 '14 at 15:04
  • $\begingroup$ @babou Turn into a full-fledged answer? $\endgroup$ – Yuval Filmus Mar 20 '14 at 18:06
12
$\begingroup$

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 tape, on a Turing machine with a singly infinite tape.

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 beyond 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.

$\endgroup$
  • $\begingroup$ @D.W. Thanks for the edit. I should have thought on doing it. As I recall, I inserted the last line as an after-thought during the 5 minutes grace period after editing. Given the existing rules on the number of edits, I usually wait to collect needed changes, before a new editing session. $\endgroup$ – babou Mar 21 '14 at 8:51
  • $\begingroup$ Ahh, yes, the edit rules! I'm not a fan of the rules that limit the number of edits; anytime it makes people reluctant to improve their answer seems like a loss for the site, but oh well, whaddya gonna do? Sorry I bumped your edit count by one -- I didn't want to bother you given the amount of work you already put in, but maybe I should have asked first. Thanks for the great answer! $\endgroup$ – D.W. Mar 21 '14 at 16:27
  • $\begingroup$ Question asking for an efficient simulation: cs.stackexchange.com/questions/28901/… $\endgroup$ – Ciro Santilli 新疆改造中心996ICU六四事件 Jun 6 '16 at 8:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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