A software company wants to build a tool that, given any program P, definitively answers 'yes' or 'no': 'Will this program ever throw a NullPointerException on any input?' According to Rice's theorem, is this possible?
AYes — null pointer exceptions are a well-defined runtime behavior that any modern compiler can detect statically.
BNo — whether a program throws a null pointer exception is a semantic property, and since it is non-trivial, Rice's theorem guarantees it is undecidable.
CYes, but only for programs under a certain size — above that size, the problem becomes undecidable.
DNo — but only because null pointer exceptions depend on runtime input, which is inherently unpredictable.
Whether a program throws a null pointer exception is a semantic property: it depends on the behavior the program exhibits, not its syntactic description. It is non-trivial: some programs throw null pointer exceptions, some don't. Rice's theorem therefore guarantees no algorithm can decide it in general. This is why static analysis tools cannot eliminate all null pointer exceptions — they use syntactic approximations that are necessarily incomplete (they miss some cases) or unsound (they report false positives). The impossibility is mathematical, not an engineering failure.
Question 2 Multiple Choice
Which of the following questions about a program is decidable?
ADoes this program halt on all inputs?
BDoes this program output a prime number on input 17?
CDoes this program have exactly 47 states in its Turing machine description?
DDo this program and a reference program compute the same function?
Only option C is syntactic: 'having exactly 47 states' is a property of the program's description, not of what it computes. You can count the states directly from the encoding — no simulation required. Options A, B, and D are all semantic (they concern what the program computes or whether it halts), and by Rice's theorem, all are undecidable for non-trivial definitions. The semantic/syntactic distinction is the key: if you can determine it by reading the description, it's syntactic (possibly decidable); if you need to observe program behavior, it's semantic (undecidable if non-trivial).
Question 3 True / False
Rice's theorem implies that no algorithm can decide whether two arbitrary programs compute the same function.
TTrue
FFalse
Answer: True
'Computing the same function as program X' is a semantic property — it depends on the function computed, not the syntactic description. It is non-trivial: some programs compute the same function as X, others don't. Rice's theorem therefore guarantees this property is undecidable. This has major practical implications: program equivalence checking (crucial for compiler optimization, refactoring verification, and software testing) cannot be done exactly in general, only approximated.
Question 4 True / False
Rice's theorem proves that most properties of programs — including syntactic properties like code length or number of variables — are undecidable.
TTrue
FFalse
Answer: False
Rice's theorem applies only to semantic properties — properties about what a program computes, not about how it is written. Syntactic properties like 'this program has 10 states,' 'this code file is 500 lines,' or 'this function has 3 parameters' are decidable because they can be determined by reading the description without simulating the program. The theorem's scope is strictly limited to semantic (behavioral) properties. Static analysis tools exploit this by replacing undecidable semantic questions with decidable syntactic overapproximations.
Question 5 Short Answer
Why must every practical static analysis tool (type checkers, linters, bug finders) be either incomplete or unsound, according to Rice's theorem?
Think about your answer, then reveal below.
Model answer: The property any such tool tries to verify (e.g., 'this program has no null pointer exceptions') is a semantic property of program behavior. Rice's theorem proves such properties are undecidable — no algorithm can correctly answer yes/no for all programs. A tool that never produces false positives (sound) must sometimes fail to detect real bugs (incomplete). A tool that never misses bugs (complete) must sometimes report false positives (unsound). There is no escape: perfect static analysis is mathematically impossible.
Tools like TypeScript's type checker and Java's NullAway work by approximating semantic properties with syntactic ones: 'this variable could be null' (syntactic, over-approximate) in place of 'this program throws NullPointerException' (semantic, undecidable). The approximation is why these tools have false positive rates — they are mathematically required to, not due to engineering failure. Rice's theorem explains why program verification is hard in principle, and why all practical tools must choose their tradeoff between soundness and completeness.