Geodesic
Friedberg numberings of families of partial computable functionals
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 331-339

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

We consider computable numberings of families of partial computable functionals of finite types. We show, that if a family of all partial computable functionals of type 0 has a computable Friedberg numbering, then family of all partial computable functionals of any given type also has computable Friedberg numbering. Furthermore, for a type $\sigma|\tau$ there are infinitely many nonequivalent computable minimal nonpositive, positive nondecidable and Friedberg numberings.
Keywords: partial computable functionals, computable morphisms, computable numberings, Rogers semilattice, minimal numbering, positive numbering, Friedberg numbering. 
S. S. Ospichev. Friedberg numberings of families of partial computable functionals. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 331-339. http://geodesic.mathdoc.fr/item/SEMR_2019_16_a4/
@article{SEMR_2019_16_a4,
     author = {S. S. Ospichev},
     title = {Friedberg numberings of families of partial computable functionals},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {331--339},
     year = {2019},
     volume = {16},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2019_16_a4/}
}
TY  - JOUR
AU  - S. S. Ospichev
TI  - Friedberg numberings of families of partial computable functionals
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2019
SP  - 331
EP  - 339
VL  - 16
UR  - http://geodesic.mathdoc.fr/item/SEMR_2019_16_a4/
LA  - ru
ID  - SEMR_2019_16_a4
ER  - 
%0 Journal Article
%A S. S. Ospichev
%T Friedberg numberings of families of partial computable functionals
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2019
%P 331-339
%V 16
%U http://geodesic.mathdoc.fr/item/SEMR_2019_16_a4/
%G ru
%F SEMR_2019_16_a4

[1] Yu.L. Ershov, Theory of numerations, Nauka, M., 1977 (In Russian) | MR

[2] S.A. Badaev, S.S. Goncharov, “Computability and numberings”, New Computational Paradigms, eds. S.B. Cooper, B. Lowe, A. Sorbi, Springer, 2008, 19–34 | DOI | MR | Zbl

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

[4] S.A. Badaev, S.S. Goncharov, “Rogers semilatices of families of arithmetic sets”, Algebra and Logic, 40:5 (2001), 283–291 | DOI | MR | Zbl

[5] S.A. Badaev, S.S. Goncharov, A. Sorbi, “On elementary theories of Rogers semilattices”, Algebra and Logic, 44:3 (2005), 143–147 | 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 and Logic, 45:6 (2006), 361–370 | DOI | MR | Zbl

[7] S.A. Badaev, S. Yu. Podzorov, “Minimal coverings in the Rogers semilattices of $\Sigma^0_n$-computable numberings”, Siberian Math. J., 43:4 (2002), 616–622 | DOI | MR | Zbl

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

[9] S.S. Goncharov, S. Lempp, D.R. Solomon, “Friedberg numberings of families of $n$-computably enumerable sets”, Algebra and Logic, 41:2 (2002), 81–86 | DOI | MR | Zbl

[10] S.S. Ospichev, “Friedberg numberings in the {E}rshov hierarchy”, Algebra and Logic, 54:4 (2015), 283–295 | DOI | MR | Zbl

[11] K. Sh. Abeshev, S.A. Badaev, M. Mustafa, “Families Without Minimal Numberings”, Algebra and Logic, 53:4 (2014), 271–286 | DOI | MR | Zbl

[12] K. Sh. Abeshev, “On the existence of universal numberings for finite families of d.c.e. sets”, Math. Logic Quat., 60:3 (2014), 161–167 | DOI | MR | Zbl

[13] S.A. Badaev, S. Lempp, “A Decomposition of the Rogers semilattice of a family of d.c.e. sets”, J. Symb. Logic, 74:2 (2009), 618–640 | DOI | MR | Zbl

[14] Yu.L. Ershov, “Computable functionals of finite types”, Algebra and Logic, 11:4 (1972), 203–242 | DOI | MR

[15] Yu.L. Ershov, “Everywhere-defined continuous functionals”, Algebra and Logic, 11:6 (1972), 363–368 | DOI | MR

[16] M. Kummer, “An easy priority-free proof of a theorem of Friedberg”, Theoretical Computer Science, 74:2 (1990), 249–251 | DOI | MR | Zbl

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

[18] A.B. Hutoreckii, “Two existence theorems for computable numerations”, Algebra and Logic, 8:4 (1969), 277–282 | DOI | MR