Geodesic
Computations on register machines with counters
Diskretnaya Matematika, Tome 29 (2017) no. 1, pp. 95-113 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Computational capabilities of register machines with counters is investigated. It is shown that the class of functions that are strictly computable on register machines with counters agrees with that of total recursive functions.
Keywords: register machines with counters. 
@article{DM_2017_29_1_a7,
     author = {I. V. Savitskii},
     title = {Computations on register machines with counters},
     journal = {Diskretnaya Matematika},
     pages = {95--113},
     year = {2017},
     volume = {29},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2017_29_1_a7/}
}
TY  - JOUR
AU  - I. V. Savitskii
TI  - Computations on register machines with counters
JO  - Diskretnaya Matematika
PY  - 2017
SP  - 95
EP  - 113
VL  - 29
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DM_2017_29_1_a7/
LA  - ru
ID  - DM_2017_29_1_a7
ER  - 
%0 Journal Article
%A I. V. Savitskii
%T Computations on register machines with counters
%J Diskretnaya Matematika
%D 2017
%P 95-113
%V 29
%N 1
%U http://geodesic.mathdoc.fr/item/DM_2017_29_1_a7/
%G ru
%F DM_2017_29_1_a7
I. V. Savitskii. Computations on register machines with counters. Diskretnaya Matematika, Tome 29 (2017) no. 1, pp. 95-113. http://geodesic.mathdoc.fr/item/DM_2017_29_1_a7/

[1] Bel'tyukov A. P., “An iterative description of the class $\mathcal{E}^1$ of Grzegorczyk's hierarchy”, J. Soviet Math., 14:5 (1980), 1429–1436 | DOI | MR | Zbl | Zbl

[2] Bel'tyukov A. P., “A machine description and the hierarchy of initial Grzegorczyk classes”, J. Soviet Math., 20:4 (1982), 2280–2289 | DOI | MR | Zbl | Zbl

[3] Marchenkov S. S., Elementarnye rekursivnye funktsii, MTsNMO, M., 2003, 112 pp.

[4] Minsky M. L., Finite and infinite machines, Prentice-Hall, 1967, 317 pp. ; Minskii M., Vychisleniya i avtomaty, per. s angl., Mir, M., 1971, 368 pp. | MR | Zbl | MR

[5] Fischer P. C., Meyer A. R., Rosenberg A. L., “Counter machines and counter languages”, Math. Syst. Theory, 4:3 (1968), 265–283 | DOI | MR

[6] Greibach S. A., “Remarks on the complexity of nondeterministic counter languages”, Theor. Comput. Sci., 1 (1976), 269–288 | DOI | MR | Zbl

[7] Ibarra O. H., “Reversal-bounded multicounter machines and their decision problems”, J. Ass. Comput. Mach., 25:1 (1978), 116–133 | DOI | MR | Zbl