The ibT degrees of computably enumerable sets are not dense (Q2498899): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: George Barmpalias / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Andrew E. M. Lewis / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Roland Sh. Omanadze / rank | |||
Normal rank |
Revision as of 18:41, 10 February 2024
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
Turing reducibility
0 references
computably enumerable sets
0 references
density
0 references