Проблема остановки машины Тьюринга: почему она неразрешима

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

Ниже - сборщик разбора: выберите, что нужно понять про проблему остановки, и получите развёрнутый пошаговый ответ.

Как формулируется проблема остановки

Формально задача ставится так. Дана машина Тьюринга $M$ и входное слово $w$. Требуется построить алгоритм $H(M, w)$, который для любой пары на вход выдаёт «да», если $M$ на $w$ когда-нибудь остановится, и «нет», если $M$ на $w$ работает бесконечно. Важно, что $H$ должен сам всегда останавливаться и давать ответ за конечное время - иначе он не алгоритм, а просто запуск самой машины.

Здесь и кроется ловушка. Запустить $M$ на $w$ и подождать недостаточно: если машина остановится, мы это увидим, но если она зациклилась, ждать придётся вечно, и мы никогда не узнаем, что ответ - «нет». Нужен анализатор, который выносит вердикт без бесконечного ожидания. Теорема Тьюринга говорит, что такого анализатора нет.

Доказательство от противного

Допустим, искомый алгоритм $H$ существует. Значит, есть машина Тьюринга, которая по описанию $\langle M \rangle$ и входу $w$ за конечное время выдаёт:

$$H(\langle M \rangle, w) = \begin{cases} 1, & \text{если } M \text{ на } w \text{ останавливается},\\ 0, & \text{если } M \text{ на } w \text{ зацикливается}. \end{cases}$$

Из $H$ построим новую машину $D$ - «диагональную». Она принимает на вход описание одной машины $\langle M \rangle$ и внутри вызывает $H(\langle M \rangle, \langle M \rangle)$, то есть спрашивает: остановится ли $M$, если подать ей на вход её собственное описание. Дальше $D$ делает прямо противоположное полученному ответу:

$$\begin{aligned} D(\langle M \rangle) &= \text{зациклиться}, & \text{если } H(\langle M \rangle, \langle M \rangle) = 1,\\ D(\langle M \rangle) &= \text{остановиться}, & \text{если } H(\langle M \rangle, \langle M \rangle) = 0. \end{aligned}$$

Машина $D$ совершенно законна: раз $H$ - алгоритм, то $D$ тоже можно собрать. И теперь зададим роковой вопрос.

Рассчитать для своей задачи

Самоприменение: запускаем D на самой себе

Подадим машине $D$ на вход её собственное описание $\langle D \rangle$. Рассмотрим оба возможных исхода.

Если $D$ на входе $\langle D \rangle$ останавливается, то по определению $D$ это произошло только когда $H(\langle D \rangle, \langle D \rangle) = 0$, то есть когда анализатор утверждает, что $D$ зацикливается. Противоречие: $D$ остановилась, хотя $H$ сказал, что она зациклится.

Если $D$ на входе $\langle D \rangle$ зацикливается, то по определению $D$ это случилось только когда $H(\langle D \rangle, \langle D \rangle) = 1$, то есть когда анализатор утверждает, что $D$ остановится. Снова противоречие: $D$ работает вечно, хотя $H$ предсказал остановку.

Оба варианта невозможны одновременно с корректной работой $H$. Единственное допущение, которое мы сделали, - существование $H$. Значит, оно ложно: алгоритм, решающий проблему остановки, существовать не может. Этот приём - заставить объект отрицать собственное предсказание о себе - называется диагональным аргументом и восходит к канторовской технике из доказательства теоремы Кантора - Бернштейна и несчётности континуума.

Почему нельзя просто запустить и подождать

Интуиция подсказывает: запусти программу и смотри. Этот метод называется полуразрешимостью. Множество пар $(M, w)$, на которых машина останавливается, рекурсивно перечислимо: если остановка произойдёт, симуляция её обнаружит за конечное число шагов. Но дополнение - множество зацикливающихся пар - уже не перечислимо: для бесконечного цикла нет момента, в который симуляция выдаст «нет».

Именно асимметрия между «да» и «нет» делает задачу неразрешимой. Разрешимость требует, чтобы алгоритм останавливался на обоих ответах. Проблема остановки полуразрешима, но не разрешима - это эталонный пример различия двух понятий.

Чтобы почувствовать разницу, удобно представить «универсальный таймаут». Можно предложить: запусти $M$ на $w$ ровно на миллион шагов; если не остановилась - считаем, что зациклилась. Такой алгоритм всегда даёт ответ, но он неверен: существуют машины, которые честно останавливаются на шаге миллион плюс один. Любую конечную границу шагов легко обмануть машиной, которая работает чуть дольше. Поэтому «подождать подольше» не превращает полуразрешимую задачу в разрешимую - нужна именно гарантия конечного и при этом корректного ответа на каждой паре.

