Problem Solving in Automata, Languages, and Complexity

5.4 Reducibility 251

Then, g is partial recursive since g(y, x) = CT&C). (Recall that flK is the
semi-characteristic function of set K.)
By the enumeration theorem, g = 4: for some e > 0. For this fixed e,
define f( 2) = si(e,z>. We check that if x E Iii, then -

kfw (d = “&!,x) (Y> = &Y, 2) = il(Y, x) = 1,

for all y E {O,l} and so VI+(,) = {O,l} # 8. Also, if x $z! I<, then

&f(z)(Y) = 43YY x) = !l(Y, x) ?,

for all y E (0, l}* and so W,(,) = 8. Thus, f is a reduction function for

IiT <7n EMP. cl

The following is another simple example. We say an r.e. set A is complete

(with respect to the many-one reducibility) if B & A for all r.e. sets B. A

complete r.e. set is not recursive, for otherwise all r.e. sets would be recursive.

Example 5.29 The halting problem I< is complete.

Proof. Let B be an r.e. set. We need to construct a reduction B srn I<.

Define

1 ifxEB,

‘(” ‘) = { t otherwise.

Then, g is partial recursive since g( y, x) = Q(X).

By the enumeration theorem, g = 4,” for some e > 0. For this fixed e, define

f(x) = s:(e,x). We check that if x E B, then $$+T(y) = @(y,x) = g(y,x) =

1 for all y E {O,l}* and, in particular, cbf(,)(f(z)) = 1 and so f(x) E I<.

Also, if x C$ B then $f&y) = &(y,x) = g(y,x) t for all y E {O,l}* and so

f(x) $ II. Thus, f is a reduction function for B Fm I<.^0

By the transitivity of the reducibility <m, an r.e. set A is complete if

I< & A. For instance, Example 5.27 showed that EMP is a complete r.e. set.

Index Sets. We say a set A C {O,l}* is a function-index set if for any

x, y E {O,l}*, & = & implies XA(Z) = x~(y); a set A C {O,l}* is a set-

index set (or, simply, an index set), if for any x, y E { 0, l}* ,W, = IVY implies

&I(x) = %4(Y)*^1 n other words, A is a function-index set (or, a set-index set)

if the membership question “x E?A” depends only on the fw-wtion qbx (or,

respectively, on the set W,), and does not depend on the machine A& that

computes &. Note that each set-index set is also a function-index set.

Each function-index set (or, a set-index set) corresponds to a property of

partial recursive functions (or, respectively, r.e. sets). We say the problem

of determining whether a partial recursive function f has the property P is

undecidable (from the code of a DTM that computes f) if the corresponding