Geodesic
Positive undecidable numberings in the Ershov hierarchy
Algebra i logika, Tome 50 (2011) no. 6, pp. 759-780.

Voir la notice de l'article provenant de la source Math-Net.Ru

A sufficient condition is given under which an infinite computable family of $\Sigma_a^{-1}$-sets has computable positive but undecidable numberings, where $a$ is a notation for a nonzero computable ordinal. This extends a theorem proved by Talasbaeva in [Algebra and Logic, 42, No. 6 (2003), 737–746] for finite levels of the Ershov hierarchy. As a consequence, it is stated that the family of all $\Sigma_a^{-1}$-sets has a computable positive undecidable numbering. In addition, for every ordinal notation $a>1$, an infinite family of $\Sigma_a^{-1}$-sets is constructed which possesses a computable positive numbering but has no computable Friedberg numberings. This answers the question of whether such families exist at any – finite or infinite – level of the Ershov hierarchy, which was originally raised by Badaev and Goncharov only for the finite levels bigger than 1.
Keywords: Ershov hierarchy, positive undecidable numbering. 
@article{AL_2011_50_6_a4,
     author = {M. Manat and A. Sorbi},
     title = {Positive undecidable numberings in the {Ershov} hierarchy},
     journal = {Algebra i logika},
     pages = {759--780},
     publisher = {mathdoc},
     volume = {50},
     number = {6},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2011_50_6_a4/}
}
TY  - JOUR
AU  - M. Manat
AU  - A. Sorbi
TI  - Positive undecidable numberings in the Ershov hierarchy
JO  - Algebra i logika
PY  - 2011
SP  - 759
EP  - 780
VL  - 50
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2011_50_6_a4/
LA  - ru
ID  - AL_2011_50_6_a4
ER  - 
%0 Journal Article
%A M. Manat
%A A. Sorbi
%T Positive undecidable numberings in the Ershov hierarchy
%J Algebra i logika
%D 2011
%P 759-780
%V 50
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2011_50_6_a4/
%G ru
%F AL_2011_50_6_a4
M. Manat; A. Sorbi. Positive undecidable numberings in the Ershov hierarchy. Algebra i logika, Tome 50 (2011) no. 6, pp. 759-780. http://geodesic.mathdoc.fr/item/AL_2011_50_6_a4/

[1] Zh. T. Talasbaeva, “O pozitivnykh numeratsiyakh semeistv mnozhestv ierarkhii Ershova”, Algebra i logika, 42:6 (2003), 737–746 | MR | Zbl

[2] S. S. Goncharov, A. Sorbi, “Obobschenno vychislimye numeratsii i netrivialnye polureshetki Rodzhersa”, Algebra i logika, 36:6 (1997), 621–641 | MR | Zbl

[3] S. A. Badaev, “O pozitivnykh numeratsiyakh”, Sib. matem. zh., 18:3 (1977), 483–496 | MR | Zbl

[4] S. A. Badaev, S. S. Goncharov, “Theory of Numberings. Open Problems”, Computability theory and its applications. Current trends and open problems, Proc. 1999 AMS–IMS–SIAM joint summer res. conf., Contemp. Math., 257, eds. P. A. Cholak et al., Am. Math. Soc., Providence, RI, 2000, 23–38 | DOI | MR | Zbl

[5] R. Rogers, Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967 ; Kh. Rodzhers, Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972 | MR | Zbl | MR

[6] Yu. L. Ershov, “Ob odnoi ierarkhii mnozhestv. I”, Algebra i logika, 7:1 (1968), 47–73 | MR

[7] Yu. L. Ershov, “Ob odnoi ierarkhii mnozhestv. II”, Algebra i logika, 7:4 (1968), 15–47 | MR | Zbl

[8] Yu. L. Ershov, “Ob odnoi ierarkhii mnozhestv. III”, Algebra i logika, 9:1 (1970), 34–51 | MR | Zbl

[9] S. Ospichev, “Computable family of $\Sigma_a^{-1}$-sets without Friedberg numberings”, CiE 2010, 6th Conf. Comput. Europe, Ponta Delgada, Azores, 2010, 311–315