Rice's theorem
Teorema de Rice
- Date
- 1951-1953 · confidence medium
- Place
- Syracuse, New York, United States
- Credited to
- Henry Gordon Rice
- Field
- Knowledge & symbols
What was discovered
Computability theory theorem stating that every non-trivial semantic property of program behavior is undecidable, generalizing the undecidability of the halting problem.
What it led to
- Fundamental theoretical limits on static program analysis
- Theoretical justification for why certain code analyzers are impossible in general
- Conceptual basis for designing verifiers and conservative compilers
- Extension of computability theory initiated by Turing and Gödel