Every non-trivial question about what a program computes is undecidable. Not just "does it halt" — any property of the computed function that some programs have and some lack has no decider. Trivial properties (held by all, or by none) are the only decidable ones. Rendered, not quoted.
source Rice, Classes of Recursively Enumerable Sets and Their Decision Problems (1953), Trans. Amer. Math. Soc. 74, 358–366 · doi:10.1090/S0002-9947-1953-0053041-6
A program is judged by the partial function it computes: for each input it either halts with an output or runs forever (⊥). A property P is a set of such functions.
Semantic: P depends only on the computed function, never on the syntax — two programs computing the same function get the same verdict. Non-trivial: some function is in P, some is out.
| property | kind | decidable? |
|---|---|---|
| held by ALL | trivial | yes (say "yes") |
| held by NONE | trivial | yes (say "no") |
| f(0)=0 | semantic, non-trivial | NO |
| computes 0 | semantic, non-trivial | NO |
Neighbour: the-halting-problem. Halting is the special case "does the computed function halt on this input." Rice generalizes it: reduce HALTING to any non-trivial semantic P, so P inherits its undecidability.
This is the hard ceiling on automated program analysis — no universal tool can decide "does this code compute X" for any interesting X.
Live re-check of the reduction invariant: over the finite family, the property-decider's verdict must track actual halting. If the TAMPER (6) plants a bogus decider, this flips red.
Simulates M on w to its exact halting step (or detects the loop), builds the reduction gadget, and computes P of the gadget's function — live, no baked numbers.
Proven result: booting…
"Just analyze the source and read off what it computes."
Behavior is a property of the function, not the text; the gadget hides M's fate inside code that looks fine.
"Only halting is undecidable; everything else is fine."
Any non-trivial semantic property is undecidable.
"Undecidable = no answer exists."
AMBER Each instance has a definite yes/no answer; no single algorithm gets them all right.
"Trivial properties are undecidable too."
No — all-or-none is decided by a constant; that is Rice's stated exception.
Plant a "decider" for the non-trivial semantic property that just answers yes to every program. Run it on the reduced halting instances — it contradicts the halting diagonal. The WITNESS (7) catches it.