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 computable function, nor false for every computable function.

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.

Another way of stating Rice's theorem that is more useful in computability theory follows.

Let S be a set of languages that is nontrivial, meaning

1. there exists a Turing machine that recognizes a language in S

2. there exists a Turing machine that recognizes a language not in S

Then, it is undecidable to determine whether the language recognized by an arbitrary Turing machine lies in S.

Formal statement

Let be an admissible numbering of the computable functions; a map from the natural numbers to the class of unary (partial) computable functions. Denote by the eth (partial) computable function.

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.

• The class of indices for computable functions that are total

• The class of indices for recursively enumerable sets that are cofinite

• The class of indices for recursively enumerable sets that are recursive