The ibT degrees of computably enumerable sets are not dense (Q2498899)

From MaRDI portal
Revision as of 19:19, 24 June 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
The ibT degrees of computably enumerable sets are not dense
scientific article

    Statements

    The ibT degrees of computably enumerable sets are not dense (English)
    0 references
    16 August 2006
    0 references
    We say that \(A\) is identity bounded Turing (ibT) reducible to \(B\) if \(A\) is Turing reducible to \(B\) and the use of the computations is bounded by the identity function, i.e., on each argument \(n\) the \(B\)-queries are for numbers \(<n\). In this paper it is proved that the ibT degrees of computably enumerable sets are not dense.
    0 references
    0 references
    Turing reducibility
    0 references
    computably enumerable sets
    0 references
    density
    0 references
    0 references
    0 references
    0 references