Rice's theorem
All non-trivial semantic properties of programs are undecidable.
Last updated
Rice's theorem is a fundamental result in computability theory, named after Henry Gordon Rice, who proved it in his doctoral dissertation of 1951 at Syracuse University. The theorem states that all non-trivial semantic properties of programs are undecidable, meaning no algorithm can decide whether a given program exhibits a particular behavior unless that behavior is either true for all programs or false for all programs.
Quick Facts
- Theorem proved in
- 1951
Facts from the source article.
Background
Rice's theorem generalizes the undecidability of the halting problem. It asserts that it is impossible to decide a property of programs that depends only on the semantics (the program's behavior when run) and not on the syntax (how the program is written), unless the property is trivial—true of all programs or false of all programs. The theorem has far-reaching implications on the feasibility of static analysis of programs, implying that it is impossible to implement a tool that checks whether any given program is correct or even executes without error.
More in Set Theory & Logic
Sources
Compiled from Wikipedia and the sources listed below. Text from Wikipedia is available under CC BY-SA 4.0; this entry is adapted from it.
- Wikipedia: Rice's theorem (CC BY-SA 4.0).
Spotted an error? Know more?
Reader corrections go straight into our review queue. Suggest an edit · How this site is sourced