matatecsМатематика и теоретические компьютерные наукиMathematics and Theoretical Computer Science2949-3919Казанский (Приволжский) федеральный университет10.26907/2949-3919.2026.1.119-132matatecs-107Research ArticleСТАТЬИКритерии полноты Арсланова и линейная сводимостьArslanovs’ completeness criteria and linear reducibilityБагавиевР. Р.BagavievR. R.

Рамиль Радифович Багавиев

Ул. Кремлевская, д. 18, Казань, 420008

Ramil Radifovich Bagaviev

18 Kremlyovskaya str., Kazan 420008

ramilbagaviev@mail.ruЯмалеевМ. М.YamaleevM. M.

Марс Мансурович Ямалеев

Ул. Кремлевская, д. 18, Казань, 420008

Mars Mansurovich Yamaleev

18 Kremlyovskaya str., Kazan 420008

mars.yamaleev@kpfu.ruКазанский (Приволжский) федеральный университет, Институт математики и механики им. Н.И. Лобачевского, Научно-образовательный математический центр ПФОРоссияKazan Federal University, N.I. Lobachevsky Institute of Mathematics and Mechanics, Volga Region Mathematical CenterRussian Federation20262206202641119132Copyright © Багавиев Р.Р., Ямалеев М.М., 20262026Багавиев Р.Р., Ямалеев М.М.Bagaviev R.R., Yamaleev M.M.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://matatecs.elpub.ru/jour/article/view/107

В 1977 году М.М. Арслановым был установлен критерий полноты вычислимо перечислимых множеств в терминах функций без неподвижных точек. Далее, в 1989–2022 годах им же критерий был обобщен на случай всех естественных алгоритмических сводимостей табличного типа, кроме линейной сводимости, для которой вопрос оставался открытым. В нашей работе дается ответ на этот вопрос и доказывается, что для линейной сводимости критерий полноты Арсланова в терминах функций без неподвижных точек не имеет места.

In 1977, M.M. Arslanov established a completeness criterion for computably enumerable sets in terms of fixed-point-free functions. Later, in 1989–2022, he generalized the criterion to all natural algorithmic table-type reducibilities, except for linear reducibility, where the question remained open. In our work, we answer this question and prove that Arslanov’s completeness criterion for linear reducibility in terms of fixed-point-free functions does not hold.

критерий полноты Арслановафункция без неподвижных точеквычислимо перечислимое множестволинейная сводимостьArslanov’s completeness criterionfixed-point-free functioncomputably enumerable setlinear reducibilityРабота выполнена за счет предоставленного в 2026 году Фондом науки и технологий Республики Татарстан гранта на осуществление фундаментальных и прикладных научных работ в научных и образовательных организациях, предприятиях и организациях реального сектора экономики Республики ТатарстанThe work was performed under a grant provided in 2026 by the Science and Technology Fund of the Republic of Tatarstan for the implementation of fundamental and applied scientific work in scientific and educational organizations, enterprises and organizations of the real sector of the economy of the Republic of TatarstanReferencesМ.М. Арсланов, Р.Ф. Надыров, В.Д. Соловьёв, Критерий полноты рекурсивно перечислимых множеств и некоторые обобщения теоремы о неподвижной точке, Изв. вузов. Матем. (4), 3–7 (1977). URL: https://www.mathnet.ru/rus/ivm5940M.M. Arslanov, R.F. Nadyrov, V.D. Solov’ev, A criterion for the completeness of recursively enumerable sets, and some generalizations of a fixed point theorem, Izv. vuzov. Matem. (4), 3–7 (1977) [in Russian]. URL: https://www.mathnet.ru/eng/ivm5940C.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/2274816C.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М.М. Арсланов, Полнота в арифметической иерархии и неподвижные точки, Алгебра и логика 28 (1), 3–17 (1989). URL: https://www.mathnet.ru/rus/al2042M.M. Arslanov, Completeness in the arithmetical hierarchy and fixed points, Algebra Logic 28 (1), 1–9 (1989). DOI: https://doi.org/10.1007/BF01980603M.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_1M.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М.М. Арсланов, Критерии полноты для одного класса сводимостей, Изв. вузов. Матем. (10), 73–78 (2022). DOI: https://doi.org/10.26907/0021-3446-2022-10-73-78M.M. Arslanov, Completeness criteria for a class of reducibilities, Russian Math. (Iz. VUZ) 66 (10), 62–66 (2022). DOI: https://doi.org/10.3103/S1066369X22100012В.Д. Соловьёв, Некоторые обобщения понятий сводимости и креативности, Изв. вузов. Матем. (3), 65–72 (1976). URL: https://www.mathnet.ru/rus/ivm6135V.D. Solov’ev, Some generalizations of the notions of reducibility and creativity, Izv. vuzov. Matem. (3), 65–72 (1976) [in Russian]. URL: https://www.mathnet.ru/eng/ivm6135В.К. Булитко, Сводимости линейными по Жигалкину таблицами, Сиб. матем. журн. 21 (3), 23–31 (1980). URL: https://www.mathnet.ru/rus/smj3723V.K. Bulitko, Reducibility by Zhegalkin-linear tables, Sib. Math. J. 21 (3), 332–339 (1980). DOI: https://doi.org/10.1007/BF00968176В.Л. Селиванов, Об одном классе сводимостей в теории рекурсивных функций, в: Вероятностные методы и кибернетика. Т. 18, Изд-во КГУ, Казань, 83–100 (1982).V.L. Selivanov, On a class of reducibility in a recursive function theory, in: Probabilistic methods and cybernetics. V. 18, Izd-vo KGU, Kazan, 83–100 (1982) [in Russian].А.Н. Дёгтев, Рекурсивно перечислимые множества и сводимости табличного типа, Наука, М., 1998.A.N. Degtev, Recursive enumerable sets and reducibilities of tabular type, Nauka, M., 1998 [in Russian].Р.И. Соар, Вычислимо перечислимые множества и степени, Казан. матем. о-во, Казань, 2000.R.I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspectives in mathematical logic. Springer-Verlag, Berlin, Heidelberg, New York, etc., 1987. URL: https://link.springer.com/book/9783540666813

The authors declare that there are no conflicts of interest present.