Rice's theorem states that all non-trivial semantic properties of programs are undecidable. It is named after Henry Gordon Rice, who proved it in 1951. The theorem also states that no general and effective method can decide whether an algorithm computes a partial function with a non-trivial property.
Carnegie Mellon University
Spring 2015
A foundational course that introduces formal languages, automata, computability, and complexity theories, including finite automata, Turing machines, and P/NP classes.
No concepts data
+ 35 more concepts