Plain bases for classes of primitive recursive functions. (English) Zbl 1017.03018
The author investigates finite bases (the closure operation is substitution, and the bases are assumed to contain also projection functions) for L. Kalmár’s class \(\mathbf{E}\) of elementary functions [L. Kalmár, Mat. Fiz. Lapok 50, 1–23 (1943; Zbl 0063.03115)] as well as for A. Grzegorczyk’s hierarchy \(\mathcal{E}^n\) [A. Grzegorczyk, Some classes of recursive functions. Rozprawy Mat. 4 (1953; Zbl 0052.24902)] for \(n\geq 3\). A finite basis for \(\mathbf{E}\) was first found by D. Rödding [Z. Math. Logik Grundlagen Math. 10, 315–330 (1964; Zbl 0199.02502)] and then by S. S. Marchenkov [Mat. Zametki 27, 321–332 (1980); translation in Math. Notes 27, 161–166 (1980; Zbl 0483.03025)].
The author proves that there exist three new bases for \(\mathbf{E}\) containing very natural and simple functions. Particularly, one of the bases consists of addition, square, the remainder, and the base two exponential functions. Particularly, for every \(n>3\), \(\mathcal{E}^n\) is shown to be the closure of each of these bases augmented with an additional Ackermann-like function \(f_n\) due to R. W. Ritchie [Pac. J. Math. 15, 1027–1044 (1965; Zbl 0133.24903)].
The obtained results enable the author to simplify the proof of H. Müller’s theorem [Klassifizierungen der primitiv rekursiven Funktionen. Dissertation, Münster (1974)] stating that for every \(n\geq 2\), \(\mathcal{E}^{n+1}=\mathbf{K}_n\), where \(\mathbf{K}_n\) is P. Axt’s hierarchy [P. Axt, Z. Math. Logik Grundlagen Math. 11, 253–255 (1965; Zbl 0144.00201)].
The author proves that there exist three new bases for \(\mathbf{E}\) containing very natural and simple functions. Particularly, one of the bases consists of addition, square, the remainder, and the base two exponential functions. Particularly, for every \(n>3\), \(\mathcal{E}^n\) is shown to be the closure of each of these bases augmented with an additional Ackermann-like function \(f_n\) due to R. W. Ritchie [Pac. J. Math. 15, 1027–1044 (1965; Zbl 0133.24903)].
The obtained results enable the author to simplify the proof of H. Müller’s theorem [Klassifizierungen der primitiv rekursiven Funktionen. Dissertation, Münster (1974)] stating that for every \(n\geq 2\), \(\mathcal{E}^{n+1}=\mathbf{K}_n\), where \(\mathbf{K}_n\) is P. Axt’s hierarchy [P. Axt, Z. Math. Logik Grundlagen Math. 11, 253–255 (1965; Zbl 0144.00201)].
Reviewer: Hrant B. Marandjian (Erevan)
MSC:
| 03D20 | Recursive functions and relations, subrecursive hierarchies |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
Citations:
Zbl 0063.03115; Zbl 0052.24902; Zbl 0199.02502; Zbl 0483.03025; Zbl 0133.24903; Zbl 0144.00201Online Encyclopedia of Integer Sequences:
Exponent of highest power of 2 dividing n, a.k.a. the binary carry sequence, the ruler sequence, or the 2-adic valuation of n.References:
| [1] | Axt, Z. Math. Logik Grundlagen Math. 11 pp 253– (1965) |
| [2] | Computability, Complexity, Logic. North-Holl and Publ. Comp., Amsterdam 1989. |
| [3] | Elementary Number Theory. Allyn and Bacon, Boston 1980. |
| [4] | Grzegorczyk, Rozprawy Matematyczne 4 (1953) |
| [5] | A basis for the Kalmár elementary functions. In: Number Theory and Applications, North-Holl and Publ. Comp., Amsterdam 1989, pp. 435 - 444. |
| [6] | and , Exponential diophantine representation of recursively enumerable sets. In: Proceedings of the Herbr and Symposium, Logic Colloquium ’81, North-Holl and Publ. Comp., Amsterdam 1982, pp. 159 - 177. |
| [7] | Kalmár, Matematikai es Fizikai Lapok 50 pp 1– (1943) |
| [8] | Kummer, J. Reine Angew. Math. 44 pp 93– (1852) · ERAM 044.1198cj · doi:10.1515/crll.1852.44.93 |
| [9] | Marchenkov, Mat. Zametki 27 pp 321– (1980) |
| [10] | Math. Notes 27 pp 161– (1980) · Zbl 0483.03025 · doi:10.1007/BF01140159 |
| [11] | Marchenkov, Banach Center Publications 25 pp 119– (1989) |
| [12] | Matijasevič, A. Steklova (LOMI) Akademii Nauk SSSR 67 pp 167– (1977) |
| [13] | J. Soviet Math. 16 pp 874– (1981) |
| [14] | Algorithmic unsolvability of exponential diophantine equations in three unknowns. In: Issledovaniya po Teorii Algorifmov i Matematičeskoi Logike, Nauka, Moscow (1979), pp. 69 - 78 (in Russian); |
| [15] | Sel. Math. Sov. 3 pp 223– (1983) |
| [16] | Hilbert’s Tenth Problem. Cambridge Univ. Press, Cambridge 1993. · Zbl 0913.03015 |
| [17] | Mentrasti, Rendiconti di Matematica, Ser. VI, 9 pp 37– (1976) |
| [18] | Müller, Recursive Functions Theory: Newsletters 5 pp 14– (1973) |
| [19] | Klassifizierungen der primitiv rekursiven Funktionen. Dissertation, Münster 1974. |
| [20] | Parsons, Z. Math. Logik Grundlagen Math. 14 pp 357– (1968) |
| [21] | Ritchie, Pacif. J. Math. 15 pp 1027– (1965) · Zbl 0133.24903 · doi:10.2140/pjm.1965.15.1027 |
| [22] | Rödding, Z. Math. Logik Grundlagen Math. 10 pp 315– (1964) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
