Столкнулся с проблемой проверки алгоритма на зацикленность. Помимо завершения успешной работы и достижения невыполнимой команды возможен случай когда алгоритм зацикливается (картека уходит бесконечно вбок или двигается по кругу). Сама реализация машины работает в режиме реального времени, команды срабатывают через определнный интервал времени. Хочу узнать какой способ проверки наиболее подходящий? На уме два варианта - находить последовательность повторяющихся команд и проверять что команды проходятся по тем же ячейкам. Либо же создать второй экземпляр машины без таймера, который запускается параллельно. И через определённое время, пропорциональное количеству команд, выдавать тревожный звоночек если работа машины до сих пор не закончена. Может есть более простой подход, о котором я на догадываюсь?
1 ответ
Невозможно уверенно во всех случаях определять что машина Поста зациклилась из-за проблемы остановки, которая, как известно, алгоритмически не разрешима. Хотя сама проблема сформулирована для машины Тьюринга, она также верна и для машины Поста.