Rice's theorem

From Wikipedia, the free encyclopedia

In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, does the program terminate for all inputs), unlike a syntactic property (for instance, does the program contain an if-then-else statement). A property is non-trivial if it is neither true for every program, nor false for every program.

Rice's theorem can also be put in terms of functions: for any non-trivial property of partial functions, no general and effective method can decide whether an algorithm computes a partial function with that property. Here, a property of partial functions is called trivial if it holds for all partial computable functions or for none, and an effective decision method is called general if it decides correctly for every algorithm. The theorem is named after Henry Gordon Rice, who proved it in his doctoral dissertation of 1951 at Syracuse University.

In other terms, it tells us that it's impossible to create a computer program that can reliably decide certain interesting things about other programs. Specifically, when it comes to aspects like how a program behaves during its execution, there's no universal method to determine if a program has a particular, more intricate trait. If you have a property that applies to formal languages, and there's at least one example of a language with that property and one without, determining if a given Turing machine has that property becomes an undecidable problem.


Let p be a property of a formal language L that is nontrivial, meaning

  1. there exists a recursively enumerable language having the property p,
  2. there exists a recursively enumerable language not having the property p,

(that is, p is neither uniformly true nor uniformly false for all recursively enumerable languages).

Then it is undecidable to determine for a given Turing machine M, whether the language recognized by it has the property p.

In practice, this means that there is no machine that can always decide whether the language of a given Turing machine has a particular nontrivial property. Special cases include e.g. the undecidability of whether the language recognized by a Turing machine could be recognized by a nontrivial simpler machine, such as a finite automaton (meaning, it is undecidable whether the language of a Turing machine is regular).

It is important to note that Rice's theorem does not concern the properties of machines or programs; it concerns properties of functions and languages. For example, whether a machine runs for more than 100 steps on a particular input is a decidable property, even though it is non-trivial. Two different machines recognizing exactly the same language might require a different number of steps to recognize the same input string. Similarly, whether a machine has more than five states is a decidable property of the machine, as the number of states can simply be counted. For properties of this kind, which concerns a Turing machine but not the language recognized by it, Rice's theorem does not apply.

Using Rogers' characterization of acceptable programming systems, Rice's theorem may essentially be generalized from Turing machines to most computer programming languages: there exists no automatic method that decides with generality non-trivial questions on the behavior of computer programs.

As an example, consider the following variant of the halting problem. Let P be the following property of partial functions F of one argument: P(F) means that F is defined for the argument '1'. It is obviously non-trivial, since there are partial functions that are defined at 1, and others that are undefined at 1. The 1-halting problem is the problem of deciding of any algorithm whether it defines a function with this property, i.e., whether the algorithm halts on input 1. By Rice's theorem, the 1-halting problem is undecidable. Similarly the question of whether a Turing machine T terminates on an initially empty tape (rather than with an initial word w given as second argument in addition to a description of T, as in the full halting problem) is still undecidable.

Formal statement[edit]

Let denote the natural numbers, and let denote the class of unary (partial) computable functions. Let be an admissible numbering of the computable functions. Denote by the eth (partial) computable function.

We identify each property that a computable function may have with the subset of consisting of the functions with that property. Thus, given a set , a computable function has property if and only if . For each property there is an associated membership decision problem of determining, given e, whether .

Rice's theorem states that the decision problem is decidable (also called recursive or computable) if and only if or .


According to Rice's theorem, if there is at least one partial computable function in a particular class C of partial computable functions and another partial computable function not in C then the problem of deciding whether a particular program computes a function in C is undecidable. For example, Rice's theorem shows that each of the following sets of partial computable functions is undecidable (that is, the set is not recursive, or not computable):

  • The class of partial computable functions that return 0 for every input, and its complement.
  • The class of partial computable functions that return 0 for at least one input, and its complement.
  • The class of partial computable functions that are constant, and its complement.
  • The class of partial computable functions that are identical to a given partial computable function, and its complement.
  • The class of partial computable functions that diverge (i.e., undefined) for some input, and its complement.
  • The class of indices for computable functions that are total.[1]
  • The class of indices for recursively enumerable sets that are cofinite.
  • The class of indices for recursively enumerable sets that are recursive.

Proof by Kleene's recursion theorem[edit]

A corollary to Kleene's recursion theorem states that for every Gödel numbering of the computable functions and every computable function , there is an index such that returns . (In the following, we say that "returns" if either , or both and are undefined.) Intuitively, is a quine, a function that returns its own source code (Gödel number), except that rather than returning it directly, passes its Gödel number to and returns the result.

Assume for contradiction that is a set of computable functions such that . Then there are computable functions and . Suppose that the set of indices such that is decidable; then, there exists a function that returns if , and otherwise. By the corollary to the recursion theorem, there is an index such that returns . But then, if , then is the same function as , and therefore ; and if , then is , and therefore . In both cases, we have a contradiction.

Proof by reduction from the halting problem[edit]

Proof sketch[edit]

Suppose, for concreteness, that we have an algorithm for examining a program p and determining infallibly whether p is an implementation of the squaring function, which takes an integer d and returns d2. The proof works just as well if we have an algorithm for deciding any other nontrivial property of program behavior (i.e. a semantic and non-trivial property), and is given in general below.

