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

Как и ранее, мы рассматриваем некий обоснованный алгоритм A (q, n), завершение выполнения которого равносильно доказательству того, что вычисление C_q(n) не завершается. Несмотря на то, что, в соответствии с ограничением (I), рассмотрению подлежат только значения q, не превышающие Q, и только значения n, не превышающие N, мы, говоря об «обоснованности», в действительности имеем в виду, что алгоритм A должен быть обоснованным для всех значений q и n, независимо от их величины. (Таким образом, можно видеть, что правила, реализуемые в алгоритме A, являются точными математическими правилами, в отличие от правил приближенных, работающих только в силу того или иного практического ограничения, налагаемого на «реально осуществимые» вычисления.) Более того, утверждая, что «вычисление C_q(n) не завершается», мы имеем в виду, что это вычисление действительно не завершается, а не то, что это вычисление просто-напросто оказывается слишком громоздким для того, чтобы его мог выполнить наш компьютер или человек, как предусматривает ограничение (II).

Вспомним, что утверждение (H) гласит:

Принимая во внимание ограничение (II), можно было бы предположить, что алгоритм А оказывается не слишком эффективен при установлении факта незавершаемости очередного вычисления, поскольку сам он состоит из большего количества шагов, чем способен выполнить компьютер или человек. Однако, как выясняется, для нашего доказательства этот факт не имеет никакого значения. Мы намерены отыскать некое вычисление A(k, k), которое не завершается вообще. Для нас абсолютно неважно, что в некоторых других случаях, когда вычисление A действительно завершается, мы не можем об этом узнать, так как не в состоянии дождаться этого самого завершения.

Далее, как и в равенстве (J), мы вводим натуральное число к, при котором вычисление A(n, n) совпадает с вычислением C_k(n) для всех n:

Следует, впрочем, рассмотреть еще предусматриваемую ограничением (I) возможность того, что упомянутое число k окажется больше Q. В случае какого- нибудь невообразимо сложного вычисления A такая ситуация вполне возможна, однако только при условии, что это А уже начинает приближаться к верхней границе допустимой сложности (в смысле количества двоичных знаков в его описании в формате машины Тьюринга), с которой может работать наш компьютер или человек. Это обусловлено тем, что вычисление, получающее значение k из описания вычисления A (например, в формате машины Тьюринга), — вещь достаточно простая и может быть задана в явном виде (как уже было показано в комментарии к Q6).

Вообще говоря, для того чтобы поставить в тупик алгоритм A, нам необходимо лишь вычисление C_k(k) — подставляя в (Н) равенство n = k, получаем утверждение (L):

Поскольку A(k, k) совпадает с C_k(k), наше доказательство показывает, что, хотя данное конкретное вычисление C_k(k) никогда не завершается, посредством алгоритма A мы этот факт установить не в состоянии, даже если бы упомянутый алгоритм мог выполняться гораздо дольше любого предела, налагаемого на него в соответствии с ограничением (II). Вычисление C_k(k) задается только введенным ранее числом k, и, при условии, что к не превышает ни Q, ни N, это вычисление и в самом деле в состоянии выполнить наш компьютер или человек — то есть в состоянии начать. Довести его до завершения невозможно в любом случае, поскольку это вычисление просто-напросто не завершается!

А может ли число k оказаться больше Q или N? Такое возможно лишь в том случае, когда для описания A требуется так много знаков, что даже совсем небольшое увеличение их количества выводит задачу за пределы возможностей нашего компьютера или человека. При этом, поскольку мы знаем об обоснованности алгоритма A, мы знаем и о том, что рассматриваемое вычисление C_k(k) не завершается, даже если реальное выполнение этого вычисления представляет для нас проблему. Соображение (I), однако, предполагает и возможность того, что вычисление A окажется столь колоссально сложным, что одно лишь его описание вплотную приблизится к доступному воображению человека пределу сложности, а сравнительно малое увеличение количества составляющих его знаков даст в результате вычисление, превосходящее всякое человеческое понимание. Что бы мы о подобной возможности ни думали, я все же считаю, что любой столь впечатляющий набор реализуемых в нашем гипотетическом алгоритме А вычислительных правил окажется, вне всякого сомнения, настолько сложным, что мы не в состоянии будем знать наверняка, является ли он обоснованным, даже если нам будут точно известны все эти