234 COMPUTABILITY THEORY
(1) S([qs, qj], (a, b)) = (h, (a,b), (S,S)), for 1 < j < 6 and Cl E L-h b E Lm
(a> S([qi, qt], (a, b)) = (h, (a, b), (S, S)), for 1 & - ys, - and a E L, b E rm,
where I& and rm are the sets of tape symbols of Mn and Mm, respectively.
Next, we construct a DTM M’ for set D = AnB. The machine M’ behaves
like machine M, except that it needs to continue simulating Mn or Mm when
the simulation of the other DTM halts. That is, M’ contains all instructions of
M, except for those in (1) and (2)) plus the following additional instructions:
(3) For each instruction 6, (qil, al> = (qiz7 a2, Dl) Of Mn 9 add a new instruc-
tion
S([Qil) qt], (al, h)) = ([t&Y qtl, (Q5 bd7 (01, w*(4) For each instruction S, (qj,, bl) = (qj,, b2, D2) of Mm, add a new in-
structionS’([qs, qj,], (al, bl)) = ([as, Qj,lY (%b2)J (S, D2))*Also, M’ has a single halting state [qS, qt]. 0
Proof 2 (by douetuiling). In order to simulate Mn and Mm, we do not need
to combine Mn and Mm together to form the product DTM. We may simply
include two machines Mn and Mm as two subprocedures of a new DTM M,
which can use them to simulate their computation. Since we do not know
which one of the two machines halts first and how many moves it takes before
it halts, the machine M needs to simulate both machines for an indefinite
number of moves. How does it do that? It first simulates each machine for
t- 1 move. If neither machine halts, it increases t by one and simulates each
of them for 2 moves. If neither machine halts in 2 moves, it increases t again
and continues the simulation until one of them halts. This technique is more
general than the product DTM technique and has many other applications.
We call it the dovetailing technique.
More precisely, for set C = AUB, the dovetailing algorithm M on an input
~xf works as follows:
(1) Set t := I.
(2) Simulate Mn on x for t moves. If it halts, then halt; otherwise, go toI
(3).
(3) Simulate Mm on x for t moves. If it halts, then halt; otherwise, go toI
(4.
(4) Increase t by one, and go to step (2).
It is clear that the above algorithm halts if at least one of Mn or Mm
halts on X. Furthermore, the algorithm is quite simple, and we can easily see!
(by the Church-Turing Thesis) that it can be implemented by a DTM M. It,
follows that C is r.e.