УНИВЕРСАЛ НӨМІРЛЕУЛЕР ТАБЫЛАТЫНДЫҒЫ ТУРАЛЫ

Бұл мақала әр түрлі есептелімді үйірлердің универсал нөмірлеулері табылу қасиеттерін зерттеуге бағытталған. Қандайда бір α нөмірлеуі басқа бір β нөмірлеуіне көшіріледі деп аталынады. Егер α = β ◦ ƒ теңдігін қанағаттандыратын ƒ есептелімді функциясы табылатын болса, кез келген S үйірі үшін α нөмірлеуі универсал болып табылады. Егер S үйіріндегі кез келген β нөмірлеуі α нөмірлеуіне көшірілетін болса, барлық рекурсив саналымды (р. с.) жиындар үйірінің универсал нөмірлеуі табылатындығы белгілі. Біз барлық дерлік жиындардың үйірлерін, рекурсив жиындардың және барлық дерлік р. с. жиындардың айырымының үйірлері үшін универсал нөмірлеулері табылатын табылмайтын қасиеттерін зерттейміз. Біз барлық рекурсив жиындардың үйірінде универсал нөмірлеу жоқ екенін дәлелдедік. Сондай-ақ, бос элементі жоқ, ақырлы жиындардың ақырлы саны жоқ р. с. жиындардың үйірінде универсал нөмірлеу болатынын көрсеттік. Ал ақырсыз р. с. жиыны жоқ барлық р. с. жиындардың үйіріне келетін болсақ, бұл жағдайда универсал нөмірлеу болмайтынын дәлелдедік. Сондай-ақ, біз ∑₂^-1 \ Β және ∑₁^-1 үйірлерінде кез келген Β ∈ ∑₂^-1 үшін ∑₂^-1-есептелімді нөмірлеу болмайтынын дәлелдедік.

1. Yu. L. Ershov. (1977) Theory of Numerations, Nauka, Moscow. (In Russian)

2. Badaev S.A., Goncharov S.S. Theory of numberings: open problems. // Computability Theory and Its Applications, Amer. Math. Soc., Providences, 2000, pp. 23–38.

3. Friedberg, R.M. Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication. J. Symb. Log. 23, 309–316 (1958)/

4. Badaev S.A. On minimal enumerations, Siberian Adv. Math., 1992, v. 2, no. 1, pp. 1–30.

5. Badaev S.A. On cardinality of semilattices of numberings of non-discrete families, Sib. Math. J., 1993, v. 34, no. 5, pp. 795–800.

6. Badaev S.A. Minimal numberings of positively computable families/ Algebra and Logic, 1994, v. 33, no. 2, pp. 131–141.

7. Goncharov S.S., Badaev S.A. Families with one-element Rogers semi-lattice. Algebra and Logic, 1998, v. 37, no. 1, pp. 21–34.

8. Khutoretsky A.B. Two existence theorems for computable numerations. Algebra i Logika, 1969, v. 8, no. 4, pp. 484–492. (In Russian).

9. Khutoretsky A.B. On the cardinality of the upper semilattice of computable numberings, Algebra and Logic, 1971, v. 10, no. 5, pp. 348–352.

10. Rogers H. Godel numberings of partial computable functions. J. Symbolic Logic, 1958, v. 23, no. 3, pp. 49–57.

11. Selivanov V.L. Enumerations of families of general recursive functions. Algebra and Logic, 1976, v. 15, no. 2, pp. 128–141.

12. Selivanov V.L. Two theorems on computable enumerations. Algebra and Logic, 1976, v. 15, no. 4, pp. 297–306.

13. 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.

14. Goncharov S.S. and Sorbi A. Generalized computable numerations and nontrivial Rogers semilattices. Algebra and Logic, 36, no. 6, 359–369 (1997).

15. 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).

16. 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.

17. 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.

18. Abeshev K.Sh., Badaev S.A., Mustafa M. Families without minimal numberings, Algebra and Logic, v. 53, no 4, 2014.

19. 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.

20. Badaev S.A., Mustafa M., Sorbi A. Friedberg numberings in the Ershov hierarchy, Arch. Math. Logic, v. 54, 2015.

21. 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.

22. 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).

23. Kalmurzayev B.S. Embeddability of the semilattice $L_m^0$ in Rogers semilattices, Algebra and Logic, v. 55, no 3, 2016.

24. Mustafa M., Sorbi A. Positive undecidable numberings in the Ershov hierarchy, Algebra and Logic, v. 50, no 6, 2012.

25. Ospichev S.S. Properties of numberings in various levels of the Ershov hierarchy, Journal of Mathematical Sciences, v. 188, no 4, 2013.

26. Ospichev S.S. Friedberg numberings in the Ershov hierarchy, Algebra and Logic, v. 54, no 4, 2015.

27. Odifreddi P. Classical Recursion Theory, Elsevier, Amsterdam, 1989.