Problem Solving in Automata, Languages, and Complexity

252 COMPUTABILITYTHEORY

function-index set Ap = {z 1 P(&)} is not recursive. Similarly, the problem
of determining whether an r.e. set A has the property P is undecidable (from
the code of a DTM that accepts A) if the corresponding set-index set Ap =
{z 1 P(U&)} is not recursive.
For instance, the set EMP of Example 5.27 is a set-index set since the
question “x E?EMP” depends only on whether the set VVz is empty or not,
and we say that the problem of determining whether an r.e. set is empty is
undecidable. Similarly, set Al = {x 1 & (0) > 5) is a function-index set (but
not a set-index set). Rice’s theorem below shows that Al is not recursive
and so the problem of determining whether a partial recursive function f has
value f (0) > 5 is undecidable.
On the other hand, the set I{ = {x 1 x E PI&} is not an index set since
the question of whether x E I< not only depends on the set Wz but also on
the membership of x itself in W$. (For a formal proof that I< is not an index
set, see, e.g., Exercise 11 of Section 5.5.) Similarly, the set B1 = {x ] A&(O)
halts in at most 200 moves} is not an index set since we can easily design two
DTM’s AIY and A& computing the same function but one is in I31 and the
other not in Br.
We say an index set A is nontrivial if it is neither empty nor equal to (0, 1)‘.
Then, by the s-m-n theorem, we can prove that all nontrivial index sets are
nonrecursive. Thus, all nontrivial properties of partial recursive functions are
undecidable.

Theorem 5.30 (Rice’s Theorem) All nontrivial function-index sets are non-

recurswe.

Proof. Let A be a nontrivial function-index set. First, assume that all indices

x such that Wx = 8 are in A. We show that I< Lrn A. Choose a fixed x0 in

A, and define

am,

dY, x) = { t

if IX: E Ii’,

otherwise.

Then, g is partial recursive since g(y, x) = OK(X) l &, (y).

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

f( > = si(e,x). We check that if x E I<, then &&(y) = g(y,x) = &,(y)

forxall y E {O,l}*. Since A is a function-index set and x0 E A, it implies

that f(z) E A. On the other hand, if x 4 I< then 4f(X)(y) = g(y,x) t for all

y E {O,l}* and so Wj(,) = 8 and it follows that f(x) E A. Therefore, f is a

reduction function for Ii’ <m A, and it follows that A is not recursive.

Now, suppose that all indices x such that Wz = Q1 are in A. Then, by the

same argument (with x0 E A), we can prove that I< <m A and so A is not

recursive.^0

Corollary 5.31 The following sets are not recursive.

(a) Al = {x I &(O) > 5).

(!I) TOT = {X I Wx = {O,l}*}.