Geodesic
Weak reducibility of computable and generalized computable numberings
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 18 (2021) no. 1, pp. 112-120 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider universal and minimal computable numberings with respect to weak reducibility. A family of total functions that have a universal numbering and two non-weakly equivalent computable numberings is constructed. A sufficient condition for the non-existence of minimal $A$-computable numberings of families with respect to weak reducibility is found for every oracle $A$.
Keywords: computable numbering, $w$-reducibility, $A$-computable numbering, Rogers semilattice. 
@article{SEMR_2021_18_1_a1,
     author = {Z. K. Ivanova and M. Kh. Faizrahmanov},
     title = {Weak reducibility of computable and generalized computable numberings},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {112--120},
     year = {2021},
     volume = {18},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a1/}
}
TY  - JOUR
AU  - Z. K. Ivanova
AU  - M. Kh. Faizrahmanov
TI  - Weak reducibility of computable and generalized computable numberings
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2021
SP  - 112
EP  - 120
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a1/
LA  - en
ID  - SEMR_2021_18_1_a1
ER  - 
%0 Journal Article
%A Z. K. Ivanova
%A M. Kh. Faizrahmanov
%T Weak reducibility of computable and generalized computable numberings
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2021
%P 112-120
%V 18
%N 1
%U http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a1/
%G en
%F SEMR_2021_18_1_a1
Z. K. Ivanova; M. Kh. Faizrahmanov. Weak reducibility of computable and generalized computable numberings. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 18 (2021) no. 1, pp. 112-120. http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a1/

[1] S. Yu. Podzorov, “On the limit property of the greatest element in the Rogers semilattice”, Sib. Adv. Math., 15:2 (2005), 104–114 | MR | Zbl

[2] S.S. Goncharov, A. Sorbi, “Generalized computable numerations and nontrivial Rogers semilattices”, Algebra Logic, 36:6 (1997), 359–369 | DOI | MR | Zbl

[3] S.A. Badaev, S.S. Goncharov, “Generalized computable universal numberings”, Algebra Logic, 53:5 (2014), 355–364 | DOI | MR | Zbl

[4] Yu.L. Ershov, Theory of Numberings, Nauka, M., 1977 | MR

[5] S. Yu. Podzorov, “Local structure of Rogers semilattices of $\Sigma^0_n$-computable numberings”, Algebra Logic, 44:2 (2005), 82–94 | DOI | MR | Zbl

[6] S.A. Badaev, S.S. Goncharov, A. Sorbi, “Isomorphism types of Rogers semilattices for families from different levels of the arithmetical hierarchy”, Algebra Logic, 45:6 (2006), 361–370 | DOI | MR | Zbl

[7] M. Kh. Faizrakhmanov, “Khutoretskii's theorem for generalized computable families”, Algebra Logic, 58:4 (2019), 356–365 | DOI | MR | Zbl

[8] R.I. Soare, Turing computability. Theory and applications, Springer-Verlag, Berlin, 2016 | MR | Zbl

[9] M. Kh. Faizrakhmanov, “Universal generalized computable numberings and hyperimmunity”, Algebra Logic, 56:4 (2017), 337–347 | DOI | MR | Zbl

[10] C.G. Jun. Jockusch, “The degrees of bi-immune sets”, Z. Math. Logik Grundlagen Math., 15 (1969), 135–140 | DOI | MR | Zbl

[11] S.S. Marchenkov, “The computable enumerations of families of general recursive functions”, Algebra Logic, 11:5 (1972), 326–336 | DOI | MR | Zbl

[12] S.A. Badaev, “Positive enumerations”, Sib. Math. J., 18:3 (1978), 343–352 | DOI | MR | Zbl

[13] M. Kh. Faizrahmanov, “Minimal generalized computable enumerations and high degrees”, Sib. Math. J., 58:3 (2017), 553–558 | DOI | MR | Zbl