Жалпыланған есептелiмдi үйiрлердiң универсал нөмiрлеулерi
DOI:
https://doi.org/10.26577/JMMCS.2022.v113.i1.03Кілттік сөздер:
Роджерс жарты торы, Ершов иерархиясы, есептелiмдi нөмiрлеу, универсал нөмiрлеу, гипериммунды жиынАннотация
Бұл жұмыста жиындардан және барлық жерде анықталған функциялардан құралған әр түрлi үйiрлердiң универсал жалпыланған есептелiмдi нөмiрлеулерi болуы туралы сұрақтар зерттеледi. Бұрыннан белгiлi кез келген A жиыны үшiн, бұл жерде ∅ 0 ≤T A, A-е.с. S ақырлы үйiрiнде A-есептелiмдi универсал нөмiрлеу болады, сонда тек сонда ғана S үйiрi iшкi жиын қатынасы бойынша ең кiшi элементтi қамтыса. Бұл критерий шексiз үйiрлер үшiн орындалмайды. Кез келген A жиыны үшiн A-есептелiмдi универсал нөмiрлеуi бар iшкi жиын қатынасы бойынша ең кiшi элементтi қамтымайтын жиындардан құралған шексiз A-есептелiмдi S үйiрi табылады, сонымен қатар S үйiрiнде барлық элементтер жұптық қиылыспайды. Егер A– гипериммунды жиын болса, онда кем дегенде екi элементi бар барлық жерде анықталған функциялардан құралған A-есептелiмдi F үйiрiнде A-есептелiмдi универсал нөмiрлеуi болмайды. Ал егер degT (A) гипериммунды-бос болса, онда әрбiр барлық жерде анықталған функциялардан құралған үйiрде A-есептелiмдi универсал нөмiрлеуi болады. Бұл жұмыста бiз A-гипериммунды-бос оракулымен есептелетiн жиындардан құралған кез келген шексiз эффективтi дискреттi үйiрлерде A-есептелiмдi универсал нөмiрелуi болатынын көрсеттiк. Сондай-ақ, егер S үйiрi барлық толықтауы ақырлы жиындарды қамтыса және кем дегенде бiр толықтауы рекурсив саналымды жиынды қамтымаса, онда бұл үйiрдiң универсал Σ −1 2 - есептелiмдi нөмiрлеуi болмайтыны дәлелдендi.
Библиографиялық сілтемелер
[2] Badaev S. A., Goncharov S. S. "Theory of numberings: open problems", Computability Theory
and Its Applications Amer. Math. Soc., Providences, (2000); 23–38.
[3] Korolkov Yu. D. "Evaluating the Complexity of Index Sets for Families of General Recursive
Functions in the Arithmetic Hierarchy", Algebra and Logic, (2002); 41(2): 87–92.
[4] Soare R. I. "Recursively enumerable sets and degrees", Perspect. Math. Log., Omega Series,
Heidelberg a.o., Springer-Verlag, (1987).
[5] Ershov Yu. L. "A hierarchy of sets, I", Algebra and Logic, (1968); 7(1): 15–47.
[6] Goncharov S. S., Sorbi A. "Generalized computable numerations and nontrivial Rogers
semilattices", Algebra and Logic, (1997); 36(6): 359–369.
[7] Badaev S. A., Goncharov S. S. "Generalized computable universal numberings", Algebra and
Logic, (2014); 53(5): 355–364.
[8] Issakhov A. A. I "Hyperimmunity and A-computable universal numberings", AIP Conference
Proceddings, (2016); 22(3): 402.
[9] Faizrakhmanov M. Kh. "Universal generalized computable numberings and hyperimmunity",
Algebra and Logic, (2017); 56(4): 337–347.
[10] Issakhov A. A., Rakymzhankyzy F, Ostemirova U. "Infinite families of total functions with
principal numberings", Herald of the Kazakh-British technical university, (2021; 18(2):53–58.
[11] Miller Webb, Martin D. A. "The degrees of hyperimmune sets", Z. Math. Logik Grundlagen
Math., (1968); 14: 159–166.
[12] Carl G., Jokush Jr., Soare Robert I. "Π0
1
classes and degrees of theories", Trans. Amer. Math.
Soc., (1972); 173: 33–56.
[13] Badaev S. A., Goncharov S. Sorbi S., A. "Completeness and universality of arithmetical
numberings", Computability and models, New York, Kluwer Academic/Plenum Publishers,
(2003); 11–44.
[14] Ershov Yu. L. "Complete numerations with an infinite number of special elements", Algebra
and Logic, (1970); 9(6): 396–399.
[15] Podzorov S. Yu. "The limit property of the greatest element in the Rogers semilattice", Math.
Trudy, (2004); 7(2): 98–108.
[16] Rakymzhankyzy F, Kalmurzayev B. S., Bazhenov N. A., Issakhov A. A. "Generalized
computable numberings of effectively discrete families", Maltsev Readings, (2021); 72
