Theory of Recursive Functions and Effective Computability

Rogers Jr., H. (1967/1987). Theory of Recursive Functions and Effective Computability. MIT Press.

Type

Book

Intellectual base

Review or monograph

Year

1987 this edition · first published 1967

ISBN

9780262680523

Link

https://openlibrary.org/isbn/9780262680523 not authoritativeverified

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..
• Reduction (Computability Theory)
  • The subscript (r) identifies the access model: Turing reduction allows adaptive oracle queries; many-one reduction requires one computable instance transformation; truth-table and related reductions impose other constraints.
• 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

Does it exist? Confirmed. This work's ISBN 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 5 citations of this work carries a recorded support check.

Was it audited? Yes. A second, independent pass read the citation against the article text and recorded a verdict.

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