4.2 Examples of Turing Machines 177
Next, we argue that these configurations, when arranged in the right order,
form the computation path of M on X. What is the right order on these
configurations? It is the order defined by the relation + on these pairs when
they were matched by rules (i) , (ii), (iii), (ii’) and (iii’) above. That is, if the
two pairs (PI,&) and (~2, 02) have the relation (PI,&) -+ (~2, Dz), then
their two corresponding configurations al and CQ satisfy clcl t- CQ. (We allow
the special case of
(h, x0 l l l xi l l l z,+1) I- (h, x0 l l *xi+1 l l l Gn+1)*)For instance, suppose that (~1, R) in Si and (~2, R) in Si+l satisfy (~1, R) +
(p2,R), and that PI # h. Then, by rule (iii), we know that J(pl, xi) =
(~2, xi, R). So, the corresponding configurations satisfy
(pl,xo-xi x,+1) t- (P2, x0 l l xi+1 l “Gn+l)*
The other cases can be verified in a similar way.
Now, we observe that if Si 2 $+I, then each pair (p, R) in Si+l has
either a predecessor (a, R) in Si or a predecessor (Q, L) in Si+l (under relation
-+). Also, each pair (p, L) in Si has either a predecessor (4, R) in Si or a
predecessor (4, L) in Si+l (under relation +). This observation, together withthe fact that So has a unique pair (s, R) which does not have a predecessor,
shows that every pair (q, D) in any crossing sequence Si , 1 < i < m + 1,
has a predecessor. Furthermore, from the recursive rules (ii), -(iii) r( ii’) and
(iii’), it is clear that each pair has a unique predecessor. In other words,the configurations corresponding to these pairs (4, D) form a linear chain,
starting from the initial configuration to the configuration (h, x0 l l l xm+l).We conclude that M accepts x. -0
Exercises 4.2
- For each of the following DTM’s, trace the machine and show the com-
putation on the given inputs:
(a) The DTM MA of Example 4.3 on inputs 0100 and 01010.
(b) The DTM of E xample 4.5 on inputs 0110 and 01010.
(c) The DTM of E xample 4.6 on inputs (3,0) and (0,3).(d) The DTM M of Example 4.9, with k = 3 and i = 2, from config-
uration (ql , BaaBBabBbbaBaba) - to (al, BaaBaBabBbbaBab). -
2. Construct DTM’s for procedures R and T of Example 4.9.
3. Construct DTM’s to decide the following languages:
(a) {ww I w E {0,1)‘~*
(b) {wwRw 1 w E {O,l}*}.