18-10-2023
В теории вычислимости проблема остановки — это проблема разрешимости, которая может неформально быть поставлена в виде:
Алан Тьюринг доказал в 1936 году, что не существует общего алгоритма для решения проблемы остановки. Другими словами, проблема остановки неразрешима на машине Тьюринга.
Рассмотрим множество алгоритмов, которые принимают на вход натуральное число и на выходе тоже выдают натуральное число. Выберем какой-нибудь полный по Тьюрингу язык программирования. Каждый алгоритм можно записать в виде конечной последовательности символов на этом языке. Упорядочим множество лексикографически (в словарном порядке), при этом каждый алгоритм получит свой порядковый номер. Назовем Анализатором гипотетический алгоритм, который получает на вход пару натуральных чисел , и:
Проблему остановки можно переформулировать следующим образом: существует ли Анализатор?
Теорема. Анализатор не существует.
Докажем это от противного. Допустим, Анализатор существует. Напишем алгоритм Диагонализатор, который принимает на вход число , передает пару аргументов Анализатору и возвращает результат его работы. Другими словами, Диагонализатор останавливается в том и только том случае, если не останавливается алгоритм с номером , получив на вход число . Пусть - это порядковый номер Диагонализатора в множестве . Запустим Диагонализатор, передав ему это число . Диагонализатор остановится в том и только том случае, если алгоритм с номером (то есть, он сам) не останавливается, получив на вход число (какое мы ему и передали). Из этого противоречия следует, что наше предположение неверно: Анализатор не существует, что и требовалось доказать.
Проблема остановки.