A theorem in computability theory asserting that every nontrivial semantic property of the language recognized by a Turing machine is undecidable: no algorithm can decide, for an arbitrary Turing machine, whether the language it accepts has that property, provided the property depends only on the language and is nontrivial.

Principle

Semantic properties of recognized languages (properties depending only on the set of accepted strings) are either trivial (true for all machines or none) or undecidable; there is no general decision procedure for nontrivial language-level properties.

Demonstration

Concrete domain example: the property 'the language recognized by the machine is regular' is a nontrivial semantic property and, by Rice's theorem, undecidable: one cannot write an algorithm that, given any Turing machine, correctly decides whether its accepted language is regular.

Misapplication

Applying Rice's theorem to syntactic or resource properties (e.g., 'does the machine have fewer than 10 states' or 'does the machine run in linear time'), which are not purely semantic language properties and may be decidable; or concluding Rice's theorem implies all program analysis is impossible in practice.

Consequence

Explains why many nontrivial program properties (termination for all inputs, equivalence to a specification, nontrivial correctness properties) are undecidable in general, shaping expectations for static analysis and motivating approximate, conservative, or domain-limited techniques.

Reversal

The converse case is that syntactic properties or trivial semantic properties are decidable; restricting the set of machines or languages (e.g., finite automata) can restore decidability.

Boundary

Applies only to semantic properties of Turing-recognizable languages that are nontrivial and extensional (depend only on the language); it does not apply to syntactic features, resource bounds, probabilistic guarantees, or properties defined relative to a restricted class of machines.

Semantic Tension

Tension between semantic undecidability (what languages are) and practical program analysis which focuses on syntactic patterns, heuristics, restricted domains, or conservative approximations that avoid the undecidable general case.

Synthesis

Rice's theorem formalizes a broad limitation: any nontrivial question that asks only about the set of strings a Turing machine accepts is undecidable, which forces program analysis to rely on approximations, restrictions, or non-extensional information.