RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 2022, том 61, номер 6, страницы 706–719 (Mi al2738)

Семейства перестановок и идеалы тьюринговых степеней

А. С. Морозов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}$.

Ключевые слова: вычислимая перестановка, семейство перестановок, скачок, тьюрингова степень, идеал тьюринговых степеней, спектр степеней.

УДК: 510.5

Поступило: 19.04.2022
Окончательный вариант: 13.10.2023

DOI: 10.33048/alglog.2022.61.603



© МИАН, 2024