Rice's Theorem
Jump to navigation
Jump to search
Every nontrivial, functional property about programs is undecidable.
- Functional property
- a property that refers to the language accepted by the program and not the specific code of the program.
- EX: Program terminates in 10 steps: (not functional); the program accepts 0 or more inputs (functional).
- Nontrivial property
- functional property about programs if some programs have the property and some do not.
- Decidability
- In reference to a decision problem, the question of the existence of an algorithm that can and will return a Boolean true or false value (instead of looping indefinitely)