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 every (the length of ), the th element of is 1 if ; and is 0 otherwise. For example, extends the string . A string is winning determining if every 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: 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 every 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 apply this result to an investigation of the Nakamura numbers for simple games in cooperative game theory and social choice theory. See also Gödel's incompleteness theorems Halting problem Recursion theory Rice–Shapiro theorem Scott–Curry theorem, an analogue to Rice's theorem in lambda calculus Turing's proof Wittgenstein on Rules and Private Language Notes References External links Articles containing proofs Theorems in theory of computation Theorems in the foundations of mathematics Undecidable problems