1

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

1
  • Пожалуйста, исправьте вопрос, чтобы он отражал конкретную проблему с достаточным количеством деталей для возможности дать адекватный ответ. 27 апр 2022 в 12:54

1 ответ 1

0

Невозможно уверенно во всех случаях определять что машина Поста зациклилась из-за проблемы остановки, которая, как известно, алгоритмически не разрешима. Хотя сама проблема сформулирована для машины Тьюринга, она также верна и для машины Поста.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.