izvuzmathИзвестия высших учебных заведений. МатематикаIzvestiya Vysshikh Uchebnykh Zavedenii. Matematika0021-34462076-4626Казанский (Приволжский) федеральный университет10.26907/0021-3446-2025-4-38-52izvuzmath-181Research ArticleСтатьиО бесконечных прямых суммах минимальных нумераций функциональных семействOn infinite direct sums of minimal numberings of functional familiesНодировШ. Д.NodirovSh. D.

Шохрух Дилмуродович Нодиров

Ул. Кучабог, д. 17, Карши, 180100

Shohruh Dilmurodovich Nodirov

17 Kuchabog str., Karshi, 180100

shoh0809@mail.ruФайзрахмановМ. Х.FaizrahmanovM. Kh.

Марат Хайдарович Файзрахманов

Ул. Кучабог, д. 17, Карши, 180100

Marat Khaidarovich Faizrahmanov

18 Kremlyovskaya str., Kazan, 420008

marat.faizrahmanov@gmail.comЩедриковаЗ. К.ShchedrikovaZ. K.

Злата Константиновна Щедрикова

Ул. Университетская, д. 1, Иннополис, 420500

Zlata Konstantinovna Shchedrikova

1 Universitetskaya str., Innopolis, 420500

zlata.shchedrikova@yandex.ruКаршинский государственный университетУзбекистанRepublic of UzbekistanUzbekistanКазанский федеральный университетУзбекистанKazan Federal University RussiaUzbekistanУниверситет ИннополисРоссияInnopolis UniversityRussian Federation202525042025043852Copyright © Нодиров Ш.Д., Файзрахманов М.Х., Щедрикова З.К., 20252025Нодиров Ш.Д., Файзрахманов М.Х., Щедрикова З.К.Nodirov S.D., Faizrahmanov M.K., Shchedrikova Z.K.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://izvuzmath.elpub.ru/jour/article/view/181

В статье рассматриваются два подхода к определению вычислимости нумераций семейств всюду определенных функций. Рассматривается как классическое определение вычислимой нумерации семейства вычислимых функций, согласно которому по номеру функции в этой нумерации эффективно определяется ее геделевский номер, так и расширяющее предыдущее определение, основанное на равномерном применении понятия вычислимо перечислимого слева элемента бэровского пространства. Основной вопрос, исследуемый в статье, заключается в возможности порождения всех вычислимых нумераций семейства замыканием относительно сводимости бесконечных прямых сумм равномерных последовательностей его однозначных, позитивных и минимальных нумераций.

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.

вычислимая нумерацияоднозначная нумерацияпозитивная нумерацияминимальная нумерацияcomputable numberingsingle-valued numberingpositive numberingminimal numberingРабота поддержана грантом Российского научного фонда (проект 23-21-00181) и выполнена в рамках реализации программы развития Научно-образовательного математического центра Приволжского федерального округа (соглашение 075-02-2023-944)ReferencesFriedberg R. Three theorems on recursive enumeration, J. Symb. Log. 23 (3), 309–316 (1958).Friedberg R. Three theorems on recursive enumeration, J. Symb. Log. 23 (3), 309–316 (1958).Schinzel B. On decomposition of Go¨delnumberings into Friedbergnumberings, J. Symb. Log. 47 (2), 267–274 (1982).Schinzel B. On decomposition of Go¨delnumberings into Friedbergnumberings, J. Symb. Log. 47 (2), 267–274 (1982).Ершов Ю.Л. Нумерации семейств общерекурсивных функций, Сиб. матем. журн. 8 (5), 1015–1025 (1967).Ершов Ю.Л. Нумерации семейств общерекурсивных функций, Сиб. матем. журн. 8 (5), 1015–1025 (1967).Марченков С.С. О вычислимых нумерациях семейств общерекурсивных функций, Алгебра и логика 11 (5), 588–607 (1972).Марченков С.С. О вычислимых нумерациях семейств общерекурсивных функций, Алгебра и логика 11 (5), 588–607 (1972).Downey R.G., Hirschfeldt D.R. Algorithmic Randomness and Complexity, Theory Appl. Comput. (Springer, New York, 2010).Downey R.G., Hirschfeldt D.R. Algorithmic Randomness and Complexity, Theory Appl. Comput. (Springer, New York, 2010).Kjos-Hanssen B., Stephan F., Teutsch J. Arithmetic complexity via effective names for random sequences, ACM Trans. Comput. Log. 13 (3), 1–18 (2012).Kjos-Hanssen B., Stephan F., Teutsch J. Arithmetic complexity via effective names for random sequences, ACM Trans. Comput. Log. 13 (3), 1–18 (2012).Stephan F., Teutsch J. Things that can be made into themselves, Information and Computation 237, 174–186 (2014).Stephan F., Teutsch J. Things that can be made into themselves, Information and Computation 237, 174–186 (2014).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.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.Ершов Ю.Л. Теория нумераций (Наука, М., 1977).Ершов Ю.Л. Теория нумераций (Наука, М., 1977).Ershov Yu.L. Theory of numberings, in: Handbook of Computability Theory, 140, Stud. Logic Found. Math., ed. by Griffor E.R. (Elsevier, Amsterdam, 1999).Ershov Yu.L. Theory of numberings, in: Handbook of Computability Theory, 140, Stud. Logic Found. Math., ed. by Griffor E.R. (Elsevier, Amsterdam, 1999).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).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).Faizrahmanov M., Kalimullin I. Limitwise monotonic sets of reals, Math. Log. Quart. 61 (3), 224–229 (2015).Faizrahmanov M., Kalimullin I. Limitwise monotonic sets of reals, Math. Log. Quart. 61 (3), 224–229 (2015).Herbert I., Jain S., Mustafa M., Lempp S., Stephan F. Reductions between types of numbering, Ann. Pure. App. Log. 170 (12), 102716 (2019).Herbert I., Jain S., Mustafa M., Lempp S., Stephan F. Reductions between types of numbering, Ann. Pure. App. Log. 170 (12), 102716 (2019).Бадаев С.А. О позитивных нумерациях, Сиб. матем. журн. 18 (3), 483–496 (1977).Бадаев С.А. О позитивных нумерациях, Сиб. матем. журн. 18 (3), 483–496 (1977).Faizrahmanov M., Shchedrikova Z. Effectively infinite classes of numberings and computable families of reals, Comput. 12 (4), 339–350 (2023).Faizrahmanov M., Shchedrikova Z. Effectively infinite classes of numberings and computable families of reals, Comput. 12 (4), 339–350 (2023).

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