Abstract:
In the paper the decidability of the boundedness problem for lossy counter Minsky machines is investigated. It is proved, that for Minsky machines with three counters the boundedness is not decidable for any lossiness relation on the set of machine configurations. It is introduced the notion of reset one-register machines, which can simulate two-counter machines with the reset lossiness relation. It is proved, that the boundedness is decidable for reset one-register machines (and, hence, for reset two-counter machines).
Fulltext:
PDF file (344 kB)