A maximal sequence of classes transformable by primitive recursion in a given class
A. P. Beltiukov
Abstract:
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.
UDC:
51.01:518.5