Geodesic
Superpositions of elementary arithmetic functions
Diskretnyj analiz i issledovanie operacij, Tome 13 (2006) no. 4, pp. 33-48.

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

A new concise proof of the following theorem is found: the system of four functions $\{x+y,x\div y,\lfloor x/y\rfloor,2^x\}$ induces the class of Kalmar elementary functions. An elimination mode of bounded summation is used in the proof. 
@article{DA_2006_13_4_a3,
     author = {S. S. Marchenkov},
     title = {Superpositions of elementary arithmetic functions},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {33--48},
     publisher = {mathdoc},
     volume = {13},
     number = {4},
     year = {2006},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2006_13_4_a3/}
}
TY  - JOUR
AU  - S. S. Marchenkov
TI  - Superpositions of elementary arithmetic functions
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2006
SP  - 33
EP  - 48
VL  - 13
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2006_13_4_a3/
LA  - ru
ID  - DA_2006_13_4_a3
ER  - 
%0 Journal Article
%A S. S. Marchenkov
%T Superpositions of elementary arithmetic functions
%J Diskretnyj analiz i issledovanie operacij
%D 2006
%P 33-48
%V 13
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2006_13_4_a3/
%G ru
%F DA_2006_13_4_a3
S. S. Marchenkov. Superpositions of elementary arithmetic functions. Diskretnyj analiz i issledovanie operacij, Tome 13 (2006) no. 4, pp. 33-48. http://geodesic.mathdoc.fr/item/DA_2006_13_4_a3/

[1] Kosovskii N. K., Osnovy teorii elementarnykh algoritmov, Izd-vo Leningradskogo un-ta, L., 1987 | MR | Zbl

[2] Maltsev A. I., Algoritmy i rekursivnye funktsii, Nauka, M., 1986 | MR

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

[4] Marchenkov S. S., “Prostye primery bazisov po superpozitsii v klasse funktsii, elementarnykh po Kalmaru”, Combinatorics and Graph Theory, Banach Center Publications, 25, 1989, 119–126 | MR | Zbl

[5] Marchenkov S. S., “Bazisy po superpozitsii v klassakh rekursivnykh funktsii”, Matematicheskie voprosy kibernetiki, Vyp. 3, Nauka, M., 1991, 115–139 | MR

[6] Marchenkov S. S., Elementarnye rekursivnye funktsii, MTsNMO, M., 2003

[7] Matiyasevich Yu. V., “Novoe dokazatelstvo teoremy ob eksponentsialno diofantovom predstavlenii perechislimykh predikatov”, Zapiski nauchnykh seminarov Leningrad. otdeleniya matem. in-ta AN SSSR, 60, 1976, 75–92 | Zbl

[8] Matiyasevich Yu. V., “Odin klass kriteriev prostoty, formuliruemykh v terminakh delimosti binomialnykh koeffitsientov”, Zapiski nauchnykh seminarov Leningrad. otdeleniya matem. in-ta AN SSSR, 67, 1977, 167–183 | MR | Zbl

[9] Davis M., Putnam H., Robinson J., “The decision problem for exponential Diophantine equations”, Ann. Math., 74 (1961), 425–436 | DOI | MR | Zbl

[10] Grzegorczyk A., “Some classes of recursive functions”, Rozprawy Matemematiczne, 4 (1953), 46 ; Gzhegorchik A., “Nekotorye klassy rekursivnykh funktsii”, Problemy matematicheskoi logiki, Mir, M., 1970, 9–49 | MR | Zbl

[11] Kalmar L., “Ein einfach Beispiel für unentscheibares Problem”, Matematikai és Fizikai Lapok, 1943, no. 50, 1–23 | MR | Zbl

[12] Kummer E., “Über die Ergänzugssätze zu den allgemeinen Reciprocitätsgesetzen”, J. Reine Angew. Math., 1852, no. 44, 93–146 | Zbl

[13] Mazzanti S., “Plain bases for classes of primitive recursive functions”, Math. Logic Quarterly, 48:1 (2002), 93–104 | 3.0.CO;2-8 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[14] Ritchie R. W., “Classes of predictably computable functions”, Trans. Amer. Math. Soc., 106 (1963), 139–173 ; Richi R. V., “Klassy predskazuemo vychislimykh funktsii”, Problemy matematicheskoi logiki, Mir, M., 1970, 50–93 | DOI | MR | Zbl | MR