Geodesic
On the decidability of boundedness problems for counter Minsky machines
Modelirovanie i analiz informacionnyh sistem, Tome 15 (2008) no. 1, pp. 16-26

Voir la notice de l'article provenant de la source Math-Net.Ru

In the paper the decidability of boundedness problems for counter Minsky machines is investigated. It is proved, that for Minsky machines with two counters the boundedness is partial decidable, but for the total boundedness problem does not even exist a semidecision algorithm. On the other hand, for one-counter Minsky machines all these problems are polinomial (quantitatively of local machine states) decidable. 
@article{MAIS_2008_15_1_a2,
     author = {E. V. Kuzmin and D. Ju. Chalyy},
     title = {On the decidability of boundedness problems for counter {Minsky} machines},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {16--26},
     publisher = {mathdoc},
     volume = {15},
     number = {1},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2008_15_1_a2/}
}
TY  - JOUR
AU  - E. V. Kuzmin
AU  - D. Ju. Chalyy
TI  - On the decidability of boundedness problems for counter Minsky machines
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2008
SP  - 16
EP  - 26
VL  - 15
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2008_15_1_a2/
LA  - ru
ID  - MAIS_2008_15_1_a2
ER  - 
%0 Journal Article
%A E. V. Kuzmin
%A D. Ju. Chalyy
%T On the decidability of boundedness problems for counter Minsky machines
%J Modelirovanie i analiz informacionnyh sistem
%D 2008
%P 16-26
%V 15
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2008_15_1_a2/
%G ru
%F MAIS_2008_15_1_a2
E. V. Kuzmin; D. Ju. Chalyy. On the decidability of boundedness problems for counter Minsky machines. Modelirovanie i analiz informacionnyh sistem, Tome 15 (2008) no. 1, pp. 16-26. http://geodesic.mathdoc.fr/item/MAIS_2008_15_1_a2/