On the decidability of boundedness problems for counter Minsky machines
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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2008-03-01
|
| Series: | Моделирование и анализ информационных систем |
| Online Access: | https://www.mais-journal.ru/jour/article/view/970 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 1818-1015 2313-5417 |