Rice’s Theorem

← Back to Undecidable Problems

Any non-trivial semantic property of programs is undecidable. A “semantic property” is about the function a program computes (not its syntax). This means no algorithm can decide properties like “does this program produce correct output?” for all programs. A sweeping generalization of the halting problem.

computational-complexity complexity-classes undecidable rices-theorem