Rice's theorem
Statement
For every nontrivial semantic property of partial computable functions, the set is undecidable.
Why is it true?
This single theorem instantly rules out algorithms for "does this program compute the zero function", "does this program compute a total function", "are these two programs equivalent", and countless other natural questions about program behavior — all in one stroke, without a separate diagonal argument for each.
Proof sketch
WLOG assume the everywhere-undefined function (computed by a program that never halts on any input) does not have property — otherwise argue with the complement property , which is decidable exactly when is. Since is nontrivial, fix some program whose function does have property .
Suppose, for contradiction, that is decidable by some algorithm (given a program index, halts and correctly reports whether that program's function has property ). We reduce the Halting Problem to , contradicting Theorem 1.
Given any pair , effectively construct (by simple textual manipulation — Kleene's s-m-n theorem) a new program that, on any input : first simulates program running on input ; if that simulation ever halts, then goes on to simulate program on input and outputs whatever it outputs.
Now examine the two possibilities. If halts on : the simulation of on finishes, so then behaves exactly like on every input, i.e. — which has property (since is semantic, it only depends on the function computed, and has ). If does not halt on : the simulation of on never finishes, so never reaches the -simulation step on any input ; hence is the everywhere-undefined function , which by assumption does not have property .
So: halts on has property answers "yes". Since is computable, the algorithm "compute from , then run " would decide the Halting Problem — contradicting Theorem 1. So no such exists: is undecidable.
Topics that use this theorem
Step-by-step proofs
No step-by-step proof yet for this theorem.
References
- Wikipedia contributors (2024). Halting problem
- Wikipedia contributors (2024). Rice's theorem
- Wikipedia contributors (2024). Ackermann function