Problem Solving in Automata, Languages, and Complexity

5.4 Reducibility 257

(b) Show that if B is an r.e. index set then nnEB Wn is also r.e.

9. Let Cl be the class of all recursive sets, Cz the class of all r.e. sets which
   are not recursive, C3 the class of all co-r.e. sets which are not r.e., and
   Cd the class of all sets that are neither r.e. nor co-r.e. For each of the
   following sets, determine in which class Ci, i E { 1,2,3,4}, it belongs to.
   (a) B1 = {x 1 A& (2) halts in at most 200 moves}.
   (b) B2 = {x I h(x) > 9).
   (c> J33 = {a: I Iml > 5).
   (d) B4 = {x I IKI 5 x}
   (e> B5 = {(XYY) I Y E ~wP+w
   (f) I?6 = {(x,y)I q&(y) is defined or q&(x) is undefined}.
   (g) B7 = b-2 I& = b-h,), w h ere no is a fixed positive integer.
   (h) B8 = {a: I range of & is finite}.
   (i) Bg = {n I Wn C P}, where P is the set of primes.
   (j) BIO = (72 1 w,- P}, where P is the set of primes.
   (9 Bll = {n 1 w, - c K}.


10. A set A is called single-valuecd if for each y, there exists at most one x
    such that (y, z> E A. Let B12 = {xl VI& is single-valued}. Show that
    EMP Lrn B12 and B12 & - EMP,


11. (a) Show that th ere is a recursive predicate R such that

x E REC e (3y)(Vz)(3w) R(x, y, z, w).

(b) Let COINF = {X I l/lrs is infinite}. Show that there exists a recur-

sive predicate Q such that

II: E COINF e (Vy)(3z)(‘dw) Q(x, y, x, w).

* 12. Prove the following reductions:

(a) TOT Lm REC.

(b) TOT & - COINF.

13. Let B13 = {x 1 WL = AT}.
    (a) Show that th ere exists a recursive predicate R such that

x E B13 - (QY)@) R(z, Y, 2).

• (b) Show that B (^13) - < TOT and TOT srn B13.

14. Let B14 = {x I (3y E Wz) [WY is infinite]}.
    (a) Show that there exists a recursive predicate R such that

x E B14 - pY)(vqw qx, Y, 2, w>*