Problem Solving in Automata, Languages, and Complexity

254 COMPUTABILITY THEORY

be

Yo

For the second part of the question, we choose,

any indexes such that WzO = JC and WY0 = {

E REC and W& C W&. So, REC is not r.e.

The same $0 and-y0 also work for REG.

For set REV, use any ~0 and yo such that W& =

for set REC, ~0 and y. to

Q j 1) ** Then, ~0 E REC,

(10) and WY0 = {lO,Ol}.

cl

* Example 5.34 Let A be an r.e. function-index set. Show that if x E A then

there exists y E A such that WY is a finite subset of W$. Thus, the following

sets are not r.e.: TOT, FIN.

Proof. Assume that A is a function-index set and that there exists an index

x0 E A such that (Vy)[W, is a finite subset of Wz, + y 4 A]. We need to

show that K <m A and so A is not r.e.

Define

g(z, x) = { fxo(z) if hdt(q xx:, z> = 0 and 2 E Wk-,y

otherwise.

Then, g is partial recursive since g(y, x) 4 and equals c$~~(x) if and only if

(3t)[halt( z, x0$)] and [ha&(x, x, z) = 01.

By the enumeration theorem, there exists e 2 0 such that &(z, x) = g(z, x).

Let f (4 = si (e, x). Suppose x 4 K. Then, h&(x, x, z) = 0 for all x > 0 and

so &f(x)(Z) = g(z, 2) =

the other hand suppose ?$“I! f

or all x > 0. It follows that f(x) EA. On

7 Let x0 =(minz)hult(x, x, z). Then, we have

ha&(x, x, z) = 6 if and only if x < x0. Therefore, Wf(,) = wx, n {Z 1 2 < zo}

is a finite subset of W,,, and so f(x) E A. The above proved that f is a

reduction function for li’ srn A. cl

The above examples showed either K 5m A or Ii’ <m A for many index

sets A. In addition, the s-m-n theorem can also beked to establish the

reductions between other index sets. For instance, the next example shows

that problems TOT and FIN are equivalent under the many-one reducibility. It

means that they have the same degree of unsolvability, in the sense that each

problem is solvable using the other problem as an orcacle, although neither is

r.e. nor co-r.e.

• Example 5.35 Show that TOT srn FIN and FIN srn TOT.

Proof. Before we give the formal proof, we present an informal analysis of the

sets TOT and FIN. We note that

x E TOT e Wx = {O,l}*

• (VY> [Y E Wx] - (Vy)(jt) [halt(y,x,t)],