|
Семейства перестановок и идеалы тьюринговых степеней
А. С. Морозовa, В. Г. Пузаренкоa, М. Х. Файзрахмановb a Ин-т матем. им. С. Л. Соболева СО РАН, Новосибирский гос. ун-т, г. Новосибирск, РОССИЯ
b Казанский (Приволжский) федерал. ун-т, Науч.-обр. матем. центр ПФО, г. Казань, РОССИЯ
Аннотация:
Изучаются семейства ${\mathcal P}_{\mathrm I}$, состоящие из перестановок натурального ряда $\omega$, степени которых принадлежат идеалу тьюринговых степеней $\mathrm I$, и их скачки ${\mathcal P}'_{\mathrm I}$. Для любого счётного тьюрингова идеала $\mathrm I$ приводятся описания спектров степеней семейств ${\mathcal P}_{\mathrm I}$ и их скачков ${\mathcal P}'_{\mathrm I}$. Для некоторых идеалов $\mathrm I$, порождённых в. п. степенями, определяются спектры семейств ${\mathcal P}_{\mathrm I}$.
Ключевые слова:
вычислимая перестановка, семейство перестановок, скачок, тьюрингова степень, идеал тьюринговых степеней, спектр степеней.
Поступило: 19.04.2022 Окончательный вариант: 13.10.2023
Образец цитирования:
А. С. Морозов, В. Г. Пузаренко, М. Х. Файзрахманов, “Семейства перестановок и идеалы тьюринговых степеней”, Алгебра и логика, 61:6 (2022), 706–719
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al2738 https://www.mathnet.ru/rus/al/v61/i6/p706
|
Статистика просмотров: |
Страница аннотации: | 81 | PDF полного текста: | 25 | Список литературы: | 16 |
|