Q5. Не является ли мое рассуждение лишь демонстрацией неприменимости некоей частной алгоритмической процедуры ( A) к выполнению вычисления C q( n)? И каким образом оно показывает, что я справлюсь с задачей лучше, чем какая бы то ни было процедура A?
Оно и в самом делевполне однозначно показывает, что мы справляемся с такого рода задачами гораздо лучше любого алгоритма. Поэтому, собственно, я и воспользовался в своем рассуждении приемом reductio ad absurdum. Пожалуй, в данном случае уместно будет привести аналогию. Читателям, вероятно, известно о евклидовом доказательстве невозможности отыскать наибольшее простое число, также основанном на reductio ad absurdum. Доказательство Евклида выглядит следующим образом. Допустим обратное: такое наибольшее простое число нам известно; назовем его p. Теперь рассмотрим число N, которое представляет собой сумму произведения всех простых чисел вплоть до pи единицы:
N = 2 × 3 × 5 × … × p + 1.
Число N, безусловно, больше p, однако оно не делится ни на одно из простых чисел 2, 3, 5, ..., p(поскольку при делении получаем единицу в остатке), откуда следует, что Nлибо и есть искомое наибольшее простое число, либо оно является составным, и тогда его можно разделить на простое число, большее p. И в том, и в другом случае мы находим простое число, большее p, что противоречит исходному допущению, заключавшемуся в том, что pесть наибольшее простое число. Следовательно, наибольшее простое число отыскать нельзя.
Такое рассуждение, основываясь на reductio ad absurdum, не просто показывает, что требуемому условию не соответствует некое частное простое число р, поскольку можно отыскать число больше него; оно показывает, что наибольшего простого числа просто не может существовать в природе. Аналогично, представленное выше доказательство Гёделя—Тьюринга не просто показывает, что нам не подходит тот или иной частный алгоритм А, оно демонстрирует, что в природе не существует алгоритма (познаваемо обоснованного), который был бы эквивалентен способности человека к интуитивному пониманию, которую мы применяем для установления факта незавершаемости тех или иных вычислений.
Q6. Можно составить программу, выполняя которую, компьютер в точности повторит все этапы представленного мною доказательства. Не означает ли это, что компьютер оказывается в состоянии самостоятельно прийти к любому заключению, к какому пришел бы я сам?
Отыскание конкретного вычисления C k( k) при заданном алгоритме А, безусловно, представляет собой вычислительный процесс. Более того, это можно достаточно явно показать [13]. Означает ли это, что предположительно неалгоритмическая математическая интуиция — интуиция, благодаря которой мы определяем, что вычисление C k( k) никогда не завершается, — на деле является все же алгоритмической?
Думаю, данное суждение следует рассмотреть более подробно, поскольку оно представляет собой одно из наиболее распространенных недоразумений, связанных с гёделевским доказательством. Следует особо уяснить, что оно не сводит на нетничего из сказанного ранее. Хотя процедуру отыскания вычисления C k( k) с помощью алгоритма Aможно представить в виде вычисления, это вычисление не входит в перечень процедур, содержащихся в A. И не может входить, поскольку самостоятельно алгоритм Aне способен установить истинность C k( k), тогда как новое вычисление (вкупе с A), судя по всему, вполне на это способно. Таким образом, несмотря на то, что с помощью нового вычисления действительно можно отыскать вычисление C k( k), членом клуба «официальных установителей истины» оно не является.
Изложим все это несколько иначе. Вообразите себе управляемого компьютером робота, способного устанавливать математические истины с помощью алгоритмических процедур, содержащихся в A. Для большей наглядности я буду пользоваться антропоморфной терминологией и говорить, что робот «знает» те математические истины (в данном случае — связанные с установлением факта незавершаемости вычислений), которые он может вывести, применяя алгоритм A. Однако если наш робот «знает» лишь A, то он никак не сможет«узнать», что вычисление C k( k) не завершается, даже если процедура отыскания C k( k) с помощью Aявляется целиком и полностью алгоритмической. Мы, разумеется, могли бы сообщитьроботу о том, что вычисление C k( k) и в самом деле не завершается (воспользовавшись для установления этого факта собственными пониманием и интуицией), однако, если робот примет это утверждение на «веру», ему придется изменить свои собственные правила, присоединив полученную новую истину к тем, что он уже «знает». Мы можем пойти еще дальше и каким-либо способом сообщить нашему роботу о том, что для получения новых истин на основании старых ему, помимо прочего, необходимо «знать» и общую вычислительную процедуру отыскания C k( k) посредством алгоритма A. К запасу «знаний» робота можно добавить все, что является вполне определенным и вычислительным по своей природе. Однако в результате у нас появляется новыйалгоритм « A», и доказательство Гёделя следует применять уже к нему, а не к старому A. Иначе говоря, везде вместо старого Aнам следовало бы использовать новый « A», поскольку менять алгоритм посреди доказательства есть не что иное, как жульничество. Таким образом, как мы видим, изъян возражения Q6очень похож на рассмотренный выше изъян Q5. В нашем reductio ad absurdumмы полагаем, что алгоритм А (под которым понимается некая познаваемая и обоснованная процедура для установления факта незавершаемости вычислений) в действительности представляет собой всю совокупностьизвестных математикам подобных процедур, из чего и следует противоречие. Попытку введения еще одной вычислительной процедуры для установления истины — процедуры, не содержащейся в A, — послетого как мы договорились, что Aпредставляет собой всю их совокупность, я расцениваю как жульничество.
Беда нашего злосчастного робота в том, что, не обладая каким бы то ни было пониманиемгёделевской процедуры, он не располагает ни одним надежным и независимым способом установления истины — истину ему сообщаем мы. (Эта проблема, вообще говоря, не имеет никакого отношения к вычислительным аспектам доказательства Гёделя.) Для того чтобы достичь чего-то большего, ему, как и всем нам, необходимо понимание смысла операций, которые ему велено выполнять. Если такого понимания нет, то он вполне может «знать» (ошибочно), что вычисление C k( k) завершается, а вовсе не наоборот. Заключение (ошибочное) «вычисление C k( k) завершается» выводится точно так же алгоритмически, как и заключение (правильное) «вычисление C k( k) не завершается». Таким образом, дело вовсе не в алгоритмическом характере этих операций, а в том, что для различения между алгоритмами, приводящими к истинным заключениям, и теми, что приводят к заключениям ложным, наш робот нуждается в способности выносить достоверные суждения об истинности. Далее, на данной стадии рассуждения, мы все еще допускаем возможность того, что процесс «понимания» представляет собой некую разновидность алгоритмической деятельности, которая не содержится ни в одной из точно заданных и «заведомо» обоснованных процедур типа A. Например, понимание может осуществляться посредством выполнения какого-то необоснованного или непознаваемого алгоритма. В дальнейшем (см. главу 3) я попробую убедить читателя в том, что в действительности понимание вообще не является алгоритмической деятельностью. На настоящий же момент нас интересуют всего лишь строгие следствия из доказательства Гёделя—Тьюринга, а на них возможность получения вычисления C k( k) из процедуры A вычислительным путем никоим образом не влияет.
