|
Zapiski Nauchnykh Seminarov LOMI, 1977, Volume 68, Pages 3–18
(Mi znsl1996)
|
|
|
|
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.
Citation:
A. P. Beltiukov, “A maximal sequence of classes transformable by primitive recursion in a given class”, Theoretical application of methods of mathematical logic. Part II, Zap. Nauchn. Sem. LOMI, 68, "Nauka", Leningrad. Otdel., Leningrad, 1977, 3–18; J. Soviet Math., 15:1 (1981), 1–10
Linking options:
https://www.mathnet.ru/eng/znsl1996 https://www.mathnet.ru/eng/znsl/v68/p3
|
|