In computer science, Rice's theorem named after Henry Gordon Rice (also known as The Rice-Myhill-Shapiro theorem after Rice and John Myhill) is an important result in the theory of computable functions. It states that, for any non-trivial property of partial functions, the question of whether a given algorithm computes a partial function with this property is undecidable. Here, a property of partial functions is called trivial if it holds for all partial computable functions or for none. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... John R. Myhill is a mathematician. ... Computable functions (or Turing-computable functions) are the basic objects of study in computability theory. ... In mathematics, a partial function is a relation that associates each element of a set (sometimes called its domain) with at most one element of another (possibly the same) set, called the codomain. ... Flowcharts are often used to graphically represent algorithms. ... In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ...

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. For the branch of mathematical logic called computability theory, see Recursion theory. ... For the test of artificial intelligence, see Turing test. ... In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ... Fig. ...

It is important to note that Rice's theorem does not say anything about properties of machines, only of functions and languages. For example, asking whether a machine runs for more than 100 steps on some input, or whether it has more than 5 states, are nontrivial but decidable properties. They are not properties of the language because it is possible to find two machines recognizing exactly the same language, one which has the property and one which does not.

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 non-trivial questions on the black-box behavior of computer programs. This is one explanation of the difficulty of debugging. Hartley Rogers, Jr is a Professor of Mathematics at the Massachusetts Institute of Technology. ... A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ... Debugging is a methodical process of finding and reducing the number of bugs, or defects, in a computer program or a piece of electronic hardware thus making it behave as expected. ...

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 non-trivial, since there are partial functions that are defined for 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. In computability theory the halting problem is a decision problem which can be stated as follows: Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. ...

Formal statement

Let be a Gödel numbering of the computable functions. This article or section may be confusing or unclear for some readers, and should be edited to rectify this. ... Computable functions (or Turing-computable functions) are the basic objects of study in computability theory. ...

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 . In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ...

Rice's theorem states that the decision problem D_F is decidable if and only if or . In computability theory a countable set is called recursive, computable or decidable if we can construct an algorithm which terminates after a finite amount of time and decides whether or not a given element belongs to the set. ...

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.

Proof

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². 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.

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 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. In computer programming and formal language theory, (and other branches of mathematics), a string is an ordered sequence of symbols. ... Reductio ad absurdum (Latin: reduction to the absurd) also known as an apagogical argument, reductio ad impossibile, or proof by contradiction, is a type of logical argument where one assumes a claim for the sake of argument, derives an absurd or ridiculous outcome, and then concludes that the original assumption... In computability theory the halting problem is a decision problem which can be stated as follows: Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. ...

Let us now assume that P(a) is an algorithm that decides some non-trivial property of F_a. 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 will hold for the negation of the property. Since P decides a non-trivial 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_no-halt, i.e., the partial function that is never defined. Since P(no-halt) = "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 non-trivial property for the function represented by a must be false.

References

• Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74, 358-366, 1953.

See also

• Rice-Shapiro theorem
• Recursion theory

Recursion theory, or computability theory, is a branch of mathematical logic dealing with generalizations of the notion of computable function, and with related notions such as Turing degrees and effective descriptive set theory. ...

External links

• Eric W. Weisstein, Rice's theorem at MathWorld.