INFINITE FAMILIES OF TOTAL FUNCTIONS WITH PRINCIPAL NUMBERINGS
https://doi.org/10.55452/1998-6688-2021-18-2-53-58
Abstract
It was known that any non-single-element (in particular, any infinite) family of total functions with an oracle A, such that Ø′≤TA, does not have A-computable principal numbering; later it was proved that any finite family of total functions with a hyperimmune-free oracle A always has an A-computable principal numbering. The unresolved question was whether there exists an infinite family of total functions with a hyperimmune-free oracle A that has an A-computable principal numbering. The paper gives a positive answer to this question: it is proved that there exists an infinite A-computable family F of total functions, where the Turing degree of the set A is hyperimmune-free, such that F has an A-computable principal numbering.
Supporting agencies: This work was supported by the Science Committee of the Republic of Kazakhstan (Grant AP08856493).
About the Authors
A. A. Issakhov
Kazakh-British technical university
Kazakhstan
Kazakhstan
Assylbek A. Issakhov - PhD Doctor, Head and Professor of the Scientific and Educational Center of Mathematics and Cybernetics
050000, Almaty
F. Rakymzhankyzy
Kazakh-British technical university
Kazakhstan
Kazakhstan
Fariza Rakymzhankyzy - Master of Science, PhD student, Scientific and Educational Center for Mathematics and Cybernetics
050000, Almaty
U. Ostemirova
Kazakh-British technical university
Kazakhstan
Kazakhstan
Uldana B. Ostemirova – PhD student, tutor of the Scientific and Educational Center of Mathematics and Cybernetics
050000, Almaty
References
1. Yu.L. Ershov. Theory of numberings Handbook of Computability Theory. – North-Holland; Amsterdam: Stud. Log. Found. Math., 1999, Vol. 140, pp. 473-503.
2. S.A. Badaev and S.S. Goncharov, Generalized computable universal numberings, Algebra and Logic, vol. 53 (2014), no. 5, pp. 355-364.
3. A.A. Issakhov, Ideals without minimal elements in Rogers semilattices, Algebra and Logic, vol. 54 (2015), no. 3, pp. 197-203.
4. A.A. Issakhov, -computable numberings of the families of total functions, The Bulletin of Symbolic Logic, vol. 22 (2016), no. 3, p. 402.
5. Assylbek Issakhov, Hyperimmunity and -computable universal numberings, AIP Conference Proceedings, vol. 1759, 020106 (2016); doi: 10.1063/1.4959720.
6. M.Kh. Faizrakhmanov, Universal generalized computable numberings and hyperimmunity, Algebra and Logic, vol. 56 (2017), no. 4, pp. 337-347.
7. Soare R.I., Recursively enumerable sets and degrees. – Berlin; Heidelberg; New York: Springer-Verlag, 1987. – 437 p.
8. Miller W., Martin D.A., The degree of hyperimmune sets Z. Math. Logik Grundlag. Math., 1968, Vol. 14, pp. 159-166.
9. Issakhov A.A., Rakymzhankyzy F., Hyperimmunity and -computable numberings The Bulletin of Symbolic Logic, 2018, Vol. 24, No. 2, pp. 248-249.
Review
For citations:
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. https://doi.org/10.55452/1998-6688-2021-18-2-53-58
Views:
421
Email this article 