Rice's theorem
E588867
Rice's theorem is a fundamental result in computability theory stating that any non-trivial semantic property of the language recognized by a Turing machine is undecidable.
All labels observed (1)
| Label | Occurrences |
|---|---|
| Rice's theorem canonical | 2 |
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf | theorem in computability theory ⓘ |
| appliesTo |
Turing machines
NERFINISHED
ⓘ
indices of partial computable functions in acceptable numberings ⓘ partial recursive functions ⓘ recursively enumerable sets ⓘ |
| assumes |
effective enumeration of partial computable functions
ⓘ
standard model of Turing computability ⓘ |
| characterizes | undecidability of non-trivial semantic properties of computable functions ⓘ |
| concerns |
languages recognized by Turing machines
ⓘ
semantic properties of partial computable functions ⓘ undecidability ⓘ |
| countryOfOrigin |
United States of America
ⓘ
surface form:
United States
|
| defines | non-trivial property as one that holds for at least one and not all computable functions ⓘ |
| excludes | trivial properties that hold for all or no computable functions ⓘ |
| field |
computability theory
ⓘ
mathematical logic ⓘ theoretical computer science ⓘ |
| hasConsequence |
many questions about program behavior are algorithmically unsolvable
ⓘ
no algorithm can decide any non-trivial semantic property of Turing-recognizable languages ⓘ |
| implies |
undecidability of many program analysis problems
ⓘ
undecidability of non-trivial properties of program output sets ⓘ undecidability of program equivalence ⓘ |
| importance | fundamental result in computability theory ⓘ |
| involvesConcept |
decidable set
ⓘ
many-one reduction ⓘ recursively enumerable sets of indices ⓘ semantic property ⓘ trivial property ⓘ |
| mainStatement | Every non-trivial semantic property of the language recognized by a Turing machine is undecidable ⓘ |
| namedAfter | Henry Gordon Rice NERFINISHED ⓘ |
| proofTechnique |
diagonalization
ⓘ
reduction from the halting problem ⓘ |
| relatedTo |
Church–Turing thesis
NERFINISHED
ⓘ
Halting problem NERFINISHED ⓘ Post's theorem NERFINISHED ⓘ Recursion theorem NERFINISHED ⓘ Rice–Shapiro theorem NERFINISHED ⓘ |
| scope | semantic properties rather than syntactic properties ⓘ |
| status | proven ⓘ |
| taughtIn |
graduate logic and recursion theory courses
ⓘ
undergraduate computability courses ⓘ |
| typeOf |
meta-theorem about computable functions
ⓘ
undecidability theorem NERFINISHED ⓘ |
| typicalFormulation | For any non-trivial property of partial computable functions, the set of indices of functions with that property is undecidable ⓘ |
| usedIn |
computability theory textbooks
ⓘ
program verification theory ⓘ proofs of undecidability in programming language theory ⓘ static analysis impossibility results ⓘ |
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.