kaz29Вестник Казахстанско-Британского технического университетаHerald of the Kazakh-British Technical University1998-66882959-8109Казахстанско-Британский Технический Университет10.55452/1998-6688-2023-20-1-14-20kaz29-606Research ArticleМАТЕМАТИЧЕСКИЕ НАУКИMATHEMATICAL SCIENCESО СУЩЕСТВОВАНИИ УНИВЕРСАЛЬНЫХ НУМЕРАЦИЙON THE EXISTENCE OF UNIVERSAL NUMBERINGShttps://orcid.org/0000-0002-1275-1413НурланбекД. Д.NurlanbekD. D.

Нурланбек Диас Дауренулы, магистрант

050000, Алматы

Nurlanbek Dias Daurenuly, Master student

050000, Almaty

nurlanbek.dias21@gmail.comКазахский Национальный университет имени аль-ФарабиКазахстанAl-Farabi Kazakh National UniversityKazakhstan2023010420232011420Copyright © Нурланбек Д.Д., 20232023Нурланбек Д.Д.Nurlanbek D.D.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.kbtu.edu.kz/jour/article/view/606

Данная статья посвящена исследованию свойства существования универсальных нумераций для различных семейств. Говорят, что нумерация α сводится к нумерации β, если существует вычислимая функция ƒ такая, что α = β ◦ ƒ. Вычислимая нумерация α для некоторого семейства S универсальна, если любая вычислимая нумерация β для семейства S сводится к α. Хорошо известно, что семейство всех вычислимо перечислимых (в.п.) множеств имеет вычислимую универсальную нумерацию. В данной работе мы изучаем семейства почти всех в.п. множеств, рекурсивные множества и почти все разности в.п. множеств, а именно вопросы о существовании универсальных нумераций для данных семейств. Мы доказали, что для семейства всех рекурсивных множеств не существует универсальной нумерации. Также для семейств в.п. множества без пустого элемента, без конечного числа конечных множеств, все еще есть универсальная нумерация. Что касается семейств всех в.п. множества без бесконечного множества, то в этом случае универсальной нумерации не будет. Также мы доказываем, что семейство ∑2-1 \ Β и семейство ∑1-1 не имеют универсальной ∑2-1-вычислимой нумерации для любой  Β ∈ ∑2-1.

The paper is devoted to research existence property of universal numberings for different computable families. A numbering α is reducible to a numbering β if there is computable function ƒ such that α = β ◦ ƒ.  A computable numbering α for some family S is universal if any computable numbering β for the family S is reducible to α. It is well known that the family of all computably enumerable (c.e.) sets has a computable universal numbering. In this paper, we study families of almost all c.e. sets, recursive sets, and almost all differences of c.e. sets, namely questions about the existence of universal numberings for given families. We proved that there is no universal numbering for the family of all recursive sets. For families of c.e. sets without an empty set or a finite number of finite sets, there still exists a universal numbering. However, for families of all c.e. sets without an infinite set, there is no universal numbering. Also, we proved that family ∑2-1 \ Β and the family ∑1-1 has no universal ∑2-1-computable numbering for any Β ∈ ∑2-1.

