FRIEDBERG NUMBERINGS WITH A HYPERIMMUNE ORACLE
Abstract
The present work investigates several questions related to hyperimmunity and A-computable Friedberg numberings of families of total functions. It is shown that if F is an infinite A-computable family of total functions, where A is an arbitrary set, then F has an A-computable Friedberg numbering; for every hyperimmune set A there exists a non-recursive A-computable set B; and also, that if F is an infinite A-computable family of total functions, where A is a hyperimmune set, then F has infinitely many pairwise nonequivalent A-computable Friedberg numberings.
About the Authors
A. A. Issakhov
Kazakh-British Technical University
Kazakhstan
Kazakhstan
F. Rakymzhankyzy
Al-Farabi Kazakh National University
Kazakhstan
Kazakhstan
References
1. Rogers H. Godel numberings of partial computable functions J. Symbolic Logic, 1956, Vol. 23, pp. 49-57.
2. Soare R. I. Recursively enumerable sets and degrees. - Berlin; Heidelberg; New York: SpringerVerlag, 1987. - 437 p.
3. Miller W., Martin D. A. The degree of hyperimmune sets Z. Math. LogikGrundlag. Math., 1968, Vol. 14, pp. 159-166.
4. Ershov Yu. L. Theory of numberings Handbook of Computability Theory. - North-Holland; Amsterdam: Stud. Log. Found. Math., 1999, Vol. 140, pp. 473-503.
5. Badaev S. A., Goncharov S. S., Sorbi A. Completeness and universality of arithmetical numberings Computability and Models, S. B. Cooper and S. S. Goncharov (eds.). - New York: Kluwer Academic/Plenum Publishers, 2003, pp. 11-44.
6. Badaev S. A., Issakhov A. A. Some absolute properties of Л-computable numberings Algebra and Logic, 2018, Vol. 57, No. 4, pp. 275-288.
7. Issakhov A. A. Ideals without minimal elements in Rogers semilattices Algebra and Logic, 2015, Vol. 54, No. 3, pp. 197-203.
8. Issakhov A. A. A-computable numberings of the families of total functions The Bulletin of Symbolic Logic, 2016, Vol. 22, No. 3, p. 402.
9. Issakhov A. A., Rakymzhankyzy F. Hyperimmunity and A-computable numberings The Bulletin of Symbolic Logic, 2018, Vol. 24, No. 2, pp. 248-249.
Review
For citations:
Issakhov A.A., Rakymzhankyzy F. FRIEDBERG NUMBERINGS WITH A HYPERIMMUNE ORACLE. Herald of the Kazakh-British technical university. 2019;16(1):68-72.
Views:
309
Email this article 