Rice's theorem

Lore & Background

Rice's theorem generalizes the undecidability of the halting problem. It asserts that it is impossible to decide a property of programs that depends only on the semantics (the program's behavior when run) and not on the syntax (how the program is written), unless the property is trivial—true of all programs or false of all programs. The theorem has far-reaching implications on the feasibility of static analysis of programs, implying that it is impossible to implement a tool that checks whether any given program is correct or even executes without error.

Reader's Guide

Rice's theorem establishes a theoretical bound on which types of static analysis can be performed automatically. It implies that one cannot algorithmically verify the absence of bugs in arbitrary programs, but this does not prevent certain types of bug prevention. For example, statically typed programming languages feature type systems that statically prevent type errors by inspecting source code syntax, not merely the hypothetical semantics. In software verification, one can require programs to be annotated with extra information (like type annotations) or written in restricted forms to make verification possible. Other workarounds include abstract interpretation, which catches many bugs without being complete, and model checking, which applies to finite-state programs but not Turing-complete languages. The theorem thus guides practical approaches to program analysis by clarifying what is theoretically impossible.

Did You Know?

• Rice's theorem is named after Henry Gordon Rice, who proved it in his doctoral dissertation of 1951 at Syracuse University.
• The theorem generalizes the undecidability of the halting problem.
• It implies that it is impossible to implement a tool that checks whether any given program is correct, or even executes without error.
• The theorem distinguishes between syntactic properties (e.g., 'does the program contain an if-then-else statement?') and semantic properties (e.g., 'does the program terminate for all inputs?').