Эта публикация цитируется в
4 статьях
О $p$-универсальных и $p$-минимальных нумерациях
М. Х. Файзрахманов Казанский (Приволжский) федеральный университет, Научно-образовательный математический центр Приволжского федерального округа, ул. Кремлевская, 35, Казань 420008
Аннотация:
Исследуется
$p$-сводимость нумераций, введенная и впервые изученная А. Н. Дегтевым и представляющая собой эффективно-ограниченный вариант
$e$-сводимости нумераций. Доказано, что для любого множества
$A$ существует
$A$-вычислимое семейство без универсальных нумераций, обладающее
$p$-универсальными нумерациями. Получен критерий существования
$p$-универсальных нумераций конечных семейств
$A$-в.п. множеств. Наконец, доказано, что любое
$A$-вычислимое семейство, где
$\emptyset''\leq _TA$, обладает бесконечным множеством попарно не
$p$-эквивалентных
$p$-минимальных
$A$-вычислимых нумераций.
Ключевые слова:
вычислимая нумерация,
$A$-вычислимая нумерация,
$p$-сводимость, универсальная нумерация,
$p$-универсальная нумерация,
$p$-минимальная нумерация.
УДК:
510.57 Статья поступила: 31.03.2021
Окончательный вариант: 31.03.2021
Принята к печати: 10.12.2021
DOI:
10.33048/smzh.2022.63.213