The claim is that we can convert our algorithm for identifying squaring programs into one that identifies functions that halt. We will describe an algorithm that takes inputs a and i and determines whether program a halts when given input i.

The algorithm for deciding this is conceptually simple: it constructs (the description of) a new program t taking an argument n, which (1) first executes program a on input i (both a and i being hard-coded into the definition of t), and (2) then returns the square of n. If a(i) runs forever, then t never gets to step (2), regardless of n. Then clearly, t is a function for computing squares if and only if step (1) terminates. Since we've assumed that we can infallibly identify programs for computing squares, we can determine whether t, which depends on a and i, is such a program; thus we have obtained a program that decides whether program a halts on input i. Note that our halting-decision algorithm never executes t, but only passes its description to the squaring-identification program, which by assumption always terminates; since the construction of the description of t can also be done in a way that always terminates, the halting-decision cannot fail to halt either.

 halts (a,i) {
   define t(n) {
     return n×n
   return is_a_squaring_function(t)

This method doesn't depend specifically on being able to recognize functions that compute squares; as long as some program can do what we're trying to recognize, we can add a call to a to obtain our t. We could have had a method for recognizing programs for computing square roots, or programs for computing the monthly payroll, or programs that halt when given the input "Abraxas"; in each case, we would be able to solve the halting problem similarly.

Formal proof[edit]

If we have an algorithm that decides a non-trivial property, we can construct a Turing machine that decides the halting problem.

For the formal proof, algorithms are presumed to define partial functions over strings and are themselves represented by strings. The partial function computed by the algorithm represented by a string a is denoted Fa. This proof proceeds by reductio ad absurdum: we assume that there is a non-trivial property that is decided by an algorithm, and then show that it follows that we can decide the halting problem, which is not possible, and therefore a contradiction.

Let us now assume that P(a) is an algorithm that decides some non-trivial property of Fa. Without loss of generality we may assume that P(no-halt) = "no", with no-halt being the representation of an algorithm that never halts. If this is not true, then this holds for the algorithm P that computes the negation of the property P. Now, since P decides a non-trivial property, it follows that there is a string b that represents an algorithm Fb and P(b) = "yes". We can then define an algorithm H(a, i) as follows:

1. construct a string t that represents an algorithm T(j) such that
  • T first simulates the computation of Fa(i),
  • then T simulates the computation of Fb(j) and returns its 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, index sets and saturated sets[edit]

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.

If a particular set holds this property, the set is considered saturated, meaning whenever a program with a certain property is in the set, all other programs that compute the same function are also in the set. This implies that the set is "complete" with respect to the property in question for programs computing a particular function.

The property does not depend on the program but on the function it computes. A saturated set contains all the indices (which are infinite) of programs that compute functions with a particular common characteristic.

This property holds extensionally, so it is considered extensional because it depends only on the elements that belong to a set, not on the specific way those elements are represented or defined. This can be used to prove a set is not recursive with the following statement:

Let be a set and . If is saturated, then is not recursive.

In simpler terms, the saturation property implies that contains all the indices of programs that compute functions with a common characteristic. This property holds extensionally, meaning it solely depends on the elements within the set without consideration for their internal representations.

The significance of this in proving non-recursiveness lies in the inherent uncertainty: we cannot definitively determine whether a program possesses a specific property precisely. The extensional nature of saturation highlights the challenge in establishing a recursive enumeration for the set , reinforcing its non-recursive nature.

An analogue of Rice's theorem for recursive sets[edit]

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.[2] In this section, we give an analogue of Rice's theorem for recursive sets, instead of recursively enumerable sets.[3] 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 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:[4][5]

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[5][6] apply this result to an investigation of the Nakamura numbers for simple games in cooperative game theory and social choice theory.

See also[edit]


  1. ^ Soare, Robert I. (1987). Recursively Enumerable Sets and Degrees. Springer. p. 21. ISBN 9780387152998.
  2. ^ A set is recursively enumerable if for some , where is the domain (the set of inputs such that is defined) of . The result for recursively enumerable sets can be obtained from that for (partial) computable functions by considering the class , where is a class of recursively enumerable sets.
  3. ^ A recursively enumerable set is recursive if its complement is recursively enumerable. Equivalently, is recursive if its characteristic function is computable.
  4. ^ Kreisel, G.; Lacombe, D.; Shoenfield, J. R. (1959). "Partial recursive functionals and effective operations". In Heyting, A. (ed.). Constructivity in Mathematics. Studies in Logic and the Foundations of Mathematics. Amsterdam: North-Holland. pp. 290–297.
  5. ^ a b Kumabe, M.; Mihara, H. R. (2008). "Computability of simple games: A characterization and application to the core". Journal of Mathematical Economics. 44 (3–4): 348–366. arXiv:0705.3227. doi:10.1016/j.jmateco.2007.05.012. S2CID 8618118.
  6. ^ Kumabe, M.; Mihara, H. R. (2008). "The Nakamura numbers for computable simple games". Social Choice and Welfare. 31 (4): 621. arXiv:1107.0439. doi:10.1007/s00355-008-0300-5. S2CID 8106333.