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. 
@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},
     publisher = {mathdoc},
     volume = {16},
     year = {2019},
     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
PB  - mathdoc
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
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2019_16_a4/
%G ru
%F SEMR_2019_16_a4
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/

[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