×

Reductions between types of numberings. (English) Zbl 1439.03077

In this article, the authors obtain a wide collection of results concerning \(k\)-r.e. numberings, \(k\) a positive integer, left-r.e. numberings and \(\alpha\)-r.e. numberings for recursive ordinals \(\alpha\geq \omega\). From the summary: “This paper considers reductions between types of numberings; these reductions preserve the Rogers semilattice of the numberings reduced and also preserve the number of minimal and positive degrees in their semilattice. It is shown how to use these reductions to simplify some constructions of specific semilattices. Furthermore, it is shown that for the basic types of numberings, one can reduce the left-r.e. numberings to the r.e. numberings and the \(k\)-r.e. numberings to the \((k+1)\)-r.e. numberings; all further reductions are obtained by concatenating these reductions.”

MSC:

03D25 Recursively (computably) enumerable sets and degrees
03D30 Other degrees and reducibilities in computability and recursion theory
03D45 Theory of numerations, effectively presented structures
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ash, Christopher J.; Knight, Julia F., Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144 (2000), Elsevier: Elsevier Amsterdam · Zbl 0960.03001
[2] Abeshev, Kuanysh Sh., On the existence of universal numberings for finite families of d.c.e. sets, MLQ Math. Log. Q., 60, 3, 161-167 (2014) · Zbl 1331.03031
[3] Abeshev, Kuanysh Sh.; Badaev, Serikzhan A.; Manat, Mustafa, Families without minimal numberings, Algebra Logic, 53, 4, 271-286 (2014) · Zbl 1318.03049
[4] Afshari, Bahareh; Barmpalias, George; Barry Cooper, S.; Stephan, Frank, Post’s programme for the Ershov hierarchy, J. Logic Comput., 17, 1025-1040 (2007) · Zbl 1136.03028
[5] Badaev, Serikzhan A., Positive enumerations, Sib. Math. J., 18, 343-352 (1977) · Zbl 0411.03036
[6] Badaev, Serikzhan A.; Mustafa, Manat; Sorbi, Andrea, Rogers semilatitices of families of two embedded sets in the Ershov hierarchy, MLQ Math. Log. Q., 58, 4-5, 366-376 (2012) · Zbl 1257.03071
[7] Badaev, Serikzhan A.; Goncharov, Sergey S.; Sorbi, Andrea, Isomorphism types of Rogers semilattices for families from different levels of the arithmetical hierarchy, Algebra Logic, 45, 6, 361-370 (2006) · Zbl 1164.03340
[8] Badaev, Serikzhan A.; Lempp, Steffen, A decomposition of the Rogers semilattice of a family of d.c.e. sets, J. Symbolic Logic, 74, 618-640 (2009) · Zbl 1185.03071
[9] Barmpalias, George; Downey, Rodney G.; Greenberg, Noam, Working with strong reducibilities above totally \(ω\)-ce and array computable degrees, Trans. Amer. Math. Soc., 362, 2, 777-813 (2010) · Zbl 1192.03014
[10] Barmpalias, George; Lewis, Andy; Stephan, Frank, \( \Pi_1^0\) classes, LR degrees and Turing degrees, Ann. Pure Appl. Logic, 152, 21-38 (2008) · Zbl 1156.03040
[11] Brodhead, Paul; Kjos-Hanssen, Bjørn, Numberings and randomness, (Fifth Conference on Computability in Europe, Proceedings. Fifth Conference on Computability in Europe, Proceedings, CiE 2009, Heidelberg, Germany, 19-24 July 2009. Fifth Conference on Computability in Europe, Proceedings. Fifth Conference on Computability in Europe, Proceedings, CiE 2009, Heidelberg, Germany, 19-24 July 2009, Springer LNCS, vol. 5635 (2009)), 49-58 · Zbl 1268.03057
[12] Cooper, S. Barry, Degrees of Unsolvability (1971), University of Leicester, PhD thesis
[13] Cooper, S. Barry, A splitting theorem for the \(n\)-r.e. degrees, Proc. Amer. Math. Soc., 115, 461-471 (1992) · Zbl 0771.03013
[14] Downey, Rodney G.; Hirschfeldt, Denis R., Algorithmic Randomness and Complexity (2010), Springer Science & Business Media · Zbl 1221.68005
[15] Ershov, Yuri L., A certain hierarchy of sets. I, Algebra Logika, 7, 1, 47-74 (1968) · Zbl 0216.00901
[16] Ershov, Yuri L., A certain hierarchy of sets. II, Algebra Logika, 7, 4, 15-47 (1968) · Zbl 0216.00902
[17] Ershov, Yuri L., A certain hierarchy of sets. III, Algebra Logika, 9, 34-51 (1970)
[18] Ershov, Yuri L., Theory of Numberings (1977), Nauka: Nauka Moscow, (in Russian) · Zbl 0948.03040
[19] Franklin, Johanna; Greenberg, Noam; Stephan, Frank; Wu, Guohua, Anticomplex sets and reducibilities with tiny use, J. Symbolic Logic, 78, 1307-1327 (2013) · Zbl 1307.03025
[20] Friedberg, Richard, Three theorems on recursive enumeration, J. Symbolic Logic, 23, 3, 309-316 (1958) · Zbl 0088.01601
[21] Goncharov, Sergey S., Computable univalent numerations, Algebra Logika, 19, 5, 507-551 (1980), 617 · Zbl 0514.03029
[22] Goncharov, Sergey S., Nonequivalent constructivizations, Tr. Inst. Mat. SO AN SSSR, 2, 4-12 (1982), (in Russian) · Zbl 0543.03017
[23] Goncharov, Sergey S.; Sorbi, Andrea, Generalized computable numerations and non-trivial Rogers semilattices, Algebra Logic, 36, 4, 359-369 (1997) · Zbl 0969.03052
[24] Goncharov, Sergey S.; Lempp, Steffen; Solomon, D. Reed, Friedberg numberings of families of \(n\)-computably enumerable sets, Algebra Logic, 41, 81-86 (2002) · Zbl 1063.03028
[25] Greenberg, Noam; Nies, André, Benign cost functions and lowness properties, J. Symbolic Logic, 76, 1, 289-312 (2011) · Zbl 1221.03036
[26] Harrison, Joseph, Recursive pseudo well-orderings, Trans. Amer. Math. Soc., 131, 526-543 (1968) · Zbl 0186.01101
[27] Kjos-Hanssen, Bjørn; Stephan, Frank; Teutsch, Jason, Arithmetic complexity via effective names for random sequences, ACM Trans. Comput. Log., 13, 3, Article 24 pp. (2012) · Zbl 1352.03047
[28] Kučera, Antonín; Nies, André, Demuth randomness and computational complexity, Ann. Pure Appl. Logic, 162, 504-513 (2011) · Zbl 1223.03026
[29] Mustafa, Manat; Sorbi, Andrea, Positive undecidable numberings in the Ershov hierarchy, Algebra Logika, 50, 759-780 (2011) · Zbl 1287.03092
[30] Nies, André, Computability and Randomness, Oxford Logic Guides, vol. 51 (2009), Oxford University Press: Oxford University Press Oxford · Zbl 1169.03034
[31] Odifreddi, Piergiorgio, Classical Recursion Theory, Studies in Logic and the Foundations of Mathematics, vol. 125 (1989), North-Holland: North-Holland Amsterdam · Zbl 0661.03029
[32] Odifreddi, Piergiorgio, Classical Recursion Theory II, Studies in Logic and the Foundations of Mathematics, vol. 143 (1999), Elsevier: Elsevier Amsterdam · Zbl 0661.03029
[33] Ospichev, Sergey, Computable family of \(\Sigma_a^{- 1}\)-sets without Friedberg numberings, (6th Conference on Computability in Europe. 6th Conference on Computability in Europe, CiE 2010, Ponta Delgada, Azores (2010)), 311-315
[34] Ospichev, Sergey, Infinite family of \(\Sigma_a^{- 1}\)-sets with a unique computable numberings, J. Math. Sci., 188, 4, 449-451 (2013) · Zbl 1285.03061
[35] Ospichev, Sergey, Computable families of sets in Ershov hierarchy without principal numberings, J. Math. Sci., 215, 4, 529-536 (2016)
[36] Podzorov, Sergei Yurevich, Arithmetical D-degrees, Sib. Math. J., 49, 6, 1109-1123 (2008) · Zbl 1224.03021
[37] Soare, Robert I., Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic. (1987), Springer-Verlag: Springer-Verlag Berlin · Zbl 0623.03042
[38] Frank Stephan, Yue Yang, Liang Yu, Turing degrees and the Ershov hierarchy, in: Proceedings of the 10th Asian Logic Conference, Kobe, Japan, 1-6 September 2008, pp. 300-321.; Frank Stephan, Yue Yang, Liang Yu, Turing degrees and the Ershov hierarchy, in: Proceedings of the 10th Asian Logic Conference, Kobe, Japan, 1-6 September 2008, pp. 300-321. · Zbl 1203.03056
[39] Stephan, Frank; Teutsch, Jason, Things which can be made into themselves, Inform. and Comput., 237, 174-186 (2014) · Zbl 1336.03049
[40] Vyugin, Vladimir V., On minimal enumerations of computable classes of recursively enumerable sets, Sov. Math., Dokl., 14, 2, 1338-1340 (1973), translated · Zbl 0298.02033
[41] Vyugin, Vladimir V., On some upper semilattices of computable enumerations, Algebra Logika, 12, 5, 287-296 (1973), translated · Zbl 0305.02059
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.