Определение, находится ли программа в бесконечном цикле (читай: решение проблемы остановки)

Question

Обнаруживает, находится ли детерминированная программа (т.е. конечный автомат) в бесконечном цикле, эквивалентно решению проблемы остановки?

Я придумал решение, и я не уверен, почему оно не должно работать:

• Пусть программа запустится
• Когда вы думаете, что он находится в бесконечном цикле, сделайте снимок его памяти с регулярными интервалами
• Если вы когда-либо обнаружите один и тот же снимок, программа будет в бесконечном цикле
• Пока вы не получаете один и тот же снимок дважды, либо (1) он не находится в бесконечном цикле, либо (2) вам нужно делать снимки быстрее (возможно, один раз при каждом обращении к памяти?)

Я предполагаю, что это не работает ... но почему?

Кажется, это вполне разумный способ обнаружить, находится ли программа в бесконечном цикле (например, особенно если вы храните хеши, а не саму память, хотя это не будет на 100% точно) ... что с этим не так, если что?

Answer 1

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

Но давайте рассмотрим вашу идею дальше.Вы также должны сделать снимок «скрытого» состояния: счетчик программы ЦП и другие регистры, и что вам необходимо сделать снимок перед каждой отдельной инструкцией.(Программа будет в бесконечном цикле, если снимок памяти будет таким же, и будет выполнена та же инструкция. Это не поможет, если содержимое памяти будет таким же, но будет выполнено что-то еще, чем последнийраз вы видели один и тот же снимок.)

На практике даже очень маленький компьютер имеет такое огромное количество потенциальных состояний, что вы никогда не сможете сохранить (даже хэши!) все свои снимки.Например, даже мини-компьютер, такой как древний коммодор 64 с 64 КБ ОЗУ, имеет 256 ^ 65536 потенциальных состояний (не включая 5 регистров ЦП).Потенциально столь длительные циклы отслеживания абсолютно бесполезны как во времени, так и в пространстве.

Answer 2

Решение не сработает даже в принципе.Машина Тьюринга не обязательно должна быть точно в одном и том же состоянии (с лентой в той же конфигурации), чтобы войти в бесконечный цикл.

Ваш алгоритм может работать для контекстно-зависимых языков и линейно-ограниченныхавтомат, но если вы не можете знать, сколько ленты понадобится ТМ, вы никогда не узнаете, если бы у вас был бесконечный цикл или вы собирались достичь вершины.Обратите внимание, что ваш метод будет работать на реальных компьютерах по разным причинам ... главная из них заключается в том, что ваш компьютер менее мощный, чем (большой) конечный автомат.