Rice's Theorem and Undecidability
Rice's theorem shows that every non-trivial question about what a program computes is undecidable.
The sweeping result
Rice's theorem states that any non-trivial semantic property of a program's behavior is undecidable. Non-trivial means the property holds for some programs and not others; semantic means it concerns what the program computes, not how its text is written. Almost every interesting question about program behavior falls under this.
Examples of undecidable properties
- Does this program ever output 0
- Does this program compute the same function as that one
- Is this program free of infinite loops on all inputs
- Does this program ever access a particular resource
Why it follows from halting
Each such property can be reduced to the halting problem: if you could decide the property, you could construct a program whose having the property depends on whether some other program halts, deciding halting too. Since halting is undecidable, so is the property.
Syntactic properties escape
Rice's theorem targets semantic properties. Purely syntactic questions, such as "does the source contain more than 100 lines" or "does it use the multiply instruction," are decidable because they inspect the text, not the behavior. The undecidability begins the moment you ask what the program does.
Practical fallout
This is why compilers, verifiers, and security scanners cannot be both fully general and exact. They use sound approximations: they may report false alarms or miss cases, but they run in finite time. Type systems, for instance, reject some safe programs in exchange for guaranteeing decidable checking.
The larger landscape
Rice's theorem is one of a family of undecidability results, alongside the halting problem, the Post correspondence problem, and the undecidability of first-order logic validity. Together they map a hard boundary that no faster hardware can cross.