Theory of Recursive Functions and Effective Computability¶
Rogers, H., & Jr. (1967). Theory of Recursive Functions and Effective Computability. McGraw-Hill.
Cited by¶
1 citation across 1 artifact.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Decidability Computability
- Lose any one and decidability fails, and the way it fails matters: a procedure that sometimes answers but sometimes loops forever is semi-decidable, a procedure that always terminates but only sometimes correctly is a heuristic, and a procedure that solves some instances but not the whole class is a special-case solver — three distinct failure modes the prime makes visible and keeps apart.
This sourceStandard reference distinguishing decidable, semi-decidable (recursively enumerable), and undecidable problem classes.
- Lose any one and decidability fails, and the way it fails matters: a procedure that sometimes answers but sometimes loops forever is semi-decidable, a procedure that always terminates but only sometimes correctly is a heuristic, and a procedure that solves some instances but not the whole class is a special-case solver — three distinct failure modes the prime makes visible and keeps apart.
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:be5ebc857df9 · see in the full table