Positive presentations of families relative to \(e\)-oracles. (English. Russian original) Zbl 1469.03123
Sib. Math. J. 59, No. 4, 648-656 (2018); translation from Sib. Mat. Zh. 59, No. 4, 823-833 (2018).
Summary: We introduce the notion of \(A\)-numbering which generalizes the classical notion of numbering. All main attributes of classical numberings are carried over to the objects considered here. The problem is investigated of the existence of positive and decidable computable \(A\)-numberings for the natural families of sets \(e\)-reducible to a fixed set. We prove that, for every computable \(A\)-family containing an inclusion-greatest set, there also exists a positive computable \(A\)-numbering. Furthermore, for certain families we construct a decidable (and even single-valued) computable total \(A\)-numbering when \(A\) is a low set; we also consider a relativization containing all cases of total sets (this in fact corresponds to computability with a usual oracle).
MSC:
| 03D45 | Theory of numerations, effectively presented structures |
| 03D25 | Recursively (computably) enumerable sets and degrees |
Keywords:
enumeration; decidable numbering; positive numbering; computable numbering; computable set; computably enumerable set; \(e\)-reducibilityReferences:
| [1] | Ershov Yu. L., The Theory of Enumerations [Russian], Nauka, Moscow (1977). |
| [2] | Ershov Yu. L., Definability and Computability, Consultants Bureau, New York and London (1996). · Zbl 0870.03019 |
| [3] | Kalimullin, I. Sh.; Puzarenko, V. G., Computable principles on admissible sets, Siberian Adv. Math., 15, 1-33, (2005) |
| [4] | Soare R. I., Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Springer-Verlag, Berlin, Heidelberg, New York, London, Paris, and Tokyo (1987). · Zbl 0623.03042 · doi:10.1007/978-3-662-02460-7 |
| [5] | Rogers H., Theory of Recursive Functions and Effective Computability, McGraw-Hill Book Comp., New York, St. Louis, San Francisco, Toronto, London, and Sydney (1967). · Zbl 0183.01401 |
| [6] | Goncharov, S. S.; Sorbi, A., Generalized computable numerations and nontrivial Rogers semilattices, Algebra and Logic, 36, 359-369, (1997) · Zbl 0969.03052 · doi:10.1007/BF02671553 |
| [7] | Badaev, S. A.; Goncharov, S. S., Generalized computable universal numberings, Algebra and Logic, 53, 355-364, (2014) · Zbl 1318.03050 · doi:10.1007/s10469-014-9296-3 |
| [8] | Issakhov, A. A., Ideals without minimal elements in Rogers semilattices, Algebra and Logic, 54, 197-203, (2015) · Zbl 1393.03024 · doi:10.1007/s10469-015-9340-y |
| [9] | Faizrahmanov, M. Kh., Universal generalized computable numberings and hyperimmunity, Algebra and Logic, 56, 337-347, (2017) · Zbl 1420.03092 · doi:10.1007/s10469-017-9454-5 |
| [10] | Faizrahmanov, M. Kh., Minimal generalized computable enumerations and high degrees, Sib. Math. J., 58, 553-558, (2017) · Zbl 1420.03106 · doi:10.1134/S0037446617030181 |
| [11] | Badaev, S. A.; Goncharov, S. S., The theory of numberings: open problems, Contemp. Math., 257, 23-38, (2000) · Zbl 0961.03038 · doi:10.1090/conm/257/04025 |
| [12] | Badaev, S. A., Positive enumerations, Sib. Math. J., 18, 343-352, (1977) · Zbl 0411.03036 · doi:10.1007/BF00967026 |
| [13] | Goncharov, S. S.; Lempp, S.; Solomon, D. R., Friedberg numberings of families of n-computably enumerable sets, Algebra and Logic, 41, 81-86, (2002) · Zbl 1063.03028 · doi:10.1023/A:1015352513117 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
