Section 10.1
4. (a) The machine has a transition function
with the restriction that for all transitions δ (q i , a) = (q j , b, L or R), the
condition a = b musthold.
(b) To simulate δ (q i , a) = (q j , b, L) with a ≠ b of the standard machine, we
introduce new transitions δ (q i , a) = (q jL , b, S) and δ (q jL , b) = (q j , b, L)
for all , and so on.
6. We introduce a pseudo-blank B. Whenever the original machine wants to
write , the new machine writes B. Then, for each δ (q i , ) = (q j , b, L) we
add δ (q i , B) = (q j , b, L), and so on. Of course, the original transition δ (q i , )
= (q j , b, L) must be retained to handle blanks that are originally on the tape.
9. This does not limit the power of the machine. For each symbol
, we
introduce a pseudo-symbol, say A. Whenever we need to preserve this a, we
first write A, then return to the cell in question to replace A by a.
11. We replace
by
for all
.
Section 10.2
2. For the formal definition use
and
, where m is the number of read-write heads.
One issue to consider is what happens when two read-write heads are on the
same cell. The formal definition must provide for the resolution of possible
conflicts.
To simulate the original machine (OM) by a standard Turing machine (SM),
we let SM have m + 1 tracks. On one track we will keep the tape contents of