Arslanovs’ completeness criteria and linear reducibility
https://doi.org/10.26907/2949-3919.2026.1.119-132
Abstract
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.
Supporting agencies: 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 Tatarstan
About the Authors
R. R. Bagaviev
Kazan Federal University, N.I. Lobachevsky Institute of Mathematics and Mechanics, Volga Region Mathematical Center
Russian Federation
Russian Federation
Ramil Radifovich Bagaviev
18 Kremlyovskaya str., Kazan 420008
M. M. Yamaleev
Kazan Federal University, N.I. Lobachevsky Institute of Mathematics and Mechanics, Volga Region Mathematical Center
Russian Federation
Russian Federation
Mars Mansurovich Yamaleev
18 Kremlyovskaya str., Kazan 420008
References
1. M.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/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. M.M. Arslanov, Completeness in the arithmetical hierarchy and fixed points, Algebra Logic 28 (1), 1–9 (1989). DOI: https://doi.org/10.1007/BF01980603
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. M.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
6. V.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
7. V.K. Bulitko, Reducibility by Zhegalkin-linear tables, Sib. Math. J. 21 (3), 332–339 (1980). DOI: https://doi.org/10.1007/BF00968176
8. 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].
9. A.N. Degtev, Recursive enumerable sets and reducibilities of tabular type, Nauka, M., 1998 [in Russian].
10. 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
Review
For citations:
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
Views:
56
JATS XML
Email this article 