Проблема остановки
Проблема остановки (англ. Halting problem) — это одна из проблем в теории алгоритмов[1], которая может неформально быть поставлена в виде:
- Даны описание процедуры и её начальные входные данные. Требуется определить: завершится ли когда-либо выполнение процедуры с этими данными; либо, что процедура всё время будет работать без остановки.
Алан Тьюринг доказал в 1936 году, что проблема остановки неразрешима на машине Тьюринга. Другими словами, не существует общего алгоритма решения этой проблемы.[2]
Проблема остановки занимает центральное место в теории вычислимости, поскольку представляет собой первый пример задачи, которую невозможно решить алгоритмическим путём.
В терминах функций проблему можно доступно описать следующим образом:
- Для любой функции F(G, start_state) которая может определять останавливается ли другая функция, всегда можно написать такую функцию G(start_state), при передаче которой в F, результат выполнения будет противоположен тому, который предсказывает F.
Для многих других задач[каких?] можно доказать их алгоритмическую неразрешимость, попытавшись свести их к проблеме остановки. Это делается по схеме "от противного": пусть есть некая задача, для которой требуется установить её неразрешимость. Тогда предположим, что она разрешима, и попытаемся, используя этот факт, написать алгоритм решения проблемы остановки для этой задачи. Если это удастся, то мы придем к противоречию, ведь известно, что не существует алгоритма решения проблемы остановки. А значит, предположение было неверным и исходная задача также неразрешима.
Доказательство
Рассмотрим множество алгоритмов, которые принимают на вход натуральное число и на выходе тоже выдают натуральное число. Выберем какой-нибудь полный по Тьюрингу язык программирования. Каждый алгоритм можно записать в виде конечной последовательности символов на этом языке. Упорядочим множество (это возможно, поскольку оно является множеством конечных последовательностей элементов конечного множества и потому счётно), при этом каждый алгоритм получит свой порядковый номер. Назовем Анализатором гипотетический алгоритм, который получает на вход пару натуральных чисел , и:
- останавливается и возвращает 1, если алгоритм с номером не останавливается, получив на вход
- не останавливается в противном случае (если алгоритм с номером останавливается, получив на вход ).
Проблему остановки можно переформулировать следующим образом: существует ли Анализатор?
Теорема. Анализатор не существует.
Докажем это от противного. Допустим, Анализатор существует. Напишем алгоритм Диагонализатор, который принимает на вход число , передает пару аргументов Анализатору и возвращает результат его работы. Другими словами, Диагонализатор останавливается в том и только том случае, если не останавливается алгоритм с номером , получив на вход число . Пусть — это порядковый номер Диагонализатора в множестве . Запустим Диагонализатор, передав ему это число . Диагонализатор остановится в том и только том случае, если алгоритм с номером (то есть, он сам) не останавливается, получив на вход число (какое мы ему и передали). Из этого противоречия следует, что наше предположение неверно: Анализатор не существует, что и требовалось доказать.
См. также
- Граф потока управления может быть использован для быстрой категоризации, когда программа не имеет циклов (и поэтому останавливается), имеет тривиальные циклы (и поэтому останавливается), имеет нетривиальные циклы (неразрешимо) или входит в бесконечный цикл.
Примечания
- Н.К.Верещагин, А.Шень Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции
- 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 — doi:10.1112/PLMS/S2-42.1.230 (в этой публикации Тьюринг вводит определение машины Тьюринга, формулирует проблему зависания и показывает, что она, также как и проблема разрешения, неразрешима).
Ссылки
- c2:HaltingProblem
- Проблема зависания (англ.)