RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. 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.

UDC: 51.01:518.5


 English version:
Journal of Soviet Mathematics, 1981, 15:1, 1–10

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024