MathLabs
TheoremProved

Rice's theorem

Statement

For every nontrivial semantic property PP of partial computable functions, the set {e:φe has property P}\{e : \varphi_e \text{ has property } P\} 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 ∅\emptyset (computed by a program that never halts on any input) does not have property PP — otherwise argue with the complement property ¬P\lnot P, which is decidable exactly when PP is. Since PP is nontrivial, fix some program e0e_0 whose function φe0\varphi_{e_0} does have property PP.

Suppose, for contradiction, that PP is decidable by some algorithm DD (given a program index, DD halts and correctly reports whether that program's function has property PP). We reduce the Halting Problem to PP, contradicting Theorem 1.

Given any pair (e,x)(e,x), effectively construct (by simple textual manipulation — Kleene's s-m-n theorem) a new program e′e' that, on any input yy: first simulates program ee running on input xx; if that simulation ever halts, then e′e' goes on to simulate program e0e_0 on input yy and outputs whatever it outputs.

Now examine the two possibilities. If ee halts on xx: the simulation of ee on xx finishes, so e′e' then behaves exactly like e0e_0 on every input, i.e. φe′=φe0\varphi_{e'}=\varphi_{e_0} — which has property PP (since PP is semantic, it only depends on the function computed, and φe0\varphi_{e_0} has PP). If ee does not halt on xx: the simulation of ee on xx never finishes, so e′e' never reaches the e0e_0-simulation step on any input yy; hence φe′\varphi_{e'} is the everywhere-undefined function ∅\emptyset, which by assumption does not have property PP.

So: ee halts on xx   ⟺  \iff φe′\varphi_{e'} has property PP   ⟺  \iff D(e′)D(e') answers "yes". Since (e,x)↦e′(e,x)\mapsto e' is computable, the algorithm "compute e′e' from (e,x)(e,x), then run D(e′)D(e')" would decide the Halting Problem — contradicting Theorem 1. So no such DD exists: PP is undecidable. ■\blacksquare

Topics that use this theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

  1. Wikipedia contributors (2024). Halting problem
  2. Wikipedia contributors (2024). Rice's theorem
  3. Wikipedia contributors (2024). Ackermann function