Problem Solving in Automata, Languages, and Complexity

5.2 RX. Sets and Recursive Sets 235

For set D = A n B, we do not have to simulate A& and A& alternatingly,
because tie need to wait for both machines to halt anyway. So, the algorithm
is simpler:
(1) Simulate A& on x until it halts; then go to step (2).
(2) Simulate Mm on z. If it halts, then halt.^0

Proof 3 (by the projection theorem). Assume that A = L(Mn) and B =

L(Mm). Then, by the projection theorem, A = {z 1 (3tl) h&(x, n,ti)} and

B = {x 1 (3t2) haZt( x, nz, tz)}. Now, observe that x E A U B if and only if

(3t)[halt( x, n, t) or haEt(x, m, t)].

It follows from the projection theorem that A U B is r.e.

For set A f/ B, the proof is similar: x E A f~ B if and only if

(3t)[halt( x, n, t) and halt(x, m, t)].^0

At first glance, it seems that Proof 3 is totally different from Proofs 1 and 2,

since it avoids the construction of the DTM simulators completely. However, if

we examine the proof more carefully, we can see that it actually uses the same

idea of the dovetailing simulation, except that it uses the existential quantifier

(3) and a simple operator or (and, in the case of A f~ B, the operator and)

to encode the whole algorithm of Proof 2. In the following, we will see more

examples of using the projection theorem to simplify the proofs.

Example 5.10 Show that the set {y 1 WY # 8) is r.e.

Proof. The idea is, for a given input y, to simulate MY on all possible inputs;

and halt whenever one of the simulations halts. This simulation algorithm1

is more complicated than that of Proof 2 of Example 5.9, since we need to)

dovetail through an infinite number of simulations. The algorithm may be:

described as follows:

(1) Set t := 1.

(2) Set x := E.

(3) If 1x1 < t, th en simulate Mg on x for t moves. If it halts, then halt;

othervke, go to step (4). If 1x1 > t, then go to step (5).

(4) Reset x := x +^1 (i.e, let x

ordering), and go to step (3).

be the next string in the lexicographic

(5) Reset t := t + 1, and go to step (2).

Note that if WY is not empty then there must be a string w and a number

n such that MY halts on w in n moves. By the time the algorithm reaches the

stage with t = max{n, lwl} and x = w, the simulation of MY on x will halt (if

the algorithm did not halt before this stage). Therefore, the above algorithm

is correct.