It is not difficult to see that this restriction does not affect the power of the
machine. To simulate a standard Turing machine M by a machine with a
semi-infinite tape, we use the arrangement shown in Figure 10.3.
The simulating machine has a tape with two tracks. On the upper one, we
keep the information to the right of some reference point on M’s tape. The
reference point could be, for example, the position of the read-write head at the
start of the computation. The lower track contains the left part of M’s tape in
reverse order. is programmed so that it will use information on the upper
track only as long as M’s read-write head is to the right of the reference point,
and work on the lower track as M moves into the left part of its tape. The
distinction can be made by partitioning the state set of into two parts, say Qu
and QL: the first to be used when working on the upper track, the second to be
used on the lower one. Special end markers # are put on the left boundary of the
tape to facilitate switching from one track to the other. For example, assume that
the machine to be simulated and the simulating machine are in the respective
configurations shown in Figure 10.4 and that the move to be simulated is
generated by
δ (q i , a) = (q j , c, L).
The simulating machine will first move via the transition
where
∈ Q u . Because belongs to Q u , only information in the upper
track is considered at this point. Now, the simulating machine sees (#, #) in state
∈ Q U . It next uses a transition
Figure 10.4
machine. To simulate a standard Turing machine M by a machine with a
semi-infinite tape, we use the arrangement shown in Figure 10.3.
The simulating machine has a tape with two tracks. On the upper one, we
keep the information to the right of some reference point on M’s tape. The
reference point could be, for example, the position of the read-write head at the
start of the computation. The lower track contains the left part of M’s tape in
reverse order. is programmed so that it will use information on the upper
track only as long as M’s read-write head is to the right of the reference point,
and work on the lower track as M moves into the left part of its tape. The
distinction can be made by partitioning the state set of into two parts, say Qu
and QL: the first to be used when working on the upper track, the second to be
used on the lower one. Special end markers # are put on the left boundary of the
tape to facilitate switching from one track to the other. For example, assume that
the machine to be simulated and the simulating machine are in the respective
configurations shown in Figure 10.4 and that the move to be simulated is
generated by
δ (q i , a) = (q j , c, L).
The simulating machine will first move via the transition
where
∈ Q u . Because belongs to Q u , only information in the upper
track is considered at this point. Now, the simulating machine sees (#, #) in state
∈ Q U . It next uses a transition
Figure 10.4