Критерии полноты Арсланова и линейная сводимость
https://doi.org/10.26907/2949-3919.2026.1.119-132
Аннотация
В 1977 году М.М. Арслановым был установлен критерий полноты вычислимо перечислимых множеств в терминах функций без неподвижных точек. Далее, в 1989–2022 годах им же критерий был обобщен на случай всех естественных алгоритмических сводимостей табличного типа, кроме линейной сводимости, для которой вопрос оставался открытым. В нашей работе дается ответ на этот вопрос и доказывается, что для линейной сводимости критерий полноты Арсланова в терминах функций без неподвижных точек не имеет места.
Ключевые слова
критерий полноты Арсланова,
функция без неподвижных точек,
вычислимо перечислимое множество,
линейная сводимость
При поддержке: Работа выполнена за счет предоставленного в 2026 году Фондом науки и технологий Республики Татарстан гранта на осуществление фундаментальных и прикладных научных работ в научных и образовательных организациях, предприятиях и организациях реального сектора экономики Республики Татарстан
Об авторах
Р. Р. Багавиев
Казанский (Приволжский) федеральный университет, Институт математики и механики им. Н.И. Лобачевского, Научно-образовательный математический центр ПФО
Россия
Россия
Рамиль Радифович Багавиев
Ул. Кремлевская, д. 18, Казань, 420008
М. М. Ямалеев
Казанский (Приволжский) федеральный университет, Институт математики и механики им. Н.И. Лобачевского, Научно-образовательный математический центр ПФО
Россия
Россия
Марс Мансурович Ямалеев
Ул. Кремлевская, д. 18, Казань, 420008
Список литературы
1. М.М. Арсланов, Р.Ф. Надыров, В.Д. Соловьёв, Критерий полноты рекурсивно перечислимых множеств и некоторые обобщения теоремы о неподвижной точке, Изв. вузов. Матем. (4), 3–7 (1977). URL: https://www.mathnet.ru/rus/ivm5940
2. C.G. Jockusch Jr., M. Lerman, R.I. Soare, R.M. Solovay, Recursively enumerable sets modulo iterated jumps and extensions of Arslanov’s completeness criterion, J. Symb. Log. 54 (4), 1288–1323 (1989). DOI: https://doi.org/10.2307/2274816
3. М.М. Арсланов, Полнота в арифметической иерархии и неподвижные точки, Алгебра и логика 28 (1), 3–17 (1989). URL: https://www.mathnet.ru/rus/al2042
4. M.M. Arslanov, Truth-table complete computably enumerable sets, in: Computability and models, Springer, Boston, MA, 1–10 (2003). DOI: https://doi.org/10.1007/978-1-4615-0755-0_1
5. М.М. Арсланов, Критерии полноты для одного класса сводимостей, Изв. вузов. Матем. (10), 73–78 (2022). DOI: https://doi.org/10.26907/0021-3446-2022-10-73-78
6. В.Д. Соловьёв, Некоторые обобщения понятий сводимости и креативности, Изв. вузов. Матем. (3), 65–72 (1976). URL: https://www.mathnet.ru/rus/ivm6135
7. В.К. Булитко, Сводимости линейными по Жигалкину таблицами, Сиб. матем. журн. 21 (3), 23–31 (1980). URL: https://www.mathnet.ru/rus/smj3723
8. В.Л. Селиванов, Об одном классе сводимостей в теории рекурсивных функций, в: Вероятностные методы и кибернетика. Т. 18, Изд-во КГУ, Казань, 83–100 (1982).
9. А.Н. Дёгтев, Рекурсивно перечислимые множества и сводимости табличного типа, Наука, М., 1998.
10. Р.И. Соар, Вычислимо перечислимые множества и степени, Казан. матем. о-во, Казань, 2000.
Рецензия
Для цитирования:
Багавиев Р.Р., Ямалеев М.М. Критерии полноты Арсланова и линейная сводимость. Математика и теоретические компьютерные науки. 2026;4(1):119-132. https://doi.org/10.26907/2949-3919.2026.1.119-132
For citation:
Bagaviev R.R., Yamaleev M.M. Arslanovs’ completeness criteria and linear reducibility. Mathematics and Theoretical Computer Science. 2026;4(1):119-132. (In Russ.) https://doi.org/10.26907/2949-3919.2026.1.119-132
Просмотров:
54
JATS XML
Послать статью по эл. почте 