Rice's Theorem

If  is a class of recursively enumerable sets, then the set of Gödel numbers of functions whose domains belong to  is called its index set. If the index set of  is a recursive set, then either  is empty or  contains all recursively enumerable sets.

Rice's theorem is an important result for computer science because it sets up boundaries for research in that area. It basically states that only trivial properties of programs are algorithmically decidable.

REFERENCES

Davis, M. Computability and Unsolvability. New York: Dover, 1982.

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

Rogers, H. Theory of Recursive Functions and Effective Computability. Cambridge, MA: MIT Press, 1987.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 1137, 2002.