БЕСКОНЕЧНЫЕ СЕМЕЙСТВА ВСЮДУ ОПРЕДЕЛЕННЫХ ФУНКЦИЙ С ГЛАВНЫМИ НУМЕРАЦИЯМИ

Ранее было известно, что любое не одноэлементное (в частности, любое бесконечное) семейство всюду определенных функций с оракулом А, такое что Ø′≤_TA, не имеет А-вычислимую главную нумерацию, позже было доказано, что любое конечное семейство всюду определенных функций с гипериммунно-свободным оракулом А всегда обладает А-вычислимой главной нумерацией. Оставался нерешенным вопрос о том, что существует ли бесконечное семейство всюду определенных функций с гипериммунно-свободным оракулом А, которое имеет -вычислимую главную нумерацию. В работе приводится положительный ответ на указанный вопрос: доказано, что существует бесконечное -вычислимое семейство F всюду определенных функций, где тьюрингова степень множества A гипериммунно-свободна, такое, что F имеет A-вычислимую главную нумерацию.

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.