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

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

Ограничения конечного характера могут быть обусловлены либо тем, что (i) описание конкретного рассматриваемого вычисления оказывается слишком громоздким (т. е. число n в Сп или пара чисел q, n в Cq (n) оказываются слишком велики для того, чтобы их мог описать человек или реально существующий компьютер), либо тем, что (ii) при внешней простоте описания вычисление, тем не менее, требует для своего выполнения чрезмерно много времени, в результате чего может показаться, что оно не завершается вовсе, хотя теоретически данное вычисление должно в конечном счете завершиться. На деле же, как мы вскоре убедимся, выясняется, что из этих двух условий сколько-нибудь существенное влияние на наши рассуждения оказывает только (i), да и оно не так уж и велико. Незначительность фактора (ii), быть может, покажется вам удивительной. Существует множество относительно простых вычислений, которые в конечном счете завершаются, однако точки их завершения путем прямого вычисления не способен достичь ни один потенциально возможный компьютер. Рассмотрим, например, следующую задачу: "распечатать последовательность из единиц, после чего остановиться". (В §3.26 будут предложены еще несколько подобных примеров, гораздо более интересных с математической точки зрения.) Вопрос о завершаемости того или иного вычисления не следует решать путем прямого вычисления: этот метод зачастую оказывается крайне неэффективным.

Для того чтобы выяснить, каким образом ограничения (i) или (ii) могут повлиять на наши гёделевские рассуждения, пройдемся

142 Глава 2

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

где предполагается, что число Q задает наиболее громоздкое вычисление, какое способен выполнить наш компьютер или человек. В случае с человеком вышеприведенное утверждение можно счесть несколько туманным. Впрочем, в настоящий момент нас не особенно заботит точное определение числа Q. (Вопрос о туманности утверждений, касающихся человеческих способностей, будет рассмотрен ниже, в комментарии к возражению Q13 в § 2.10.) Кроме того, можно предположить, что, попытавшись применить упомянутые вычисления к какому-то конкретному натуральному числу п, мы обнаружим, что значение п ограничено некоторой фиксированной величиной N, поскольку наш компьютер (или человек) оказывается не способен работать с числами, превышающими N. (Строго говоря, следует учесть и возможность того, что число N не является фиксированным, но зависит от того или иного конкретного вычисления Cq, т.е. N может зависеть от . Однако этот факт не влияет на наши рассуждения сколько-нибудь существенным образом.)

Как и ранее, мы рассматриваем некий обоснованный алгоритм А (д, п), завершение выполнения которого равносильно доказательству того, что вычисление не завершается. Несмотря на то, что, в соответствии с ограничением (i), рассмотрению подлежат только значения , не превышающие Q, и только значения п, не превышающие N, мы, говоря об "обоснованности", в действительности имеем в виду, что алгоритм А должен быть обоснованным для всех значений q и п, независимо от их величины. (Таким образом, можно видеть, что правила, реализуемые в алгоритме А, являются точными математическими правилами, в отличие от правил приближенных, работающих только в силу того или иного практического ограничения, налагаемого на "реально осуществимые" вычисления.) Более того, утверждая, что "вычисление Cq (п) не завершается", мы имеем в виду, что это вычисление действительно не завершается, а не то, что это вычисление просто-напросто оказывается слишком громоздким для того, чтобы его мог выполнить наш компьютер или человек, как предусматривает ограничение