Theory of Recursive Functions and Effective Computability

Hartley Rogers Jr., T. o. R. F., & Effective Computability, M. P. (1987). Theory of Recursive Functions and Effective Computability. MIT Press.

Type

Book chapter

Intellectual base

Review or monograph

Year

1987

ISBN

9780262680523

Link

https://openlibrary.org/books/OL2738948Mmatched

Cited by

5 citations across 5 artifacts.

Domain-specific

• Cylindrification
  • Rogers supplies the classical framework of indices, acceptable systems, reducibilities, and computable pairing in which this maneuver is interpreted.
• Dovetailing (computer science)
  • … directly demonstrates that each spawned computation receives unbounded cumulative steps under a stated fair schedule and outputs are merged without requiring failed branches to terminate. to An applied instance preserves the same invariant under a changed notation, scale, implementation, or empirical setting..
• Numbering (Computability Theory)
  • The map need not be injective: multiple programs or descriptions can denote the same object, and that intensional redundancy is central to index-set and equivalence questions.
• S-m-n Theorem
  • Standard computability texts use it alongside universal programs to characterize acceptable programming systems.
• Truth-table reduction
  • Complexity-bounded nonadaptive reductions require resource bounds and belong to a separately qualified setting.

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:5710c9645518 · see in the full table