вычислимые нумерациивычислимо перечислимые множестваполурешетки Роджерсаиерархия Ершовауниверсальная нумерацияComputable numberingcomputably enumerable setsRogers semilatticesErshov's hierarchyuniversal numberingThe work of the authors is supported by the Ministry of Education and Science of the Republic of Kazakhstan, grant AP08856834 “Problems on Rogers semilattices of families of sets in the first and second levels of the Ershov hierarchy”.ReferencesYu. L. Ershov. (1977) Theory of Numerations, Nauka, Moscow. (In Russian)Yu. L. Ershov. (1977) Theory of Numerations, Nauka, Moscow. (In Russian)Badaev S.A., Goncharov S.S. Theory of numberings: open problems. // Computability Theory and Its Applications, Amer. Math. Soc., Providences, 2000, pp. 23–38.Badaev S.A., Goncharov S.S. Theory of numberings: open problems. // Computability Theory and Its Applications, Amer. Math. Soc., Providences, 2000, pp. 23–38.Friedberg, R.M. Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication. J. Symb. Log. 23, 309–316 (1958)/Friedberg, R.M. Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication. J. Symb. Log. 23, 309–316 (1958)/Badaev S.A. On minimal enumerations, Siberian Adv. Math., 1992, v. 2, no. 1, pp. 1–30.Badaev S.A. On minimal enumerations, Siberian Adv. Math., 1992, v. 2, no. 1, pp. 1–30.Badaev S.A. On cardinality of semilattices of numberings of non-discrete families, Sib. Math. J., 1993, v. 34, no. 5, pp. 795–800.Badaev S.A. On cardinality of semilattices of numberings of non-discrete families, Sib. Math. J., 1993, v. 34, no. 5, pp. 795–800.Badaev S.A. Minimal numberings of positively computable families/ Algebra and Logic, 1994, v. 33, no. 2, pp. 131–141.Badaev S.A. Minimal numberings of positively computable families/ Algebra and Logic, 1994, v. 33, no. 2, pp. 131–141.Goncharov S.S., Badaev S.A. Families with one-element Rogers semi-lattice. Algebra and Logic, 1998, v. 37, no. 1, pp. 21–34.Goncharov S.S., Badaev S.A. Families with one-element Rogers semi-lattice. Algebra and Logic, 1998, v. 37, no. 1, pp. 21–34.Khutoretsky A.B. Two existence theorems for computable numerations. Algebra i Logika, 1969, v. 8, no. 4, pp. 484–492. (In Russian).Khutoretsky A.B. Two existence theorems for computable numerations. Algebra i Logika, 1969, v. 8, no. 4, pp. 484–492. (In Russian).Khutoretsky A.B. On the cardinality of the upper semilattice of computable numberings, Algebra and Logic, 1971, v. 10, no. 5, pp. 348–352.Khutoretsky A.B. On the cardinality of the upper semilattice of computable numberings, Algebra and Logic, 1971, v. 10, no. 5, pp. 348–352.Rogers H. Godel numberings of partial computable functions. J. Symbolic Logic, 1958, v. 23, no. 3, pp. 49–57.Rogers H. Godel numberings of partial computable functions. J. Symbolic Logic, 1958, v. 23, no. 3, pp. 49–57.Selivanov V.L. Enumerations of families of general recursive functions. Algebra and Logic, 1976, v. 15, no. 2, pp. 128–141.Selivanov V.L. Enumerations of families of general recursive functions. Algebra and Logic, 1976, v. 15, no. 2, pp. 128–141.Selivanov V.L. Two theorems on computable enumerations. Algebra and Logic, 1976, v. 15, no. 4, pp. 297–306.Selivanov V.L. Two theorems on computable enumerations. Algebra and Logic, 1976, v. 15, no. 4, pp. 297–306.Badaev S.A., Goncharov S.S., Sorbi.A "Isomorphism types of Rogers semilattices for families from different levels of the arithmetical hierarchy. Algebra and Logic, 45:6 (2006), 361–370.Badaev S.A., Goncharov S.S., Sorbi.A "Isomorphism types of Rogers semilattices for families from different levels of the arithmetical hierarchy. Algebra and Logic, 45:6 (2006), 361–370.Goncharov S.S. and Sorbi A. Generalized computable numerations and nontrivial Rogers semilattices. Algebra and Logic, 36, no. 6, 359–369 (1997).Goncharov S.S. and Sorbi A. Generalized computable numerations and nontrivial Rogers semilattices. Algebra and Logic, 36, no. 6, 359–369 (1997).Abeshev K.Sh. On the existence of universal numberings for finite families of d.c.e. sets, Math. Log. Quart. 60, no. 3, 161–167 (2014).Abeshev K.Sh. On the existence of universal numberings for finite families of d.c.e. sets, Math. Log. Quart. 60, no. 3, 161–167 (2014).Badaev S.A., Lempp S. A decomposition of the Rogers semilattice of a family of d.c.e. sets, The Journal of Symbolic Logic, v. 74, no 2, 2009.Badaev S.A., Lempp S. A decomposition of the Rogers semilattice of a family of d.c.e. sets, The Journal of Symbolic Logic, v. 74, no 2, 2009.I. Herbert, S. Jain, S. Lempp, M. Mustafa, and F. Stephan. Reductions between types of numberings, Ann. Pure Appl. Log., 170, no. 12 (2019), article 102716, pp. 1–25.I. Herbert, S. Jain, S. Lempp, M. Mustafa, and F. Stephan. Reductions between types of numberings, Ann. Pure Appl. Log., 170, no. 12 (2019), article 102716, pp. 1–25.Abeshev K.Sh., Badaev S.A., Mustafa M. Families without minimal numberings, Algebra and Logic, v. 53, no 4, 2014.Abeshev K.Sh., Badaev S.A., Mustafa M. Families without minimal numberings, Algebra and Logic, v. 53, no 4, 2014.Badaev S.A., Kalmurzayev B.S., Mukash N., Mustafa M. One-element Rogers semilattices in the Ershov hierarchy, Algebra and Logic, v. 60, no 4, 2021.Badaev S.A., Kalmurzayev B.S., Mukash N., Mustafa M. One-element Rogers semilattices in the Ershov hierarchy, Algebra and Logic, v. 60, no 4, 2021.Badaev S.A., Mustafa M., Sorbi A. Friedberg numberings in the Ershov hierarchy, Arch. Math. Logic, v. 54, 2015.Badaev S.A., Mustafa M., Sorbi A. Friedberg numberings in the Ershov hierarchy, Arch. Math. Logic, v. 54, 2015.Badaev S.A., Mustafa M., Sorbi A. Rogers semilattices of families of two embedded sets in the Ershov hierarchy, Mathematical Logic Quarterly, v. 58, no 4–5, 2012.Badaev S.A., Mustafa M., Sorbi A. Rogers semilattices of families of two embedded sets in the Ershov hierarchy, Mathematical Logic Quarterly, v. 58, no 4–5, 2012.Badaev S.A. and Talasbaeva Zh.T. Computable numberings in the hierarchy of Ershov, Mathematical Logic in Asia, S. S. Goncharov (Ed.), World Scientific, NJ, 17–30 (2006).Badaev S.A. and Talasbaeva Zh.T. Computable numberings in the hierarchy of Ershov, Mathematical Logic in Asia, S. S. Goncharov (Ed.), World Scientific, NJ, 17–30 (2006).Kalmurzayev B.S. Embeddability of the semilattice $L_m^0$ in Rogers semilattices, Algebra and Logic, v. 55, no 3, 2016.Kalmurzayev B.S. Embeddability of the semilattice $L_m^0$ in Rogers semilattices, Algebra and Logic, v. 55, no 3, 2016.Mustafa M., Sorbi A. Positive undecidable numberings in the Ershov hierarchy, Algebra and Logic, v. 50, no 6, 2012.Mustafa M., Sorbi A. Positive undecidable numberings in the Ershov hierarchy, Algebra and Logic, v. 50, no 6, 2012.Ospichev S.S. Properties of numberings in various levels of the Ershov hierarchy, Journal of Mathematical Sciences, v. 188, no 4, 2013.Ospichev S.S. Properties of numberings in various levels of the Ershov hierarchy, Journal of Mathematical Sciences, v. 188, no 4, 2013.Ospichev S.S. Friedberg numberings in the Ershov hierarchy, Algebra and Logic, v. 54, no 4, 2015.Ospichev S.S. Friedberg numberings in the Ershov hierarchy, Algebra and Logic, v. 54, no 4, 2015.Odifreddi P. Classical Recursion Theory, Elsevier, Amsterdam, 1989.Odifreddi P. Classical Recursion Theory, Elsevier, Amsterdam, 1989.

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