1953 United States undecidable

Rice's Theorem

Henry Gordon Rice, 1953 — every non-trivial question about a program's behavior is undecidable. Refactoring without breaking is, in the limit, impossible.

Henry Gordon Rice, in his Syracuse PhD thesis, proved a sweeping generalization of the Halting Problem. A semantic property of a program is any property of its behavior — does it terminate, does it produce a given output, does it satisfy a given specification, does it behave like this other program. Rice proved that every non-trivial semantic property is undecidable. "Non-trivial" means there exists at least one program with the property and at least one without. The proof reduces the question to halting. The implication for software maintenance is direct and devastating: the question "does this refactored version behave the same as the original" is a non-trivial semantic property, and is therefore undecidable in the general case. No tool, no compiler, no AI system can answer it for arbitrary programs.

In plain terms

Turing's halting problem is one specific question — does this program stop. Rice asked: what about other questions? Does this program ever output the number seven. Does this program loop forever on at least one input. Does this version behave the same as that version. Are these two functions equivalent. Rice proved all of those questions are undecidable. Every single one. As long as the question is about behavior rather than syntax, and as long as the answer is sometimes yes and sometimes no, you cannot build a tool that always answers correctly. This is the theorem that decides whether automated maintenance is possible. It is not. Not in the general case. Asking "does this change preserve behavior" is exactly the kind of non-trivial semantic question Rice ruled out. When a static analyzer claims to detect bugs, it is using approximations and giving up completeness — it will miss bugs, or flag false ones, or both. Rice's theorem is why. When a compiler refuses to optimize a piece of code, it is because deciding whether the optimization preserves behavior is, in general, this same undecidable question. When an AI tool refactors your code and the tests pass, the tests passing means the tested behaviors are preserved. Rice's theorem tells you nothing else can be promised. This is the second floor. Above the halting problem, below NP. The room where every interesting question about software lives, and where no tool can ever answer them all. Every meaningful question about behavior, undecidable. Maintenance, undecidable in the limit.