WikiSort.ru - Не сортированное

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

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

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

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

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

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

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

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

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

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

См. также

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

Примечания

Ссылки

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