4.2 Examples of Turing Machines 175
sequence Si between the boundary of Ci- 1 and Ci , reads the symbol a in cell
Ci, and nondeterministically guesses the next crossing sequence Si+l between
Ci and Ci+l. After the guess, it then verifies that sequences Si and ,$+I are
consistent with respect to symbol a. It continues to the next step if S; and
S i+l are indeed consistent. At the end, if the last pair of the crossing sequence
S n+l is (h, R), then it accepts the input.
To implement this idea by an NFA, we must decide, from the transition
function S, whether two crossing sequences S and T are consistent. That is,
we need to check whether there exists a computation path in which S and
T occur as the two crossing sequences around a symbol a E C U (B}. This
notion can be made more precise by the following recursive definition. First,
let QR (and QL) be th e collection of all crossing sequences whose first pair
is (5 R) (and, respectively, (4, L)) for some q E Q U {h}. Consider a symbol
a E I’. Then, two crossing sequences S = (( 41, R), (qz, L),... , (qk, Dk)) and
T = ((PI, R), (P2A l l l 7 (pe, De)) in QR are consistent with respect to symbol
a (denoted by S G T), if one of the following conditions holds:
(i) Both S and T are empty, or both S and T are the singleton sequence
((h, R)). In the latter case, we write (ql, R) -+ (~1, R).
(ii) 6(q1, a) = (q2, a, L), and S” = ((43, R),.. .) (qk, Dk)) and T in QR have
the relation S” & T. In this case, we write (ql, R) + (q2, L).
(iii) S(ql,a) = (p~,a,R), and S’ = ((q2,L),(qs,R),-,(qk,Dk)) and T’ =((P2, L), (P3, R), ’ l. , (pe, De)) in QL have the relation S’ & T’. In this
case, we write (ql, R) -+ (~1, R).
Also, two crossing sequences S = ((ql , L), (q2, R),... , (qk , ok)) and T =
((Pl,L),(P2,R),**‘, (~1, De)) in QL are consistent with respect to symbol a
(also denoted by S $ T), if one of the following conditions holds:
(i’) Both S and T are empty.(ii’) S(pl, a) = (~2, a, R), and S and T” = ((~3, L),.. l , (PC, De)) in QL have
the relation S G T”. In this case, we write (~1, L) + (~2, R).
(iii’) &%,a) = (Ql, a, L), and s’ = ((42, R), (43, L), * ’ l 7 (qk, Dk)) and T’ =((P2, R), (P3, L), l l. , (pe, Dl)) in QR have the relation S’ $ T’. In this
case, we write (pl, L) + (ql, L).
For instance, consider, in Figure 4.10, the crossing sequences S = ((p, R))
and T = ((CL R), (5 L), (P, R)) at th e t wo sides of cell Cl. We can verify that
S & T as follows:(1) Sequences So = 8 and To = 0 are consistent sequences in QL (by rule
‘I
(^1 >>.