Recursively Enumerable Sets and Degrees

Soare, R. I. (1987). Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer.

Type

Book

Intellectual base

Review or monograph

Year

1987

DOI

10.1007/978-3-662-02460-7

ISBN

9783540666813

DOI registrant

Springer Nature

Link

https://doi.org/10.1007/978-3-662-02460-7

Cited by

3 citations across 3 artifacts.

Domain-specific

• Creative and Productive Sets
  • A set C is creative when C is computably enumerable and its complement is productive.
• Reduction (Computability Theory)
  • It is not automatically polynomial-time: classical computability reductions constrain effectiveness and oracle access, not necessarily time or space.
• Truth-table reduction
  • … with a fixed negation convention if allowed by the chosen formulation. to A total Turing functional on Cantor space gives a truth-table reduction because compactness of \(2^\omega\) yields, for each input, a finite uniform amount of oracle information sufficient to determine the output. demonstrates that continuity.

Verification

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

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:0d5c199bb379 · see in the full table