Рассчитать для своей задачи

Связь с тезисом Чёрча - Тьюринга

Теорема доказана для машин Тьюринга, но её сила гораздо шире. Согласно тезису Чёрча - Тьюринга, любая интуитивно вычислимая функция вычислима машиной Тьюринга. Поэтому неразрешимость проблемы остановки означает: её не решит никакая модель вычислений - ни лямбда-исчисление, ни рекурсивные функции, ни реальный компьютер с любым объёмом памяти.

Это фундаментальная граница. Существование универсальной машины Тьюринга, способной эмулировать любую другую, как раз и позволяет машине $D$ запускать анализатор над произвольным кодом - без универсальности конструкция самоприменения не собралась бы.

Практический вывод из тезиса важен для программиста: барьер не зависит от языка и железа. Переписать гипотетический анализатор на более мощном языке, дать ему квантовый компьютер или бесконечную память бесполезно - все эти модели сводятся к машине Тьюринга и наследуют ровно ту же границу. Неразрешимость проблемы остановки - это утверждение не о технологии, а о пределах самого понятия «механически вычислить».

Следствия: что ещё неразрешимо

От проблемы остановки неразрешимость распространяется на множество задач через приём сведения: если задачу $A$ можно свести к задаче $B$, и $A$ неразрешима, то и $B$ неразрешима. Так доказали неразрешимость целого ряда вопросов:

• Теорема Райса: любое нетривиальное свойство функции, вычисляемой программой (например «программа печатает 0», «программа вычисляет константу»), неразрешимо.
• Проблема соответствий Поста - комбинаторная задача о подборе последовательности доминошек.
• Десятая проблема Гильберта - существование целочисленных корней у произвольного диофантова уравнения.
• Проблема эквивалентности программ - определить, вычисляют ли две программы одну и ту же функцию.

Все они «заражены» неразрешимостью именно от проблемы остановки. Логика сведения всегда одинакова: если бы существовал решатель для $B$, мы бы по правилам сведения построили из него решатель для проблемы остановки - а его нет. Поэтому решателя для $B$ тоже не существует. Проблема остановки служит «корневым» неразрешимым примером, от которого неразрешимость растекается по теории вычислимости, подобно тому как от одной невозможной точки опоры рушится вся опирающаяся на неё конструкция.

Частые ошибки

• «Проблему остановки решили современные анализаторы кода». Статические анализаторы и верификаторы работают на частных классах программ или дают приближённые ответы с «не знаю». Универсального решателя для всех программ нет и быть не может.
• Путать неразрешимость и сложность. Проблема остановки не «очень долгая» - она в принципе невычислима, это качественно иной барьер, чем NP-трудность.
• Считать, что для конкретной программы ответ непредсказуем. Для многих конкретных машин остановка очевидна. Неразрешимость - про отсутствие единого алгоритма для всех случаев, а не про каждый отдельный случай.
• Думать, что доказательство опирается на нехватку памяти или времени. Машина Тьюринга имеет бесконечную ленту; барьер чисто логический, а не ресурсный.
• Смешивать полуразрешимость с разрешимостью. Остановку можно подтвердить запуском, а вот зацикливание - нет; именно поэтому задача только полуразрешима.

FAQ

Кто и когда доказал неразрешимость проблемы остановки? Алан Тьюринг в статье 1936 года «On Computable Numbers». Независимо близкий результат о неразрешимости получил Алонзо Чёрч через лямбда-исчисление; отсюда совместное название тезиса Чёрча - Тьюринга.

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

Чем диагональный аргумент Тьюринга похож на аргумент Кантора? Оба строят объект, который по построению отличается от каждого элемента предполагаемого «полного» списка. У Кантора это число, отличающееся в каждой диагональной цифре; у Тьюринга - машина $D$, противоречащая предсказанию анализатора о ней самой.

Коротко

Проблема остановки машины Тьюринга - задача определить, завершится ли произвольная программа на данном входе. Тьюринг доказал её неразрешимость от противного: из гипотетического анализатора $H$ строится диагональная машина $D$, которая, будучи запущенной на собственном описании, обязана сделать противоположное тому, что предскажет $H$, - и приходит к противоречию. Задача остаётся полуразрешимой (остановку можно подтвердить запуском), но не разрешимой, а через сведения её неразрешимость наследуют теорема Райса, проблема Поста и десятая проблема Гильберта.