Problem Solving in Automata, Languages, and Complexity

5.4 Reducibility 255

and
x E FIN <q VV$ is infinite
+=a (VWY) [Y > - x and Y E wi?]

• (‘d4(3Y) [Y > iTic and (3t) paqy, o)]]
  a (VZ)(~W) [l(w) > - x and halt(l(w),x,r(w)].

Therefore, both sets TOT and FIN have the form

for some recursive predicate R. Furthermore, we know from earlier examples

that they are neither r.e. nor co-r.e. Therefore, they do not have a simpler

form of {x ] (3~) Q(x, y)} or {x ] (Vy) Q(x, y)} for any recursive predicate Q.

This suggests that these two sets have the same degree of zansoluability.

Now, we present the reductions between them. First, we prove TOT Lrn

FIN. Define a function

1

g(x’ ‘) = { T

if (V&GJ [x E w,],

otherwise.

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

pqp+<y ha+, x, t)]*

(Note: (VZ)~Q is a bounded quantifier, and so [(VZ)~<~ halt@, x,t)] is a

recursive predicate.)

-

By the enumeration theorem and the s-m-n theorem, there exists a recur-

sive function f such that for all x, y 2 0, +f(X~ (y) = g(x, y). Now we observe

that if x E TOT, then IV3 = {O,l}* and so the condition (VX)~.Q, [x E Wij’

holds for all y > 0. It follows that VI+(,) = (0, l}* and is infinite.-Conversely,

if x 4 TOT, then W, # (0, l}*. Let yo be the least string in w,. Then,

g(x, y) T for all y > - yo. That is, W,(,) = {y ] g(x, y) j,} is finite. Therefore, f

is a reduction function for TOT Lrn FIN.

Next, we prove FIN Lrn TOT. We define a function

Then,

h(x, Y) = (34 V(w) L Y and haw-4 x, r(w)>],

and so h is partial recursive.

By the enumeration theorem and the s-m-n theorem, there is a recursive

function k such that for all x, y > 0, &+)(y) = h(x, y). Now, if x E FIN then

for every y > - 0, the condition (3z),>, [z E VVJ holds and so VVj+) = (0, l}*.

Conversely, if x E FIN, then M& is-finite. Let yo be the greatest integer in

Vi& (or, let yo = 0 if VI& = 8). Then, the condition (3x),>, [x E VVJ does not

hold for all y > yo. It follows that VV&) is finite and is not equal to (0, l}*.

This shows that JG is a reduction function for FIN Lrn TOT. cl