Problem Solving in Automata, Languages, and Complexity

5.4 Reducibility 253

(c) FIN = {Z 1 Wx is finite}.

(d) REC = {z 1 W, is recursive}.

(e) REG = {z 1 Wx is a regular set}.

(f) REV = {z ] VI& = w,R}.

Next, we apply the technique of reducibility to prove that some index sets

are not r.e. Our first result is a simple application of the proof of Rice’s

theorem.

Example 5.32 Let A be a nontrivial function-index set. Show that if EMP C

A, then A is not r.e. Thus, the following index sets are not r.e: Al, EMF,

TOT, FIN, REC, REG and REV.

Proof. From the proof of Rice’s theorem, we see that if EMP C A,

K Lrn A, or, equivalently, K Lrn A. It follows from Proposition 5.26 th

is not r.e.

Since sets Al, EMP, TOT, FIN, REC, REG and REV all contain EMP

subset, they are not r.e.

For set Al, there is another simple way to show that A1 is not r.e.

observe that

then

at A

We

x E A1 e (3)(3w) [print(O, w, x, t) and w > 51

e (3~) [print(O, l(z), x, r(z)) and Z(z) > 51.

So, by the projection theorem, Al is r.e. Also, by Rice’s theorem, Al is not

recursive. It follows from Theorem 5.15 that Al is not r.e.^0

* Example 5 33 Let A be an r.e. index set. Show that if x E A and Wz C WY

then y E A. Thus, the following sets are not r.e.:

- - -

REC, REG, REV.

Proof. Assume that A is an index set and that there exist x0 E A and yo sf A

such that WzO C WgO. We show that, then, K -Cm A and hence A is not r.e.

Define -

1

g(z’x) = { T

if z E WXO or [z E WY0 and x E I<],

otherwise.

Then, g is partial recursive since g( x, x) .J.. and equals 1 if and only if

(3t)[halt( x,x0, t) or [haZt(z, yo, t) and haZt(x, x, t)]].

By the enumeration theorem, there exists e > 0 such that c#$(z, x) = g(z, x).

IJet f (4 = si(e, x). If x E Ii’, then 9f&) = g(z,x), and so Wf(,) =

wyo u W& = w&v Thus, x E K implies f(x) E 2. On the other hand, if

x @ K, then WJ(,) = W& and so f(x) E A. Th is shows that f is a reduction

function for Ii’ <m - A and, hence, A is not r.e.