Geodesic
An example of a simple quasi-universal function in the class $\mathcal E^2$ of the Grzegorczyk hierarchy
Diskretnaya Matematika, Tome 18 (2006) no. 4, pp. 31-44 
S. A. Volkov. An example of a simple quasi-universal function in the class $\mathcal E^2$ of the Grzegorczyk hierarchy. Diskretnaya Matematika, Tome 18 (2006) no. 4, pp. 31-44. http://geodesic.mathdoc.fr/item/DM_2006_18_4_a3/
@article{DM_2006_18_4_a3,
     author = {S. A. Volkov},
     title = {An example of a~simple quasi-universal function in the class $\mathcal E^2$ of the {Grzegorczyk} hierarchy},
     journal = {Diskretnaya Matematika},
     pages = {31--44},
     year = {2006},
     volume = {18},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2006_18_4_a3/}
}
TY  - JOUR
AU  - S. A. Volkov
TI  - An example of a simple quasi-universal function in the class $\mathcal E^2$ of the Grzegorczyk hierarchy
JO  - Diskretnaya Matematika
PY  - 2006
SP  - 31
EP  - 44
VL  - 18
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2006_18_4_a3/
LA  - ru
ID  - DM_2006_18_4_a3
ER  - 
%0 Journal Article
%A S. A. Volkov
%T An example of a simple quasi-universal function in the class $\mathcal E^2$ of the Grzegorczyk hierarchy
%J Diskretnaya Matematika
%D 2006
%P 31-44
%V 18
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2006_18_4_a3/
%G ru
%F DM_2006_18_4_a3

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

We give an example of a quasi-universal function in the class $\mathcal E^2$ of the Grzegorczyk hierarchy. This function is of very simple structure and does not contain an explicit enumeration of any Turing machine. As a corollary we obtain a simple basis over superposition in the class $\mathcal E^2$.

[1] Gzhegorchik A., “Nekotorye klassy rekursivnykh funktsii”, Problemy matematicheskoi logiki, Mir, Moskva, 1970, 9–49

[2] Maltsev A. I., Algoritmy i rekursivnye funktsii, Nauka, Moskva, 1986

[3] Marchenkov C. S., “Bazisy po superpozitsii v klassakh rekursivnykh funktsii”, Matem. voprosy kibernetiki, 3 (1991), 115–139 | Zbl

[4] Marchenkov S. S., “Ob ogranichennykh rekursiyakh”, Mathematica Balkanica, 2 (1972), 124–142 | MR | Zbl

[5] Marchenkov C. S., “Ob odnom bazise po superpozitsii v klasse funktsii, elementarnykh po Kalmaru”, Matem. zametki, 27:3 (1980), 321–332 | MR | Zbl

[6] Marchenkov C. S., “Prostye primery bazisov po superpozitsii v klasse funktsii, elementarnykh po Kalmaru”, Banach Center Publ., 25 (1989), 119–126

[7] Marchenkov S. S., Elementarnye rekursivnye funktsii, MTsNMO, Moskva, 2003

[8] Minskii M., Vychisleniya i avtomaty, Mir, Moskva, 1971