2.6. Возможные формальные возражения против & 133

т. е. мы имеем полное право включить "опыт" (или способы его порождения) в перечень операций, составляющих следующий алгоритм (т.е., собственно, в At (q, n)). Действуя таким образом, мы опять-таки получаем единичный алгоритм (At (q, n)), который зависит алгоритмически от всех трех параметров: t, q, п. На его основе можно построить алгоритм А*, столь же мощный, что и весь ряд At (q, n), однако зависящий только от двух натуральных чисел: q и п. Для получения такого A* (q, n) нам, как и прежде, необходимо лишь выполнить первые десять шагов алгоритма А0 (q, n) и запомнить результат; затем первые десять шагов алгоритма (q, n) и вторые десять шагов алгоритма (q, n), запоминая получаемые результаты; затем первые десять шагов алгоритма (q, n). вторые десять шагов алгоритма (q, n), третьи десять шагов алгоритма АО (q, n) и т.д., запоминая получаемые на каждом шаге вычисления результаты. В конечном итоге, сразу после завершения любого из составляющих алгоритм вычислений завершается выполнение и всей процедуры в целом. Замена процедуры А процедурой никак не влияет на ход рассуждений, посредством которых мы пришли к выводу .

Q3. Не был ли я излишне категоричен, утверждая, что в тех случаях, когда уже можно определенно утверждать, что данное вычисление Cq (n) и вправду завершается, алгоритм А все равно должен выполняться бесконечно? Допусти мы, что А в таких случаях также завершается, все наше рассуждение оказалось бы ложным. В конце концов, общеизвестно, что присущая людям способность к интуитивному пониманию позволяет им порой делать заключение о возможности завершения того или иного вычисления, однако я, судя по всему, здесь этой способностью пренебрег. Не слишком ли много искусственных ограничений?

Вовсе нет. Предполагается, что наше рассуждение применимо лишь к тому пониманию, которое позволяет заключить, что вычисление не завершается, но никак не к тому пониманию, благодаря которому мы приходим к противоположному выводу. Гипотетический алгоритм А вовсе не обязан достигать "успешного завершения", обнаружив что то или иное вычисление завершается. Не в этом заключается его смысл.

134 Глава 2

Если вас такое положение дел не устраивает, попробуйте представить алгоритм А следующим образом: пусть А объединяет в себе оба вида понимания, но в том случае, когда выясняется, что вычисление Cq (n) действительно завершается, алгоритм А искусственно зацикливается (т. е. выполняет какую-то операцию снова и снова, бесконечное количество раз). Разумеется, на самом деле математики работают иначе, однако дело не в этом. Наше рассуждение построено как reductio ad absurdum , т. е. начав с допущения, что для установления математической истины используются заведомо обоснованные алгоритмы, мы в итоге приходим к противоположному выводу. Такое доказательство не требует, чтобы гипотетическим алгоритмом непременно оказался какой-то конкретный алгоритм А, мы вполне можем заменить его на другой алгоритм, построенный на основе А, - как, например, в только что упомянутом случае.

Этот комментарий применим и к любому другому возражению вида: "А что если алгоритм А завершится по какой-либо совершенно посторонней причине и не даст нам доказательства того, что вычисление Cq (n) не завершается?". Если нам вдруг придется иметь дело с алгоритмом "А", который ведет себя подобным образом, то мы просто применим представленное в § 2.5 обоснование к немного другому А - к такому, который зацикливается всякий раз, когда исходный "Л" завершается по любой из упомянутых посторонних причин.

Q4. Судя по всему, каждое вычисление Са в предложенной мною последовательности является вполне определенным, тогда как при любом прямом переборе (численном или алфавитном) компьютерных программ ситуация, конечно же, была бы иной?

В самом деле, было бы весьма затруднительно однозначно гарантировать, что каждому натуральному числу q в нашей последовательности действительно соответствует некое рабочее вычисление . Например, описанная в НРК последовательность машин Тьюринга этому условию, конечно же, не удовлетворяет; см. НРК, с. 54. При определенных значениях q машину Тьюринга Тд можно назвать "фиктивной" по одной из четы-

4Приведение к абсурду (лат.), доказательство от противного. - Прим. перев.