Rice's Theorem - An Analogue of Rice's Theorem For Recursive Sets

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 any recursive set whether it has a certain property, then finitely many integers determine whether a recursive set has the property. This result is analogous to the original Rice's theorem because both 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 for a recursive set belonging to, then the algorithm gives "yes";
• if is a characteristic index for a recursive set not belonging to, then the algorithm gives "no".

A set extends a string of 0's and 1's if for any (the length of ), the th element of is 1 if ; is 0 otherwise. For example, extends string . A string is winning determining if any recursive set extending belongs to . A string is losing determining if no recursive set extending belongs to .

We can now state the following analogue of Rice's theorem (Kreisel, Lacombe, and Shoenfield, 1959, Kumabe and Mihara, 2008):

A class of recursive sets is computable if and only if there are a recursively enumerable set of losing determining strings and a recursively enumerable set of winning determining strings such that any recursive set extends a string in .

This result has been applied to foundational problems in computational social choice (more broadly, algorithmic game theory). For instance, Kumabe and Mihara (2008, 2008) apply this result to an investigation of the Nakamura numbers for simple games in cooperative game theory and social choice theory.