Geodesic
Generalized computable universal numberings
Algebra i logika, Tome 53 (2014) no. 5, pp. 555-569.

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

We aim to consider the notion of a computable numbering as a uniform enumeration of sets of a family relative to an arbitrary oracle. The questions under investigation concern primarily universal computable numberings. A study of this kind of numberings is mostly motivated by their nature since any universal numbering of a family contains information on all its computable numberings.
Keywords: computability, universal computable numbering.
Mots-clés : oracle 
@article{AL_2014_53_5_a0,
     author = {S. A. Badaev and S. S. Goncharov},
     title = {Generalized computable universal numberings},
     journal = {Algebra i logika},
     pages = {555--569},
     publisher = {mathdoc},
     volume = {53},
     number = {5},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2014_53_5_a0/}
}
TY  - JOUR
AU  - S. A. Badaev
AU  - S. S. Goncharov
TI  - Generalized computable universal numberings
JO  - Algebra i logika
PY  - 2014
SP  - 555
EP  - 569
VL  - 53
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2014_53_5_a0/
LA  - ru
ID  - AL_2014_53_5_a0
ER  - 
%0 Journal Article
%A S. A. Badaev
%A S. S. Goncharov
%T Generalized computable universal numberings
%J Algebra i logika
%D 2014
%P 555-569
%V 53
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2014_53_5_a0/
%G ru
%F AL_2014_53_5_a0
S. A. Badaev; S. S. Goncharov. Generalized computable universal numberings. Algebra i logika, Tome 53 (2014) no. 5, pp. 555-569. http://geodesic.mathdoc.fr/item/AL_2014_53_5_a0/

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

[2] S. A. Badaev, S. S. Goncharov, “Theory of numberings: open problems”, Computability theory and its applications, Contemp. Math., 257, eds. P. Cholak et al., Am. Math. Soc., Providence, RI, 2000, 23–38 | MR | Zbl

[3] S. A. Badaev, S. S. Goncharov, A. Sorbi, “Completeness and universality of arithmetical numberings”, Computability and models, eds. S. B. Cooper, S. S. Goncharov, Kluwer Academic/Plenum Publishers, New York, 2003, 11–44 | MR

[4] S. A. Badaev, S. S. Goncharov, S. Yu. Podzorov, A. Sorbi, “Algebraic properties of Rogers semilattices of arithmetical numberings”, Computability and models, eds. S. B. Cooper, S. S. Goncharov, Kluwer Academic/Plenum Publishers, New York, 2003, 45–77 | MR

[5] S. A. Badaev, S. S. Goncharov, A. Sorbi, “Isomorphism types and theories of Rogers semilattices of arithmetical numberings”, Computability and models, eds. S. B. Cooper, S. S. Goncharov, Kluwer Academic/Plenum Publishers, New York, 2003, 79–91 | MR

[6] S. A. Badaev, S. S. Goncharov, “O polureshetkakh Rodzhersa semeistv arifmeticheskikh mnozhestv”, Algebra i logika, 40:5 (2001), 507–522 | MR | Zbl

[7] S. A. Badaev, S. S. Goncharov, A. Sorbi, “Ob elementarnykh teoriyakh polureshëtok Rodzhersa”, Algebra i logika, 44:3 (2005), 261–268 | MR | Zbl

[8] S. A. Badaev, S. S. Goncharov, A. Corbi, “Tipy izomorfizmov polureshëtok Rodzhersa semeistv iz razlichnykh urovnei arifmeticheskoi ierarkhii”, Algebra i logika, 45:6 (2006), 637–654 | MR | Zbl

[9] S. A. Badaev, S. Yu. Podzorov, “Minimalnye nakrytiya v polureshetkakh Rodzhersa $\Sigma^0_n$-vychislimykh numeratsii”, Sib. matem. zhurn., 43:4 (2002), 769–778 | MR | Zbl

[10] S. Yu. Podzorov, “Nachalnye segmenty v polureshetkakh Rodzhersa $\Sigma^0_n$-vychislimykh numeratsii”, Algebra i logika, 42:2 (2003), 211–226 | MR | Zbl

[11] S. Yu. Podzorov, “O predelnosti naibolshego elementa polureshëtki Rodzhersa”, Matem. tr., 7:2 (2004), 98–108 | MR | Zbl

[12] S. Yu. Podzorov, “O lokalnom stroenii polureshëtok Rodzhersa $\Sigma^0_n$-vychislimykh numeratsii”, Algebra i logika, 44:2 (2005), 148–172 | MR | Zbl

[13] S. Badaev, S. Goncharov, “Computability and numberings”, New computational paradigms. Changing conceptions of what is computable, eds. S. B. Cooper et al., Springer-Verlag, New York, NY, 2008, 19–34 | MR | Zbl

[14] S. S. Goncharov, “Computable numberings of hyperarithmetical sets and complexity of countable models”, Mathematical theory and computational practice, 5th Conf. on computability in Europe, CiE 2009 (Heidelberg, Germany, July 19–24, 2009), Univ. Heidelberg, 2009, 13–14

[15] Yu. L. Ershov, Teoriya numeratsii, Nauka, M., 1977 | MR

[16] Yu. L. Ershov, “Theory of numberings”, Handbook of computability theory, Stud. Logic Found. Math., 140, ed. E. R. Griffor, Elsevier, Amsterdam, 1999, 473–503 | MR | Zbl

[17] A. I. Maltsev, “Polno numerovannye mnozhestva”, Algebra i logika, 2:2 (1963), 4–29 | MR | Zbl

[18] A. H. Lachlan, “Standard classes of recursively enumerable sets”, Z. Math. Logik Grundlagen Math., 10:1 (1964), 23–42 | DOI | MR | Zbl

[19] R. M. Friedberg, “Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication”, J. Symb. Log., 23:3 (1958), 309–316 | DOI | MR