HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Turing machine - infinite tape in one or two directions

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
infiniteonetapetwomachineturingdirections

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#22863, answer score: 15

Revisions (0)

No revisions yet.