Rice's Theorem Introduction
You'll learn: Why any interesting question about what a program does is fundamentally undecidable.
The Ultimate Limit on Program Analysis
You've just seen that the Halting Problem is undecidable—we can't build a universal decider that tells whether an arbitrary program halts. Rice's Theorem takes this limitation much further: it proves that any non-trivial property of program behavior is undecidable.
What Does "Non-Trivial Property" Mean?
A property of program behavior is:
- Trivial if it's true for all programs or no programs
- Non-trivial if it's true for some programs but not others
Examples of non-trivial properties:
- "Does this program compute a prime number?"
- "Does this program output 'Hello'?"
- "Does this program sort its input?"
- "Does this program run in polynomial time?"
The Theorem's Power
Rice's Theorem says: If you're asking about what a program computes (its behavior, not its source code), and the answer varies between different programs, then the question is undecidable.
Think of it this way: You can easily check if source code contains the word "Hello" (that's syntax). But you cannot decide if a program will ever output "Hello" during execution (that's semantics/behavior).
Why This Matters
This means automated program verification has fundamental limits. No tool can answer questions like "Does my code have security vulnerabilities?" or "Will this loop always terminate?" for all possible programs.
Key Takeaway: Rice's Theorem proves that any interesting question about what programs do (as opposed to what they look like) is undecidable—making it one of the most sweeping impossibility results in computer science.