RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Zap. Nauchn. Sem. POMI: Year: Volume: Issue: Page: Find

 Zap. Nauchn. Sem. LOMI, 1979, Volume 88, Pages 30–46 (Mi znsl3100)

A machine description and a hierarchy of initial Grzegorczyk's classes

A. P. Beltiukov

Abstract: A type of abstract computing machines (stack register machines) and a computation complexity measure for these machines are described. They are naturally connected with Grzegorczyk's hierarchy. The recursive construction used in the original definition of Grzegorczyk's classes is based on algebraic, and non-machine approach. All Grzegorczyk's classes $\mathscr E_*^n$ for $n=0,1,2,3,…$ are a complexity classes for this type of machines and this measure. Complexity description of the Smullyan's rudimentary predicates class is also obtained on the basis of similar machines. Coincidence with $\mathscr E_*^0$ on the predicates of some subclasses of $\mathscr E^1$ based on bounded recursion and containing functions growing faster than the functions of $\mathscr E^0$ is proved with the aid of the machines under investigation. The same machine model is applied to prove that the class of unary functions of $\mathscr E^0$ and some similar classes have no finite bases under superposition. It is also proved that $\mathscr E_*^1=\mathscr E_*^2$ implies $\mathscr E_*=\mathscr E_*^1$.
Any stack register machine consists of
1) finite number of input registers $x_1,x_2,…,x_a$ containing input numbers;
2) finite number of stack registers $t_0,t_1,…,t_b$;
3) working register $r$;
4) zero register 0 containing 0.
Control device can execute the following instructions:
1) $r:=z$, where $z$ is $x_i,t_i,r$ or 0; the contents of $z$ are copied by this instruction to $r$, then the next instruction of the program is executed;
2) $t_i:=t_i+1$; the contents of $t_i$ are increased by this instruction by 1, the contents of $t_j$ for $j<i$ become zeroes, then the next instruction of the program is executed;
3) branching instruction: if $z_1=z_2$ then go to $L_i$ else go to $L_j$, where $z_1$, $z_2$ are $x_m$, $t_m$, $r$ or 0; the contents of the registers are not changed by this instruction; after its execution the instruction labelled by $L_i$ in the program is executed if the contents of $z_1$ and $z_2$ coincide, else the instruction labelled by $L_j$ is executed.
The program is a finite labelled by different labels $L_i$.
The last instruction $J_k$ is not a branching instruction. After its execution the machine stops. When it stops, the result of the computation can be read in $R$. A program of any stack register machine contains at most one instruction $t_i:=t_i+1$ for any $i$.
Complexity measure Space is considered, where Space $(M,W)$ is the maximum value contained in the registers $M$ while processing the input $W$. It is proved that any of Grzegorczyk's classes $\mathscr E_*^0$, $\mathscr E_*^1$, $\mathscr E_*^2$, $\mathscr E_*^{n+3}$ is a union of complexity classes for the machines with complexity bound families $\{\lambda x(x+c)\}_{c=0}^\infty$; $\{\lambda x(c\cdot x+c)\}_{c=0}^\infty$; $\{\lambda x(x^c+c)\}_{c=0}^\infty$; $\{P_{n+3}^{\langle c\rangle}\}_{c=0}^\infty$ correspondingly, where $P_3(x)=2^x$, $P_{n+4}(x)=P_{n+3}^{\langle x\rangle}(1)$, $f^{\langle x\rangle}=f\circ f\circ…\circ f$ ($x$ times), $f\circ g(x)=f(g(x))$.

Full text: PDF file (777 kB)

English version:
Journal of Soviet Mathematics, 1982, 20:4, 2280–2289

Bibliographic databases:

UDC: 510.52

Citation: A. P. Beltiukov, “A machine description and a hierarchy of initial Grzegorczyk's classes”, Studies in constructive mathematics and mathematical logic. Part VIII, Zap. Nauchn. Sem. LOMI, 88, "Nauka", Leningrad. Otdel., Leningrad, 1979, 30–46; J. Soviet Math., 20:4 (1982), 2280–2289

Citation in format AMSBIB
\Bibitem{Bel79} \by A.~P.~Beltiukov \paper A~machine description and a~hierarchy of initial Grzegorczyk's classes \inbook Studies in constructive mathematics and mathematical logic. Part~VIII \serial Zap. Nauchn. Sem. LOMI \yr 1979 \vol 88 \pages 30--46 \publ "Nauka", Leningrad. Otdel. \publaddr Leningrad \mathnet{http://mi.mathnet.ru/znsl3100} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=556217} \zmath{https://zbmath.org/?q=an:0429.03017|0493.03012} \transl \jour J. Soviet Math. \yr 1982 \vol 20 \issue 4 \pages 2280--2289 \crossref{https://doi.org/10.1007/BF01629435} 

• http://mi.mathnet.ru/eng/znsl3100
• http://mi.mathnet.ru/eng/znsl/v88/p30

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. S. S. Marchenkov, “On the complexity of the $\mathscr E^2$ Grzegorczyk class”, Discrete Math. Appl., 20:1 (2010), 61–73
2. I. V. Savitskii, “Computations on register machines with counters”, Discrete Math. Appl., 28:2 (2018), 97–111