The class of Skolem elementary functions

S. A. Volkov

Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 2, pp. 42-60.

Résumé

In this paper, we consider different equivalent definitions of the class of Skolem elementary functions (these definitions are analogous to the well-known definitions of the Kalmar elementary function class) and some results concerned with this class which are obtained by different mathematicians. Some definitions of this class were investigated by mathematicians independently. In this paper we prove equivalence of these definitions. Also, we study the problem on existence of superposition bases for this class. We prove that this problem is equivalent to one problem from complexity theory. Bibl. 26.

Détail

Keywords: classification of recursive functions, computational complexity.

Bibliographie

[1] Volkov S. A., “Porozhdenie nekotorykh klassov rekursivnykh funktsii superpozitsiyami prostykh arifmeticheskikh funktsii”, Dokl. RAN, 415:4 (2007), 439–440 | MR | Zbl

[2] Volkov S. A., “Eksponentsialnoe rasshirenie klassa funktsii, elementarnykh po Skolemu, i ogranichennye superpozitsii prostykh arifmeticheskikh funktsii”, Mat. voprosy kibernetiki, 16, Fizmatlit, M., 2007, 163–190

[3] Kosovskii N. K., “Vozmozhnosti operatsii odnomestnogo summirovaniya i odnomestnogo ogranichennogo umnozheniya”, Zap. nauch. sem. LOMI, 49, 1975, 3–6 | MR | Zbl

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

[5] Marchenkov S. S., “O funktsiyakh, elementarnykh po Skolemu”, Mat. zametki, 17:1 (1975), 133–141 | Zbl

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

[7] Marchenkov C. S., “Prostye primery bazisov po superpozitsii v klasse funktsii, elementarnykh po Kalmaru”, Banach Center Publication, 25, Warsaw, 1989, 119–126 | MR | Zbl

[8] Marchenkov C. S., “Bazisy po superpozitsii v klassakh rekursivnykh funktsii”, Mat. voprosy kibernetiki, 3, Nauka, M., 1991, 115–139

[9] Marchenkov S. S., Elementarnye rekursivnye funktsii, MTsNMO, M., 2003, 112 pp.

[10] Matiyasevich Yu. V., “Suschestvovanie neeffektiviziruemykh otsenok v teorii eksponentsialno diofantovykh uravnenii”, Zap. nauch. sem. LOMI, 40, 1974, 77–93 | MR | Zbl

[11] Matiyasevich Yu. V., “Novoe dokazatelstvo teoremy ob eksponentsialno diofantovom predstavlenii perechislimykh predikatov”, Zap. nauch. sem. LOMI, 60, 1976, 75–92 | MR | Zbl

[12] Nepomnyaschii V. A., “Rudimentarnoe modelirovanie nedeterminirovannykh tyuringovykh vychislenii”, Kibernetika, 1973, no. 2, 23–29 | Zbl

[13] Allender E., Barrington D. A. M., Hesse W., “Uniform constant-depth threshold circuits for division and iterated multiplication”, J. Comp. System Sci., 65 (2002), 695–716 | DOI | MR | Zbl

[14] Durand A., More M., “Non-erasing, counting and majority over the linear time hierarchy”, Information and Computation, 174:2 (2002), 132–142 | DOI | MR | Zbl

[15] Esbelin H.-A., More M., “Rudimentary relations and primitive recursion: A toolbox”, Theoret. Comp. Sci., 193 (1998), 129–148 | DOI | MR | Zbl

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

[17] Kalmar L., “Egyszerü pelda eldönthetelen aritmetikai problemara”, Matematikai es fizikai lapok, 50 (1943), 1–23 | MR | Zbl

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

[19] Parsons Ch., “Hierarchies of primitive recursive functions”, Zeitschr. math. Logik und Grundlag. Math., 14:4 (1968), 357–376 | DOI | MR | Zbl

[20] Ritchie R. W., “Classes of predicably 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

[21] Rödding D., “Über die Eliminierbarkeit von Definitionsschemata in der Theorie der rekursiven Funktionen”, Zeitschr. math. Logik und Grundlag. Math., 10:4 (1964), 315–330 | DOI | MR | Zbl

[22] Skolem Th., “A theorem on recursively enumerable sets”, Abstract of Short Comm. Int. Congress Math., Stockholm, 1962, 11

[23] Skolem Th., “Proof of some theorems on recursively enumerable sets”, Notre Dame J. Formal Logic, 3:2 (1962), 65–74 | DOI | MR

[24] Smullyan R. M., Theory of Formal Systems, Princeton, 1961, 156 pp. ; Smalyan R., Teoriya formalnykh sistem, Nauka, M., 1981, 207 pp. | MR | MR

[25] Toda S., “On the computational power of PP and $\oplus\mathrm P$”, IEEE Symposium on founations of computer science, 1989, 514–519

[26] Wrathall C., “Rudimentary predicates and relative computation”, SIAM J. Comp., 7:2 (1978), 194–209 | DOI | MR | Zbl