Classes of Recursively Enumerable Sets and Their Decision Problems¶
Rice, H. G. (1953). Classes of Recursively Enumerable Sets and Their Decision Problems. Transactions of the American Mathematical Society, 74(2), 358-366.
Cited by¶
6 citations across 6 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Axiomatic Incompatibility
- In computability, Rice's theorem makes any non-trivial semantic property of programs undecidable.
This sourceProves that every non-trivial semantic property of programs is undecidable.
- In computability, Rice's theorem makes any non-trivial semantic property of programs undecidable.
- Computability
- Diagonal Impossibility
- In computability, the halting problem assumes a halting decider and builds a program that consults the decider on itself and does the opposite, and Rice's theorem extends the result to all non-trivial semantic properties via a diagonal-style flip.
This sourceEvery non-trivial semantic property of programs is undecidable, extending the diagonal result.
- In computability, the halting problem assumes a halting decider and builds a program that consults the decider on itself and does the opposite, and Rice's theorem extends the result to all non-trivial semantic properties via a diagonal-style flip.
Mechanisms¶
- Constraint and Invariant Checker
- Decision-Procedure Specification
- Rice's theorem
This sourceRice's theorem; any non-trivial semantic property of arbitrary program behavior has no total decision procedure; spec that quietly promises one is writing a check it cannot cash
- Rice's theorem
- Halting-Problem Reduction
- The result is about the unrestricted class; it says nothing about decidable subclasses, promises, or approximations, yet teams routinely hear "undecidable" as "nothing here is computable" and abandon tractable restrictions a Decidable Subclass Map would have found.
This sourceProves undecidability for every nontrivial class of recursively enumerable sets in the theorem’s unrestricted domain.
- The result is about the unrestricted class; it says nothing about decidable subclasses, promises, or approximations, yet teams routinely hear "undecidable" as "nothing here is computable" and abandon tractable restrictions a Decidable Subclass Map would have found.
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Not recorded. Neither this nor any other of the 6 citations of this work carries a recorded support check.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:8ef8ba90677e · see in the full table