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.

مواضيع ذات صلة

Lemma

Proof

Zeno,s Paradoxes

Unexpected Hanging Paradox

Strange Loop

Sorites Paradox

Simpson,s Paradox

Russell,s Antinomy

Paradox

Newcomb,s Paradox

Missing Dollar Paradox

Line Point Picking