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

Zap. Nauchn. Sem. LOMI, 1972 Volume 32, Pages 12–17 (Mi znsl2558)

The increase of the complexity of functions at an application of the multiple recursion

E. Ya. Dantsin


Abstract: The note deals with the hierarchy of classes $C_{\alpha}$, ($\alpha$ being an ordinal) constructed by Löb and Wainer ([I],[2]). If $\alpha<{\omega}$ then this hierarchy coincides with Grzegorczyk classification and $\bigcup_{\alpha<{\omega^k}}$ is the class of all $k$-recursive functions ($k=1,2,\dots$).
The complexity and the rate of growth of functions from $C_{\alpha}$ are characterized by the ordinal $\alpha$. In the present paper it is shown that if $\varphi$ is obtained from functions of $C_{\alpha}$, by one applicatien of the $k$-recursion, then the complexity of $\varphi$ is characterized by the ordinal $\alpha+\omega^{k-1}$, namely $\varphi$ is primitive recursive in $C_{\alpha+\omega^{k-1}}$. In particular for the primitive recursion ($k=1$) $\varphi\in C_{\alpha+1}$.



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024