Вычислимость и проблема остановки: что машина никогда не решит

Что значит «вычислить»?

Алан Тьюринг в 1936 году, параллельно с Гёделем и независимо, доказал другой фундаментальный предел: существуют задачи, которые принципиально невычислимы — ни одна машина (и, вероятно, ни один алгоритм) не сможет их решить.

«Проблема остановки» (Halting Problem): можно ли написать программу, которая для любой другой программы и входных данных определяет, остановится ли эта программа (даст результат) или зациклится навсегда?

Тьюринг доказал: нет. Предположим, такая программа H(p, x) существует. Тогда можно построить программу D, которая: берёт программу p, запускает H(p, p), и если H говорит «остановится» — зацикливается, если «зациклится» — останавливается. Что делает H(D, D)? Противоречие неизбежно.

Класс невычислимых проблем

Проблема остановки — лишь первая из огромного класса невычислимых задач. «Десятая проблема Гильберта»: определить, имеет ли диофантово уравнение целочисленное решение. Юрий Матиясевич (1970) доказал: невычислима. «Проблема соответствия Поста»: невычислима. Многие «практические» задачи верификации программ — невычислимы.

Класс сложности P и NP: за это предлагается миллион долларов. Задачи класса P решаются за полиномиальное время. Задачи класса NP — решение можно проверить за полиномиальное время, но неизвестно, можно ли найти за полиномиальное. Если P=NP — большинство криптографии нужно переделывать.

Это не только теория: задачи расписания, оптимизации логистики, проверки программного обеспечения — всё это NP-полные задачи, требующие эвристик и приближённых решений, потому что точное решение вычислительно недостижимо.

Вопрос для размышления: Есть задачи, которые принципиально неразрешимы никаким алгоритмом. Какие «неразрешимые» задачи существуют в вашей профессии — ситуации, в которых нет алгоритма, только суждение?