Minimal generalized computable enumerations and high degrees. (English. Russian original) Zbl 1420.03106
Sib. Math. J. 58, No. 3, 553-558 (2017); translation from Sib. Mat. Zh. 58, No. 3, 710-716 (2017).
Summary: We establish that the set of minimal generalized computable enumerations of every infinite family computable with respect to a high oracle is effectively infinite. We find some sufficient condition for enumerations of the infinite families computable with respect to high oracles under which there exist minimal generalized computable enumerations that are irreducible to the enumerations.
MSC:
| 03D45 | Theory of numerations, effectively presented structures |
| 03D30 | Other degrees and reducibilities in computability and recursion theory |
Keywords:
generalized computable enumeration; minimal enumeration; high set; \(\mathrm{Low}_2\) set; arithmetic enumerationReferences:
| [1] | Goncharov S. S. and Sorbi A., “Generalized computable numerations and nontrivial Rogers semilattices,” Algebra and Logic, vol. 36, no. 6, 359-369 (1997). · Zbl 0969.03052 · doi:10.1007/BF02671553 |
| [2] | Badaev S. A. and Goncharov S. S., “Rogers semilattices of families of arithmetic sets,” Algebra and Logic, vol. 40, no. 5, 283-291 (2001). · Zbl 0989.03040 · doi:10.1023/A:1012516217265 |
| [3] | Badaev S. A. and Podzorov S. Yu., “Minimal coverings in the Rogers semilattices of Σn0-computable numberings,” Sib. Math. J., vol. 43, no. 4, 616-622 (2002). · Zbl 1008.03026 · doi:10.1023/A:1016364016981 |
| [4] | Badaev S. A., Goncharov S. S., and Sorbi A., “Elementary theories for Rogers semilattices,” Algebra and Logic, vol. 44, no. 3, 143-147 (2005). · Zbl 1106.03041 · doi:10.1007/s10469-005-0016-x |
| [5] | Badaev S. A., Goncharov S. S., and Sorbi A., “Isomorphism types of Rogers semilattices for families from different levels of the arithmetical hierarchy,” Algebra and Logic, vol. 45, no. 6, 361-370 (2006). · Zbl 1164.03340 · doi:10.1007/s10469-006-0034-3 |
| [6] | Ershov Yu. L., Theory of Numberings [Russian], Nauka, Moscow (1977). · Zbl 0948.03040 |
| [7] | Ershov, Yu. L.; Griffor, E. R. (ed.), Theory of numberings, 473-503 (1999) · Zbl 0948.03040 · doi:10.1016/S0049-237X(99)80030-5 |
| [8] | 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 |
| [9] | Faizrahmanov M. Kh., “Universal generalized computable numerations and hyperimmunity,” Algebra and Logic (to be published). · Zbl 1420.03106 |
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.
