Проблема зависания

В теории вычислимости проблема остановки — это проблема разрешимости, которая может неформально быть поставлена в виде:

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

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

Набросок доказательства

Все конечные последовательности символов из некоторого алфавита можно пронумеровать. Выпишем сначала все символы из алфавита, потом все последовательности из двух символов, потом - из трех и т.д. Любая конечная последовательность когда-нибудь встретится в этом списке. Позиция, на которой она встретится - это и будет ее номер. Рассмотрим алгоритмы, которые принимают на вход натуральное число и на выходе тоже выдают натуральное число. Алгоритм может рано или поздно остановиться и выдать результат, или же не остановиться никогда (например, из-за бесконечного цикла или бесконечной рекурсии). Каждый алгоритм можно записать в виде конечной последовательности символов на некотором языке программирования, поэтому у каждого алгоритма есть номер. Все пары натуральных чисел тоже можно пронумеровать. Представим, что все пары выписаны в виде таблицы: на первой строке находятся все пары, первый элемент которых равен 1, на второй строке находятся все пары, первый элемент которых равен 2 и т.д. Мы можем обойти эту таблицу по диагоналям, выписывая все пары в ряд: (1,1),(1,2),(2,1),(1,3),(2,2),(3,1) и т.д. Позиция, на которой встретится некоторая пара - это и будет ее номер. И наоборот, каждому номеру соответствует какая-то пара чисел. Назовем Анализатором гипотетический алгоритм, который получает на вход номер пары натуральных чисел, интерпретируемых как номер алгоритма N и его входные данные X, и:

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

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

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

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

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

См. также

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

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

Ссылки

• Алан Тьюринг, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, 42 (1936), pp 230—265. online version Это эпохальная публикация где Тьюринг вводит определение машины Тьюринга, формулирует проблему зависания и показывает, что она (также как и en:Entscheidungsproblem) неразрешима.
• Wiki:HaltingProblem