result. 2. return P(t). We can now show that H decides the halting problem: Assume that the algorithm represented by a halts on input i. In this case Ft = Fb and, because P(b) = "yes" and the output of P(x) depends only on Fx, it follows that P(t) = "yes" and, therefore H(a, i) = "yes". Assume that the algorithm represented by a does not halt on input i. In this case Ft = Fno-halt, i.e., the partial function that is never defined. Since P(no-halt) = "no" and the output of P(x) depends only on Fx, it follows that P(t) = "no" and, therefore H(a, i) = "no". Since the halting problem is known to be undecidable, this is a contradiction and the assumption that there is an algorithm P(a) that decides a non-trivial property for the function represented by a must be false. Rice's theorem and index sets Rice's theorem can be succinctly stated in terms of index sets: Let be a class of partial recursive functions with index set . Then is recursive if and only if or . Here is the set of natural numbers, including zero. An analogue of Rice's theorem for recursive sets One can regard Rice's theorem as asserting the impossibility of effectively deciding for any recursively enumerable set whether it has a certain nontrivial property. In this section, we give an analogue of Rice's theorem for recursive sets, instead of recursively enumerable sets. Roughly speaking, the analogue says that if one can effectively determine for every recursive set whether it has a certain property, then only finitely many integers determine whether a recursive set has the property. This result is analogous to the original theorem of Rice, because both results assert that a property is "decidable" only if one can determine whether a set has that property by examining for at most finitely many (for no , for the original theorem), if belongs to the set. Let be a class (called a simple game and thought of as a property) of recursive sets. If is a recursive set, then for some , computable function is the characteristic function of . We call a characteristic index for . (There are infinitely many such .) Let's say the class is computable if there is an algorithm (computable function) that decides for any nonnegative integer (not necessarily a characteristic index), if is a characteristic index