A maximal sequence of classes transformable by primitive recursion in a given class

A. P. Beltiukov

Zapiski Nauchnykh Seminarov POMI, Theoretical application of methods of mathematical logic. Part II, Tome 68 (1977), pp. 3-18

Résumé

Let $\mathscr E(g)$ be the closure of a set of functions $$ U_{1\leqslant k\leqslant n}\{\lambda x_1\dots x_n.x_k\}\cup\{\lambda x.0,\lambda x\lambda y.\max(x,y),\lambda x.x+1,g\} $$ with respect to composition and bounded recursion; let $\mathscr RA$ be the closure with respect to cornposition of the set of all functions obtained by a single application of primitive recursion to the functions of $\mathscr A$. Let $f$ be an increasing function with a graph from $\mathscr E^\circ$ bounded below by the function $\lambda x.x+1$. Let, for any k and sufficiently large $x$, $$ f(x+1)>f(x)+k. $$ A sequence of functions $\alpha_i$ is constructed such that for any $i$ $$ \mathscr E(\alpha_i)\subsetneqq\mathscr E(\alpha_{i+1}),\quad U^\infty_{j=1}\mathscr E(\alpha_j)\subsetneqq\mathscr E(f),\quad \mathscr E(f)=\mathscr{RE}(\alpha_i); $$ moreover, for any nondecreasing function $g$ with graph from $\mathscr E^\circ$ bounded below by the function $\lambda x.x+1$, if $U^\infty_{j=0}\mathscr E(\alpha_j)\subseteq\mathscr E(g)$, then $\mathscr E(f)\subsetneqq\mathscr E(g)$. If $f(x)=2^x$ for all $x$, then the classes $\mathscr E(\alpha_i)$ appear naturally on scrutiny of the memory bank used in calculating the functions on Turing machines.