Плотность вниз в n-вычислимо перечислимых тьюринговых степенях и равномерные конструкции
https://doi.org/10.26907/2949-3919.2024.3.76-91
Аннотация
В 1993 Р. Доуни и М. Стоб показали, что плотность вниз вычислимо перечислимых (далее, в. п.) тьюринговых степеней в частичном порядке 2-в. п. тьюринговых степеней не может быть доказана при помощи равномерной конструкции. Мы обобщаем этот результат на случай произвольного натурального n > 2 и доказываем, что не существует равномерной конструкции для плотности вниз (n − 1)-в. п. степеней в структуре n-в. п. степеней. Более того, нами показано, что не существует равномерной конструкции для плотности вниз в структуре n-в. п. степеней.
Об авторе
М. М. Ямалеев
Казанский (Приволжский) федеральный университет, Институт математики и механики им. Н.И. Лобачевского, Научно-образовательный математический центр ПФО
Россия
Марс Мансурович Ямалеев
Россия
Марс Мансурович Ямалеев
ул. Кремлевская, д. 18, г. Казань, 420008
Список литературы
1. А.И. Талипова, М.М. Ямалеев, Неравномерность плотности вниз в n-вычислимо перечислимых тьюринговых степенях, Изв. вузов. Матем. (11), 124–131 (2022). DOI: https://doi.org/10.26907/0021-3446-2022-11-124-131
2. Р.И. Соар, Вычислимо перечислимые множества и степени, Казан. матем. о-во, Казань, 2000.
3. R. Downey, M. Stob, Splitting theorems in recursion theory, Ann. Pure Appl. Log. 65 (1), 1–106 (1993). DOI: https://doi.org/10.1016/0168-0072(93)90234-5
4. S.B. Cooper, A.S. Li, Non-uniformity and generalised Sacks splitting, Acta Math. Sinica 18 (2), 327–334 (2002). DOI: https://doi.org/10.1007/s101140100150
5. M.M. Arslanov, I.Sh. Kalimullin, S. Lempp, On Downey’s conjecture, J. Symb. Log. 75 (2), 401–441 (2010). DOI: https://doi.org/10.2178/jsl/1268917488
Рецензия
Для цитирования:
Ямалеев М.М. Плотность вниз в n-вычислимо перечислимых тьюринговых степенях и равномерные конструкции. Математика и теоретические компьютерные науки. 2024;2(3):76-91. https://doi.org/10.26907/2949-3919.2024.3.76-91
For citation:
Yamaleev M.M. Downwards density in the n-computably enumerable Turing degrees and the uniform constructions. Mathematics and Theoretical Computer Science. 2024;2(3):76-91. (In Russ.) https://doi.org/10.26907/2949-3919.2024.3.76-91
Просмотров:
82
Послать статью по эл. почте 