Rice's theorem
From Wikipedia, the free encyclopedia
In computability theory, Rice's theorem states that, for any nontrivial property of partial functions, there is no general and effective method to 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, and is also known as the RiceMyhillShapiro theorem after Rice, John Myhill, and Norman Shapiro.
Contents 
[edit] Introduction
Another way of stating this problem that is more useful in computability theory is this: suppose we have a set of languages S. Then the problem of deciding whether the language of a given Turing machine is in S is undecidable, provided that there exists a Turing machine that recognizes a language in S and a Turing machine that recognizes a language not in S. Effectively this means that there is no machine that can always correctly decide whether the language of a given Turing machine has a particular nontrivial property. Special cases include the undecidability of whether a Turing machine accepts a particular string, whether a Turing machine recognizes a particular recognizable language, and whether the language recognized by a Turing machine could be recognized by a nontrivial simpler machine, such as a finite automaton.
It is important to note that Rice's theorem does not say anything about those properties of machines or programs which are not also properties of functions and languages. For example, whether a machine runs for more than 100 steps on some input is a decidable property, even when it is nontrivial. Implementing exactly the same language, two different machines might require a different number of steps to recognize the same input. Where a property is of the kind that either of the two machines may or may not have it, while still implementing exactly the same language, the property is of the machines and not of the language, and Rice's Theorem does not apply.
Similarly, whether a machine has more than 5 states is a decidable property. On the other hand, the statement that "No modern generalpurpose computer can solve the general problem of determining whether a program is virus free" is a consequence of Rice's Theorem because, while a statement about computers, it can be reduced to a statement about languages.
Using Rogers' characterization of acceptable programming systems, this result may essentially be generalized to most computer programming languages: there exists no automatic method that decides with generality nontrivial questions on the blackbox behavior of computer programs. This is one explanation of the difficulty of debugging.
As an example, consider the following variant of the halting problem: Take the property a partial function F has if F is defined for argument 1. It is obviously nontrivial, since there are partial functions that are defined for 1 and others that are undefined at 1. The 1halting 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 1halting problem is undecidable.
[edit] Formal statement
Let be a Gödel numbering of the computable functions; a map from the natural numbers to the class of unary partial computable functions.
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 φ_{e} has property F if and only if . For each property there is an associated decision problem D_{F} of determining, given e , whether .
Rice's theorem states that the decision problem D_{F} is decidable if and only if or .
[edit] Examples
According to Rice's theorem, if there is at least one computable function in a particular class C of computable functions and another 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 computable functions is undecidable:
 The class of computable functions that return 0 for every input, and its complement.
 The class of computable functions that return 0 for at least one input, and its complement.
 The class of computable functions that are constant, and its complement.
[edit] Proof by Kleene's recursion theorem
A corollary to Kleene's recursion theorem states that for every Gödel numbering of the computable functions and every computable function Q(x,y), there is an index e such that φ_{e}(y) returns Q(e,y). (In the following, we will say that f(x) "returns" g(x) if either f(x) = g(x), or both f(x) and g(x) are undefined.) Intuitively, φ_{e} is a quine, a function that returns its own source code (Gödel number), except that rather than returning it directly, φ_{e} passes its Gödel number to Q and returns the result.
Let F be a set of computable functions such that . Then there are computable functions and . Suppose that the set of indices x such that is decidable; then, there exists a function Q(x,y) that returns g(y) if , f(y) otherwise. By the corollary to the recursion theorem, there is an index e such that φ_{e}(y) returns Q(e,y). But then, if , then φ_{e} is the same function as g, and therefore ; and if , then φ_{e} is f, and therefore . In both cases, we have a contradiction.
[edit] Proof by reduction to the halting problem
[edit] Proof sketch
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 d^{2}. The proof works just as well if we have an algorithm for deciding any other nontrivial property of programs, and will be given in general below.
The claim is that we can convert our algorithm for identifying squaring programs into one which identifies functions that halt. We will describe an algorithm which takes inputs a and i and determines whether program a halts when given input i.
The algorithm is simple: we construct a new program t which (1) temporarily ignores its input while it tries to execute program a on input i, and then, if that halts, (2) returns the square of its input. Clearly, t is a function for computing squares if and only if step (1) halts. Since we've assumed that we can infallibly identify program for computing squares, we can determine whether t is such a program, and therefore whether program a halts on input i. Note that we needn't actually execute t; we need only decide whether it is a squaring program, and, by hypothesis, we know how to do this.
t(n) { a(i) return n×n }
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", or programs that commit array bounds errors; in each case, we would be able to solve the halting problem similarly.
[edit] Formal proof
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 F_{a}. This proof proceeds by reductio ad absurdum: we assume that there is a nontrivial 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 nontrivial property of F_{a}. Without loss of generality we may assume that P(nohalt) = "no", with nohalt being the representation of an algorithm that never halts. If this is not true, then this will hold for the negation of the property. Since P decides a nontrivial property, it follows that there is a string b that represents an algorithm 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 F_{a}(i)
 then T simulates the computation of F_{b}(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 F_{t} = F_{b} and, because P(b) = "yes" and the output of P(x) depends only on F_{x}, 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 F_{t} = F_{nohalt}, i.e., the partial function that is never defined. Since P(nohalt) = "no" and the output of P(x) depends only on F_{x}, 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 nontrivial property for the function represented by a must be false.
[edit] 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 C. Then C is recursive if and only if C is empty, or C is all of ω.
where ω is the set of natural numbers, including zero.
[edit] See also
[edit] References
 Hopcroft, John; Ullman, Jeffrey (1979), Introduction to automata theory, languages, and computation, AddisonWesley, pp. 185–192.
 Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74, 358366, 1953.
 Rogers, Hartley (1967), Theory of recursive functions and effective computability, New York: McGrawHill.