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

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

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

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

[править] Набросок доказательства

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

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

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

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

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

[править] См. также

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

[править] Ссылки

Алан Тьюринг On computable numbers, with an application to the Entscheidungsproblem // Proceedings of the London Mathematical Society, Series 2. в 1936. в Т. 42. в С. 230265. (в этой публикации Тьюринг вводит определение машины Тьюринга, формулирует проблему зависания и показывает, что она (также как и проблема разрешения) неразрешима).
Wiki:HaltingProblem
Проблема зависания (англ.)

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

[править] Набросок доказательства

[править] См. также

[править] Ссылки

Личные инструменты

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация

Участие

Печать/экспорт

Инструменты

На других языках