Problem Solving in Automata, Languages, and Complexity

236 COMPUTABILITY THEORY

The above dovetailing algorithm can be simplifed by the projection theorem

as follows:

(Recall that (a, b) is the pairing function developed in Section 4.7, and E(z)

and r(z) are the inverse of the pairing function: x = (Z(x), r(a)).)

We note that using the last line of the proof by the projection theorem, we

can actually construct a simpler simulation algorithm because, by the use of

the pairing function, we only need to search for one string x instead of two

strings x and t:

(1) Set 2 := 0.

(2) Simulate A& on input x = Z(z) for t = r(x) moves. If it halts, then

accept; otherwise, go to step (3).

(3) Reset z := z + 1, and go back to step (2). Cl

Example 5.11 Show that if A is r.e. then B = (JyEA WY is also r.e.

Proof. Assume that A = Mn. Intuitively, we need to simulate AL& on all

possible inputs and then, for each y found in W,, to simulate A& on the given

input x. All these simulations need to be dovetailed, and the algorithm does

not seem simple at all (see Exercise 2).

On the other hand, the projection theorem gives us a very simple proof’

(and, hence, a simple simulation algorithm) :

XEB u (jy)[yE Wn andxe WY]

• (3Y)W)[h4Y> 72, t) and huZt(x, y, t)]
  u (3x)[halt(Z(z), n, Y(Z)) and haZt(x, Z(z), r(z))].

It follows that B is r.e. q l

Example 5.12 Show that the range of a partial recursive function f :
{O,l} + {O,l} is an r.e. set.

Proof. Assume that f = & and let A be the range of f. Then, we have

z E A e (ilx)(Zlt)print(x, x, y, t)

• (3w)Prqqw), 6 Y, r(w))* El

We say a tape of a DTM is a one-way write-only tape to mean that the

DTM can only write on the tape and once a symbol is written, the tape head

moves to the right and is not allowed to move left. We say an infinite set A is

Turing-enumeruble if there exists a two-tape DTM M, whose second tape is a