О разрешимости проблем ограниченности для счетчиковых машин Минского

Исследуется разрешимость проблем ограниченности для счетчиковых машин Минского. Доказывается, что для машин Минского с двумя счетчиками проблема ограниченности лишь частично разрешима, а проблема тотальной ограниченности не является даже частично разрешимой. Для односчетчиковых машин Минского указанные проблемы разрешимы за время, полиномиально зависящее от общего количества локальных состояний счетчиковой машины.