|Generate QR code
Open Access
Subscription Access
On infinite direct sums of minimal numberings of functional families
https://doi.org/10.26907/0021-3446-2025-4-38-52
Abstract
The paper discusses two approaches to defining the computability of numberings of families of total functions. We consider both the classical definition of computable numbering of a family of computable functions, according to which the number of a function in this numbering effectively provides its G\"odel number, and, expanding the previous one, a definition based on the uniform application of the concept of the left-c.e. element of Baire space. The main question studied in the paper is the possibility of generating all computable numberings of a family by the closure with respect to the reducibility of infinite direct sums of uniform sequences of its single-valued, positive, and minimal numberings.
About the Authors
Sh. D. Nodirov
Republic of Uzbekistan
Uzbekistan
Uzbekistan
Shohruh Dilmurodovich Nodirov
17 Kuchabog str., Karshi, 180100
M. Kh. Faizrahmanov
Kazan Federal University Russia
Uzbekistan
Uzbekistan
Marat Khaidarovich Faizrahmanov
18 Kremlyovskaya str., Kazan, 420008
Z. K. Shchedrikova
Innopolis University
Russian Federation
Russian Federation
Zlata Konstantinovna Shchedrikova
1 Universitetskaya str., Innopolis, 420500
References
1. Friedberg R. Three theorems on recursive enumeration, J. Symb. Log. 23 (3), 309–316 (1958).
2. Schinzel B. On decomposition of Go¨delnumberings into Friedbergnumberings, J. Symb. Log. 47 (2), 267–274 (1982).
3. Ершов Ю.Л. Нумерации семейств общерекурсивных функций, Сиб. матем. журн. 8 (5), 1015–1025 (1967).
4. Марченков С.С. О вычислимых нумерациях семейств общерекурсивных функций, Алгебра и логика 11 (5), 588–607 (1972).
5. Downey R.G., Hirschfeldt D.R. Algorithmic Randomness and Complexity, Theory Appl. Comput. (Springer, New York, 2010).
6. Kjos-Hanssen B., Stephan F., Teutsch J. Arithmetic complexity via effective names for random sequences, ACM Trans. Comput. Log. 13 (3), 1–18 (2012).
7. Stephan F., Teutsch J. Things that can be made into themselves, Information and Computation 237, 174–186 (2014).
8. Soare R.I. Recursively enumerable sets and degrees. A study of computable functions and computably generated sets (Perspect. Math. Log., Omega Series), Springer-Verlag, Berlin etc., 1987.
9. Ершов Ю.Л. Теория нумераций (Наука, М., 1977).
10. Ershov Yu.L. Theory of numberings, in: Handbook of Computability Theory, 140, Stud. Logic Found. Math., ed. by Griffor E.R. (Elsevier, Amsterdam, 1999).
11. Brodhead P., Kjos-Hanssen B., Numberings and randomness, in: Mathematical Theory and Computational practice. CiE 2009, V. 5635, Lecture Notes in Computer Science ed. by K. Ambos-Spies, B. Lo¨we, W. Merkle (Springer, Berlin, Heidelberg, 2009).
12. Faizrahmanov M., Kalimullin I. Limitwise monotonic sets of reals, Math. Log. Quart. 61 (3), 224–229 (2015).
13. Herbert I., Jain S., Mustafa M., Lempp S., Stephan F. Reductions between types of numbering, Ann. Pure. App. Log. 170 (12), 102716 (2019).
14. Бадаев С.А. О позитивных нумерациях, Сиб. матем. журн. 18 (3), 483–496 (1977).
15. Faizrahmanov M., Shchedrikova Z. Effectively infinite classes of numberings and computable families of reals, Comput. 12 (4), 339–350 (2023).
Review
For citations:
Nodirov Sh.D., Faizrahmanov M.Kh., Shchedrikova Z.K. On infinite direct sums of minimal numberings of functional families. Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika. 2025;(4):38-52. (In Russ.) https://doi.org/10.26907/0021-3446-2025-4-38-52
Views:
30
Email this article 