СЕМЕЙСТВА ПЕРЕСТАНОВОК И ИДЕАЛЫ ТЬЮРИНГОВЫХ СТЕПЕНЕЙ (2022)

Изучаются семейства PI, состоящие из перестановок натурального ряда ω, степени которых принадлежат идеалу тьюринговых степеней I, и их скачки P′I. Для любого счётного тьюрингова идеала I приводятся описания спектров степеней семейств PI и их скачков P′I. Для некоторых идеалов I, порождённых в. п. степенями, определяются спектры семейств PI.

Тип: Статья
Автор (ы): МОРОЗОВ Андрей Сергеевич
Соавтор (ы): ПУЗАРЕНКО Вадим Григорьевич, ФАЙЗРАХМАНОВ Марат Хайдарович
Ключевые фразы: ВЫЧИСЛИМАЯ ПЕРЕСТАНОВКА, СЕМЕЙСТВО ПЕРЕСТАНОВОК, СКАЧОК, ТЬЮРИНГОВА СТЕПЕНЬ, ИДЕАЛ ТЬЮРИНГОВЫХ СТЕПЕНЕЙ, СПЕКТР СТЕПЕНЕЙ

Идентификаторы и классификаторы

УДК
510.5. Теория алгоритмов и вычислимые функции
Префикс DOI
10.33048/alglog.2022.61.603
eLIBRARY ID
54693357
Текстовый фрагмент статьи