Неразрешимость проблемы останова

Теперь мы хотим показать, что решение проблемы останова выходит за пределы возможностей машин. Мы будем исходить из того, что для решения задачи потребуется алгоритм вычисления невычислимой функции. Входами этой функции являются закодированные варианты программ на скелетном языке, а выходами — значения 0 и 1. Точнее, мы определяем функцию так, что при подаче на вход самозавершающейся программы она порождает выходное значение 1, а для программы, не завершающейся самостоятельно, она выдает 0. Для краткости мы будем называть эту функцию функцией останова.

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

Если функция останова вычислима, то (так как скелетный язык является универсальным языком программирования) должна существовать программа на скелетном языке для вычисления этой функции. Другими словами, эта программа должна останавливаться с выходом, равным 1, если ее вход — закодированный вариант самозавершающейся программы, и выдавать 0 в противном случае.

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

Предполагая, что выходная переменная программы — X (если это другая переменная, мы можем переименовать их), мы можем изменить программу, добавив в конце операторы

while X not 0 do: end;

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

В частности, если эта новая программа самозавершающаяся, и мы запустим ее с переменными, содержащими закодированное представление этой программы, то на момент, когда выполнение достигнет добавленного оператора while, значение переменной X будет равно 1. (До этого момента новая программа идентична исходной, которая выдает 1, если на вход было подано закодированное представление самозавершающейся программы.) Теперь программа навсегда войдет в цикл while-end, так как мы не предусмотрели уменьшение значения X в цикле. Однако это противоречит нашему предположению, что новая программа самозавершающаяся. Таким образом, мы можем сделать вывод, что новая программа не является самозавершающейся.

Если же новая программа не самозавершающаяся, и мы запустим ее, присвоив переменным закодированное значение программы, она достигнет добавленного оператора while со значением X, равным 0. (Это происходит потому, что операторы, предшествующие оператору while, генерируют выход программы, равный 0, если на вход подана кодировка не самозавершающейся программы.) В этом случае цикл while-end не будет выполнен, и программа остановится. Но это свойство самозавершающейся программы, поэтому мы делаем вывод, что новая программа самозавершающаяся, так же, как ранее увидели, что она не является самозавершающейся.

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

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

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

Сложность задач

В разделе 11.4 мы исследовали проблемы в терминах разрешимости. В этом разделе нас будет интересовать сложность задач (complexity of problem), то есть вопрос, существует ли практическое решение разрешимых задач. Мы узнаем, что некоторые теоретически разрешимые проблемы настолько сложны, что их невозможно решить с практической точки зрения.