§ 35. Алгоритмически неразрешимые задачи

Определения и обозначения

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

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

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

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

Как это устроено

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

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

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

Чтобы доказать неразрешимость другой задачи, используют сведение. Представим, что для новой задачи найден решатель, и преобразуем вход известной неразрешимой задачи так, чтобы ответ решателя сообщал ответ на исходный вопрос. Тогда решатель новой задачи позволил бы решить и известную задачу, что невозможно. Следовательно, предположение о решателе новой задачи было ошибочным. При сведении нужно обосновать, что преобразование действительно сохраняет связь между ответами.

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

Разрешимые и неразрешимые задачи

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

Разбор задач

Задача 1. Для программы с единственной командой «вывести 1» определить, завершится ли она на заданном входе. Здесь программа не содержит цикла или условия, которое могло бы изменить ход выполнения. Нужно рассмотреть именно данный текст программы, а не пытаться решить проблему остановки для всех возможных программ.

1. Запускаем программу на заданных исходных данных: команда выводит число 1.
2. После выполнения единственной команды следующих инструкций нет, поэтому работа программы заканчивается.
3. Проверяем, не зависит ли этот ход от значения входа: команда не использует входные данные и не содержит ветвления.

Ответ: программа завершится на любом допустимом входе. Вывод получен прямым анализом конкретной программы, а не универсальной проверкой остановки.

Задача 2. Определить, остановится ли программа, которая увеличивает счётчик, пока тот не достигнет заданного конечного числа. Предположим, что счётчик начинает с нуля, а конечное число — натуральное. Условие остановки достижимо, потому что при каждом повторении значение счётчика увеличивается на единицу и не уменьшается.

1. Обозначим конечное значение через N. После k шагов счётчик равен k, поскольку изначально он равен нулю и каждый раз увеличивается на единицу.
2. Когда k достигнет N, счётчик станет равен заданному значению, и проверка условия завершит цикл.
3. Значит, программа выполнит не более N повторений, после чего остановится.

Ответ: при этих условиях программа завершится за конечное число шагов. Если начальное значение или условие цикла заданы иначе, их нужно отдельно учесть: вывод относится к указанному варианту.

Задача 3. Предположить, что существует алгоритм, который для любой программы и любого входа определяет, завершится ли выполнение, и показать противоречие. Обозначим предполагаемый проверяющий алгоритм через H: он получает описание программы и вход, затем сообщает прогноз «остановится» или «не остановится». Построим программу D, которая использует ответ H, чтобы поступить ему наперекор.

1. Если H предсказывает, что D на своём описании остановится, D запускает бесконечный цикл.
2. Если H предсказывает, что D на своём описании не остановится, D сразу завершает работу.
3. Запускаем D на её собственном описании. При первом прогнозе она не останавливается, при втором — останавливается.
4. В обоих случаях результат противоречит прогнозу H, хотя H по предположению всегда отвечает правильно.

Ответ: такого универсального проверяющего алгоритма не существует, поэтому проблема остановки алгоритмически неразрешима. Противоречие возникло из-за предположения о безошибочном решателе.

Типичные ошибки

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

Ошибка: объявлять задачу неразрешимой, потому что не удалось найти алгоритм. Неудача поиска показывает лишь, что решение пока не найдено, а не что его не существует. Для вывода о неразрешимости требуется доказательство, например противоречие или корректное сведение. Проверьте себя: приведён ли аргумент, исключающий любой возможный общий решатель?

Ошибка: путать отсутствие общего алгоритма с невозможностью решить конкретный пример. Её допускают, перенося общее утверждение на каждый отдельный вход. Между тем простой случай может иметь очевидный ответ при прямом просмотре кода. Проверьте себя: утверждается ли невозможность решить именно этот пример или только невозможность универсального способа?

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

Связь с другими темами

Для изучения темы нужны понятия алгоритма, программы, входных данных и завершения вычислений. Чтобы разобраться в доказательстве проблемы остановки, полезно уметь прослеживать выполнение программы и понимать условие цикла. Противоречие строится методом доказательства от противного: временное предположение приводит к невозможному результату. Наконец, понятие неразрешимости помогает оценивать принципиальные ограничения программ и вычислительных систем, а не только их скорость и объём памяти.

Что запомнить

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