Plain bases for classes of primitive recursive functions
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 [\textit{L. Kalmár}, Mat. Fiz. Lapok 50, 1--23 (1943; Zbl 0063.03115)] as well as for A. Grzegorczyk's hierarchy \(\mathcal{E}^n\) [\textit{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 \textit{D. Rödding} [Z. Math. Logik Grundlagen Math. 10, 315--330 (1964; Zbl 0199.02502)] and then by \textit{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 \textit{R. W. Ritchie} [Pac. J. Math. 15, 1027--1044 (1965; Zbl 0133.24903)]. The obtained results enable the author to simplify the proof of \textit{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 [\textit{P. Axt}, Z. Math. Logik Grundlagen Math. 11, 253--255 (1965; Zbl 0144.00201)].
- Super-exponentials nonprimitive recursive, but rudimentary
- Elementary functions and loop programs
- Arithmetization of register machines with counters
- Generating some classes of recursive functions by superpositions of simple arithmetic functions
- On the class of Skolem elementary functions
- scientific article; zbMATH DE number 3841837 (Why is no real title available?)
- A classification of the one-argument primitive recursive functions
- On the Algebraic Structure of Primitive Recursive Functions
- scientific article; zbMATH DE number 4145887 (Why is no real title available?)
- scientific article; zbMATH DE number 4108744 (Why is no real title available?)
- scientific article; zbMATH DE number 23014 (Why is no real title available?)
- scientific article; zbMATH DE number 3557765 (Why is no real title available?)
- scientific article; zbMATH DE number 3557782 (Why is no real title available?)
- On Closed Classes of Primitive Recursive Functions, II
- New substitution bases for complexity classes
- An example of a simple quasi-universal function in the class ε 2 of the Grzegorczyk hierarchy
- scientific article; zbMATH DE number 3245446 (Why is no real title available?)
- Operation of bound prefix concatenation and finite superposition bases
- Any function I can actually write down is measurable, right?
- Arithmetic terms for sums of multinomial coefficients
- Computational considerations on the representation of number-theoretic functions by arithmetic terms
- On the representation of C-recursive integer sequences by arithmetic terms
- An arithmetic term for the factorial function
- On other two representations of the C-recursive integer sequences by terms in modular arithmetic
- A minimal substitution basis for the Kalmár elementary functions
- Arithmetic-term representations for the greatest common divisor
This page was built for publication: Plain bases for classes of primitive recursive functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2776813)
