Boundedness problems for Minsky counter machines
Egor V. Kuzmin, Valery A. Sokolov, Dmitry Ju. Chalyy · Programming and Computer Software · 2010
In the paper, the decidability of boundedness problems for counter Minsky machines is studied. It is proved that, for Minsky machines with two counters, the boundedness problem is partially decidable, and the total boundedness problem is not even partially decidable. On the other hand, for the one-counter Minsky machines, the above problems are decidable for time polynomially depending on the total number of local states of the counter machine.