General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Zap. Nauchn. Sem. POMI:

Personal entry:
Save password
Forgotten password?

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

This article is cited in 2 scientific papers (total in 2 papers)

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
\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
\jour J. Soviet Math.
\yr 1982
\vol 20
\issue 4
\pages 2280--2289

Linking options:

    SHARE: FaceBook Twitter Livejournal

    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  mathnet  crossref  crossref  mathscinet  zmath  elib
    2. I. V. Savitskii, “Computations on register machines with counters”, Discrete Math. Appl., 28:2 (2018), 97–111  mathnet  crossref  crossref  isi  elib
  • Записки научных семинаров ПОМИ
    Number of views:
    This page:235
    Full text:88

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2018