Decidability of boundedness problems for Minsky counter machines
Egor V. Kuzmin, Dmitry Ju. Chalyy · Automatic Control and Computer Sciences · 2010
The decidability of boundedness problems for Minksy counter machines is studied. It is proved that, for Minsky machines with two counters, the boundedness problem is partially decidable and the problem of the total boundedness is not even partially decidable. For one-counter Minsky machines, these problems are decidable during a time polynomially depending on the total number of local states of the counter machine.