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

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

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

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

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

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

Для любой функции 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$ (какое мы ему и передали). Из этого противоречия следует, что наше предположение неверно: Анализатора не существует, что и требовалось доказать.

См. также

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

Примечания

↑ Н. К. Верещагин, А. Шень Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции Архивная копия от 12 ноября 2015 на Wayback Machine
↑ Turing A. On Computable Numbers, with an Application to the Entscheidungsproblem (англ.) // Proceedings of the London Mathematical Society — London Mathematical Society, 1937. — Vol. s2-42, Iss. 1. — P. 230—265. — ISSN 0024-6115; 1460-244X; 0024-6115 — doi:10.1112/PLMS/S2-42.1.230 (в этой публикации Тьюринг вводит определение машины Тьюринга, формулирует проблему зависания и показывает, что она, также как и проблема разрешения, неразрешима).

Ссылки

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

[1] Н. К. Верещагин, А. Шень Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции Архивная копия от 12 ноября 2015 на Wayback Machine

[2] Turing A. On Computable Numbers, with an Application to the Entscheidungsproblem (англ.) // Proceedings of the London Mathematical Society — London Mathematical Society, 1937. — Vol. s2-42, Iss. 1. — P. 230—265. — ISSN 0024-6115; 1460-244X; 0024-6115 — doi:10.1112/PLMS/S2-42.1.230 (в этой публикации Тьюринг вводит определение машины Тьюринга, формулирует проблему зависания и показывает, что она, также как и проблема разрешения, неразрешима).

[1]

[2]