The ibT degrees of computably enumerable sets are not dense (Q2498899)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5047218
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The ibT degrees of computably enumerable sets are not dense |
scientific article; zbMATH DE number 5047218 |
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
0.7995004653930664
0 references
0.7916538119316101
0 references
0.7883632183074951
0 references
0.7770302891731262
0 references
0.767838716506958
0 references
