Проблема остановки

Проблема остановки (англ. Halting problem) — одна из проблем в теории алгоритмов, которая может неформально быть поставлена в виде:

Даны описание процедуры и её начальные входные данные. Требуется определить: завершится ли когда-либо выполнение процедуры с этими данными; либо, что процедура всё время будет работать без остановки.

Алан Тьюринг доказал в 1936 году, что проблема остановки неразрешима на машине Тьюринга. Другими словами, не существует общего алгоритма решения этой проблемы.

Проблема остановки занимает центральное место в теории вычислимости, поскольку представляет собой первый пример задачи, которую невозможно решить алгоритмическим путём.

В терминах функций проблему можно доступно описать следующим образом:

Для любой функции F(G, start_state), которая может определять, останавливается ли другая функция, всегда можно написать такую функцию G(start_state), при передаче которой в F результат выполнения будет противоположен тому, который предсказывает F.

Для многих других задач^{[каких?]} можно доказать их алгоритмическую неразрешимость, попытавшись свести их к проблеме остановки. Это делается по схеме "от противного": пусть есть некая задача, для которой требуется установить её неразрешимость. Тогда, предположим, что она разрешима, и попытаемся, используя этот факт, написать алгоритм решения проблемы остановки. Если это удастся, то мы придем к противоречию, ведь известно, что не существует алгоритма решения проблемы остановки. А значит, предположение было неверным и исходная задача также неразрешима.

Доказательство

Рассмотрим множество $S$ алгоритмов, которые принимают на вход натуральное число и на выходе тоже выдают натуральное число. Выберем какой-нибудь полный по Тьюрингу язык программирования. Каждый алгоритм можно записать в виде конечной последовательности символов на этом языке. Упорядочим множество $S$ по алфавиту. При этом каждый алгоритм получит свой порядковый номер; более того существует алгоритм, который по номеру элемента $S$ восстанавливает его код в выбранном языке программирования. Назовем Анализатором гипотетический алгоритм, который получает на вход пару натуральных чисел $(N,X)$, и:

• останавливается и возвращает 1, если алгоритм с номером $N$ не останавливается, получив на вход $X$
• не останавливается в противном случае (если алгоритм с номером $N$ останавливается, получив на вход $X$).

Проблему остановки можно переформулировать следующим образом: существует ли Анализатор?

Теорема. Анализатора не существует.

Докажем это от противного. Допустим, Анализатор существует. Напишем алгоритм Диагонализатор, который принимает на вход число $N$, передает пару аргументов $(N,N)$ Анализатору и возвращает результат его работы. Другими словами, Диагонализатор останавливается в том и только том случае, если не останавливается алгоритм с номером $N$, получив на вход число $N$. Пусть $K$ — это порядковый номер Диагонализатора в множестве $S$. Запустим Диагонализатор, передав ему это число $K$. Диагонализатор остановится в том и только том случае, если алгоритм с номером $K$ (то есть, он сам) не останавливается, получив на вход число $K$ (какое мы ему и передали). Из этого противоречия следует, что наше предположение неверно: Анализатора не существует, что и требовалось доказать.

См. также

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

Ссылки

• c2:HaltingProblem
• Проблема зависания (англ.)