Как и ранее, мы рассматриваем некий обоснованный алгоритм A( q, n), завершение выполнения которого равносильно доказательству того, что вычисление C q( n) не завершается. Несмотря на то, что, в соответствии с ограничением (I), рассмотрению подлежат только значения q, не превышающие Q, и только значения n, не превышающие N, мы, говоря об «обоснованности», в действительности имеем в виду, что алгоритм Aдолжен быть обоснованным для всехзначений qи n, независимо от их величины. (Таким образом, можно видеть, что правила, реализуемые в алгоритме A, являются точными математическими правилами, в отличие от правил приближенных, работающих только в силу того или иного практического ограничения, налагаемого на «реально осуществимые» вычисления.) Более того, утверждая, что «вычисление C q( n) не завершается», мы имеем в виду, что это вычисление действительноне завершается, а не то, что это вычисление просто-напросто оказывается слишком громоздким для того, чтобы его мог выполнить наш компьютер или человек, как предусматривает ограничение (II).
Вспомним, что утверждение (H)гласит:
Если завершается вычисление A( q, n), то вычисление C q( n) не завершается.
Принимая во внимание ограничение (II), можно было бы предположить, что алгоритм А оказывается не слишком эффективен при установлении факта незавершаемости очередного вычисления, поскольку сам он состоит из большего количества шагов, чем способен выполнить компьютер или человек. Однако, как выясняется, для нашего доказательства этот факт не имеет никакого значения. Мы намерены отыскать некое вычисление A( k, k), которое не завершается вообще. Для нас абсолютно неважно, что в некоторых других случаях, когда вычисление A действительнозавершается, мы не можем об этом узнать, так как не в состоянии дождаться этого самого завершения.
Далее, как и в равенстве (J), мы вводим натуральное число к, при котором вычисление A( n, n) совпадает с вычислением C k( n) для всех n:
A( n, n) = C k( n).
Следует, впрочем, рассмотреть еще предусматриваемую ограничением (I) возможность того, что упомянутое число kокажется больше Q. В случае какого-нибудь невообразимо сложного вычисления Aтакая ситуация вполне возможна, однако только при условии, что это А уже начинает приближаться к верхней границе допустимой сложности (в смысле количества двоичных знаков в его описании в формате машины Тьюринга), с которой может работать наш компьютер или человек. Это обусловлено тем, что вычисление, получающее значение kиз описания вычисления A(например, в формате машины Тьюринга), — вещь достаточно простая и может быть задана в явном виде (как уже было показано в комментарии к Q6).
Вообще говоря, для того чтобы поставить в тупик алгоритм A, нам необходимо лишь вычисление C k( k) — подставляя в (Н)равенство n= k, получаем утверждение (L):
Если завершается вычисление A( k, k), то вычисление C k( k) не завершается.
Поскольку 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окажется столь колоссально сложным, что одно лишь его описание вплотную приблизится к доступному воображению человека пределу сложности, а сравнительно малое увеличение количества составляющих его знаков даст в результате вычисление, превосходящее всякое человеческое понимание. Что бы мы о подобной возможности ни думали, я все же считаю, что любой столь впечатляющий набор реализуемых в нашем гипотетическом алгоритме А вычислительных правил окажется, вне всякого сомнения, настолько сложным, что мы не в состоянии будем знатьнаверняка, является ли он обоснованным, даже если нам будут точно известны все эти правила по отдельности. Таким образом, наше прежнее заключение остается в силе: при установлении математических истин мы неприменяем познаваемо обоснованныенаборы алгоритмических правил.
Не помешает несколько более подробно остановиться на сравнительно незначительном увеличении сложности, сопровождающем переход от Aк C k( k). Помимо прочего, это существенно поможет нам в нашем дальнейшем исследовании (в §§3.19и 3.20). В Приложении А предложено явное описание вычисления C k( k) в виде предписаний для машины Тьюринга, рассмотренных в НРК ( глава 2). Согласно этим предписаниям, под обозначением T mпонимается « m-я машина Тьюринга». Для большего удобства и упрощения рассуждений здесь мы также будем пользоваться этим обозначением вместо « C m», в частности, для определения степени сложностивычислительной процедуры или отдельного вычисления. В соответствии с вышесказанным, определим степень сложности μмашины Тьюринга T mкак количество знаков в двоичном представлении числа m(см. НРК, с. 39); при этом степень сложности некоторого вычисления T m( n) определяется как большее из двух чисел μ и ν, где ν— количество двоичных знаков в представлении числа n. Рассмотрим далее приведенное в Приложении Аявное предписание для составления вычисления C k( k) на основании алгоритма A, заданного в упомянутых спецификациях машины Тьюринга. Полагая степень сложности Aравной α, находим, что степень сложности явного вычисления C k( k) не превышает числа α + 210 log 2( α+ 336) — а это число, в свою очередь, оказывается лишь очень ненамного больше собственно α, да и то только тогда, когда число а очень велико.
В вышеприведенных общих рассуждениях имеется один потенциально спорный момент. В самом деле, какой смысл рассматривать вычисления, слишком сложные даже для того, чтобы просто их записать, или те, что, будучи записанными, возможно, потребуют на свое действительное выполнение промежуток времени, гораздо больший предполагаемого возраста нашей Вселенной, даже при условии, что каждый шаг такого вычисления будет производиться за самую малую долю секунды, какая еще допускает протекание каких бы то ни было физических процессов? Упомянутое выше вычисление — то, результатом которого является последовательность из 2 2 65536единиц и которое завершается лишь послевыполнения этой задачи, — представляет собой как раз такой пример; при этом позицию математика, позволяющего себе утверждать, что данное вычисление является незавершающимся, можно охарактеризовать как крайне нетрадиционную. Однако в математике существуют и некоторые другие точки зрения, пусть и не до такойстепени нетрадиционные, — но все же решительно презирающие всяческие условности, — согласно которым известная доля здорового скептицизма в отношении вопроса об абсолютной математической истинности идеализированных математических утверждений отнюдь не помешает. На некоторые из них, безусловно, стоит хотя бы мельком взглянуть.