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!
|
| _version_ | 1849338732463783936 |
|---|---|
| author | E. V. Kuzmin D. Ju. Chalyy |
| author_facet | E. V. Kuzmin D. Ju. Chalyy |
| author_sort | E. V. Kuzmin |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-eef25e44424b4157b9788b6a8f64b61d |
| institution | Kabale University |
| issn | 1818-1015 2313-5417 |
| language | English |
| publishDate | 2008-03-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj-art-eef25e44424b4157b9788b6a8f64b61d2025-08-20T03:44:18ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172008-03-011511626711On the decidability of boundedness problems for counter Minsky machinesE. V. Kuzmin0D. Ju. Chalyy1Ярославский государственный университетЯрославский государственный университет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.https://www.mais-journal.ru/jour/article/view/970 |
| spellingShingle | E. V. Kuzmin D. Ju. Chalyy On the decidability of boundedness problems for counter Minsky machines Моделирование и анализ информационных систем |
| title | On the decidability of boundedness problems for counter Minsky machines |
| title_full | On the decidability of boundedness problems for counter Minsky machines |
| title_fullStr | On the decidability of boundedness problems for counter Minsky machines |
| title_full_unstemmed | On the decidability of boundedness problems for counter Minsky machines |
| title_short | On the decidability of boundedness problems for counter Minsky machines |
| title_sort | on the decidability of boundedness problems for counter minsky machines |
| url | https://www.mais-journal.ru/jour/article/view/970 |
| work_keys_str_mv | AT evkuzmin onthedecidabilityofboundednessproblemsforcounterminskymachines AT djuchalyy onthedecidabilityofboundednessproblemsforcounterminskymachines |