Downwards density in the n-computably enumerable Turing degrees and the uniform constructions
In 1993, R. Downey and M. Stob showed that the downwards density of computably enumerable (c.e.) Turing degrees in the partial 2-c.e. Turing degrees cannot be obtained from a uniform construction. We generalize this result for any n > 2 and show that there is no a uniform construction for the downwards density of ( n − 1) -c.e. degrees in the structure of n -c.e. degrees. Moreover, we show that there is no a uniform construction for the downwards density in the n -c.e. degrees.
Authors
- M. M. Yamaleev
Institutions
- Kazan Federal University (RU)
Publication Details
- Journal
- Mathematics and Theoretical Computer Science
- Published
- 2024-10-20
- DOI
- https://doi.org/10.26907/2949-3919.2024.3.76-91
- Primary Topic
- Computability, Logic, AI Algorithms
- Type
- article
- Field-Weighted Citation Impact
- 0.00