Boundedness problem for lossy counter machines
Egor V. Kuzmin · Automatic Control and Computer Sciences · 2010
The decidability of the boundedness problem for lossy Minsky counter machines is studied. It is proved that, for Minsky machines with three counters, the boundedness problem is undecidable for any lossiness on the set of machine configurations. The notion of counter reset one-register machines is introduced; these machines are capable of simulating two-counter machines with a reset lossiness relation. It is proved that the boundedness problem for reset one-register machines (and, therefore, reset two-counter machines) is decidable.