TOPICS
Search

Rice's Theorem

If A is a class of recursively enumerable sets, then the set of Gödel numbers of functions whose domains belong to A is called its index set. If the index set of A is a recursive set, then either A is empty or A 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.

See also

Decidable, Gödel Number, Recursively Enumerable Set, Undecidable

This entry contributed by Alex Sakharov (author's link)

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Rice's Theorem

Cite this as:

Sakharov, Alex. "Rice's Theorem." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/RicesTheorem.html

Subject classifications