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

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

Если завершается вычисление A (q, п), то вычисление не завершается.

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

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

А(п, п) = Ck (п).

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

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

Если завершается вычисление A (k, k), то вычисление Ck (k) не завершается.

Поскольку A (k, k) совпадает с Ck (k), наше доказательство показывает, что, хотя данное конкретное вычисление С/с (k) никогда

144 Глава 2

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

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

Не помешает несколько более подробно остановиться на сравнительно незначительном увеличении сложности, сопровождающем переход от А к Ck (k). Помимо прочего, это существенно поможет нам в нашем дальнейшем исследовании (в §§3.19 и 3.20). В Приложении А (с. 193) предложено явное описание вычисления Ck (k) в виде предписаний для машины Тьюринга, рассмотренных в НРК (глава 2). Согласно этим предписаниям, под обозначением Тт понимается " -я машина Тьюринга". Для

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

большего удобства и упрощения рассуждений здесь мы также будем пользоваться этим обозначением вместо "Ст", в частности, для определения степени сложности вычислительной процедуры или отдельного вычисления. В соответствии с вышесказанным, определим степень сложности ц машины Тьюринга Тт как количество знаков в двоичном представлении числа m (см. НРК, с. 39); при этом степень сложности некоторого вычисления Тт (п) определяется как большее из двух чисел где v - количество двоичных знаков в представлении числа п. Рассмотрим далее приведенное в Приложении А явное предписание для составления вычисления на основании алгоритма А, заданного в упомянутых спецификациях машины Тьюринга. Полагая степень сложности А равной а, находим, что степень сложности явного вычисления не превышает числа а +

+ 210 Iog2 (a + 336) - а это число, в свою очередь, оказывается лишь очень ненамного больше собственно а, да и то только тогда, когда число а очень велико.

В вышеприведенных общих рассуждениях имеется один потенциально спорный момент. В самом деле, какой смысл рассматривать вычисления, слишком сложные даже для того, чтобы просто их записать, или те, что, будучи записанными, возможно, потребуют на свое действительное выполнение промежуток времени, гораздо больший предполагаемого возраста нашей Вселенной, даже при условии, что каждый шаг такого вычисления будет производиться за самую малую долю секунды, какая еще допускает протекание каких бы то ни было физических процессов? Упомянутое выше вычисление - то, результатом которого является последовательность из единиц и которое завершается лишь после выполнения этой задачи, - представляет собой как раз такой пример; при этом позицию математика, позволяющего себе утверждать, что данное вычисление является незавершающимся, можно охарактеризовать как крайне нетрадиционную. Однако в математике существуют и некоторые другие точки зрения, пусть и не до такой степени нетрадиционные, - но все же решительно презирающие всяческие условности, - согласно которым известная доля здорового скептицизма в отношении вопроса об абсолютной математической истинности идеализированных математических утверждений отнюдь не помешает. На некоторые из них, безусловно, стоит хотя бы мельком взглянуть.

146 Глава 2

Q9. Точка зрения, известная как интуиционизм, не позволяет сделать вывод о непременной завер-шаемости вычисления на определенном этапе на том лишь основании, что бесконечное продолжение этого вычисления приводит к противоречию; бытуют в математике и иные точки зрения сходного характера - например, "конструктивизм" и "фини-тизм". Не окажется ли гёделевское доказательство спорным, будучи рассмотрено с этих позиций?

В своем гёделевском доказательстве (в частности, в утверждении (М)) я использовал аргумент следующего вида: "Допущение о ложности X приводит к противоречию; следовательно, утверждение X истинно". Под "X" в данном случае следует понимать утверждение: "Вычисление не завершается". Это рассуждение относится к типу reductio ad absurdum; что же касается доказательства Гёделя в целом, то оно и в самом деле построено именно таким образом. Направление же в математике, называемое "интуиционизмом" (у истоков которого стоял голландский математик Л. Э. Я. Брауэр; см. [223] и НРК, с. 113- 116), отрицает возможность построения обоснованного доказательства на основе reductio ad absurdum. Интуиционизм возник приблизительно в 1912 году как реакция на некоторые сформировавшиеся к концу девятнадцатого - началу двадцатого века математические тенденции, суть которых сводится к следующему: математический объект можно полагать "существующим" даже в тех случаях, когда нет никакой возможности этот объект так или иначе воплотить в действительности. А надо сказать, что слишком вольное применение крайне расплывчатой концепции математического существования и впрямь приводит порой к весьма неприятным противоречиям. Самый известный пример такого противоречия связан с парадоксальным "множеством всех множеств, не являющихся членами самих себя" Бертрана Рассела. (Если множество Рассела является членом самого себя, то оно таковым не является; если же оно членом самого себя не является, то оно им, как ни странно, является! Подробнее см. §3.4 и НРК, с. 101.) Дабы противостоять общей тенденции, в рамках которой могут считаться "существующими" весьма вольно определенные математические объекты, интуиционисты полагают необоснованным математическое рассуждение, позволяющее

2.7. Некоторые математические соображения 147

делать вывод о существовании того или иного математического объекта на основании одной лишь противоречивости его несуществования. Доказательство существования объекта посредством reductio ad absurdum не дает абсолютно никаких оснований полагать, что упомянутый объект действительно можно построить.

Каким же образом запрет на применение reductio ad absurdum может повлиять на наше геделевское доказательство? Вообще говоря, совсем не может, по той простой причине, что reductio ad absurdum мы применяем, если можно так выразиться, наоборот, то есть противоречие в нашем случае выводится из допущения, что нечто существует, а не из обратного допущения. С интуиционистской точки зрения все выглядит совершенно законно: мы заключаем, что объект не существует, на том основании, что противоречие возникает как раз из допущения о существовании этого самого объекта. Предложенное мною геделевское доказательство, по сути своей, является в интуиционистском смысле абсолютно приемлемым. (См. [223], с. 492.)

Аналогичные рассуждения применимы и ко всем прочим "конструктивистским" или "финитистским" направлениям в математике, о каких мне известно. Комментарий к возражению Q8 демонстрирует, что даже та точка зрения, согласно которой последовательность натуральных чисел нельзя считать "на самом деле" бесконечной, не освобождает нас от неизбежного вывода: для установления математической истины мы таки не пользуемся познаваемо обоснованными алгоритмами.

2.7. Некоторые более глубокие математические

соображения

Для того чтобы лучше разобраться в значении гёделевского доказательства, полезно будет вспомнить, с какой, собственно, целью оно было первоначально предпринято. На рубеже веков ученые, деятельность которых была связана с фундаментальными математическими принципами, столкнулись с весьма серьезными проблемами. В конце XIX века - в значительной степени благодаря глубоко оригинальным математическим трудам Георга Кантора (с "диагональным доказательством" которого мы уже познакомились) - математики получили в распоряжение эффективные методы доказательства некоторых наиболее фунда-

148 Глава 2

ментальных своих результатов, основанные на свойствах бесконечных множеств. Однако с этими преимуществами оказались связаны и не менее фундаментальные трудности, проистекающие из чересчур вольного обращения с концепцией бесконечного множества. Особо отметим парадокс Рассела (на который я уже ссылался в комментарии к Q9, см. также § 3.4 -o Кантор о нем также упоминает), обозначивший некоторые препятствия, подстерегающие склонных к опрометчивым умозаключениям. Тем не менее, все понимали, что если вопрос о допустимости тех или иных методов рассуждения продумать с достаточной тщательностью, то можно добиться очень и очень впечатляющих математических результатов. Проблема, по всей видимости, сводилась к отысканию способа, посредством которого можно было бы в каждом конкретном случае абсолютно точно определить, была ли соблюдена при выборе метода рассуждения "достаточная тщательность".

Одной из главных фигур движения, поставившего перед собой цель достичь этой точности, был великий математик Давид Гильберт. Движение окрестили формализмом; в соответствии с его основополагающим принципом, следовало однозначно определить все допустимые методы математического рассуждения в пределах той или иной конкретной области раз и навсегда, включая и те, что связаны с понятием бесконечного множества. Такая совокупность правил и математических утверждений называется формальной системой. После того как определены правила формальной системы F, решение вопроса о корректности применения этих правил - количество которых непременно является конечным6 - сводится к элементарной механической проверке. Разумеется, если мы хотим, чтобы любой выводимый с помощью таких правил результат мог считаться действительно истинным, нам придется присвоить им всем статус вполне допустимых и об-

Представление некоторых формальных систем включает в себя бесконечное количество аксиом (они описываются через посредстьо структур, называемых "схемами аксиом"), однако, чтобы оставаться "формальной" в том смысле, какой вкладываю в это понятие я, система должна быть выразима в каком-то конечном виде - например, упомянутая система с бесконечным количеством аксиом должна порождаться конечным набором вычислительных правил. Это вполне возможно, и именно так и обстоит дело со стандартными формальными системами, которые применяются в математических доказательствах, - одной из таких систем является, например, знаменитая "формальная система Цермело- Френкеля" , описывающая традиционную теорию множеств.

2.7. Некоторые математи ческие соображения 149

основанных форм математического рассуждения. Однако некоторые из рассматриваемых правил могут подразумевать какие-либо манипуляции с бесконечными множествами, и в этом случае математическая интуиция, подсказывающая нам, какие методы рассуждения допустимы, а какие нет, может оказаться и не достойной абсолютного доверия. Сомнения в этой связи как нельзя более уместны, учитывая несоответствия, возникающие при столь вольном обращении с бесконечными множествами, что допустимым становится даже парадоксальное "множество всех множеств, не являющихся членами самих себя" Бертрана Рассела. Правила системы F не должны допускать существования "множества" Рассела, но где же, в таком случае, следует провести границу? Вообще запретить применение бесконечных множеств было бы слишком строгим ограничением (обычное евклидово пространство, например, содержит бесконечное множество точек, да и множество натуральных чисел является бесконечным); кроме того, существуют же формальные системы, абсолютно в этом смысле удовлетворительные (поскольку в их рамках не допускается, к примеру, формулировать сущности, подобные "множеству" Рассела), применяя которые можно получить большую часть необходимых математических результатов. Откуда нам знать, каким из этих формальных систем можно верить, а каким нельзя?

Рассмотрим подробнее одну такую формальную систему F; для математических утверждений, которые можно получить с помощью правил системы F, введем обозначение ИСТИННЫЕ, а для утверждений, отрицания которых выводятся из того же источника (т. е. утверждения, обратные рассматриваемым), - обозначение ЛОЖНЫЕ. Любое утверждение, которое можно сформулировать в рамках системы F, но которое не является в этом смысле ни ИСТИННЫМ, ни ЛОЖНЫМ, будем полагать НЕРАЗРЕШИМЫМ. Кто-то, возможно, сочтет, что поскольку на деле может оказаться "бессмысленным" и само понятие бесконечного множества, то, по всей видимости, нельзя абсолютно осмысленно говорить ни об истинности, ни о ложности относящихся к ним утверждений. (Это мнение применимо по крайней мере к некоторым разновидностям бесконечных множеств, если не ко всем.) Если придерживаться такой точки зрения, то нет особой разницы, какие именно утверждения о бесконечных множествах (некоторых разновидностей) оказываются истинными, а какие -

150 Глава 2

ложными, лишь бы не вышло так, что одно утверждение получится истинным и ЛОЖНЫМ одновременно, т.е. система F должна все же быть непротиворечивой. Собственно говоря, в этом и состоит суть истинного формализма, а в отношении формальной системы F первостепенно важно знать лишь следующее: (а) является ли она непротиворечивой и (Ь) является ли она полной. Система F называется полной, если любое математическое утверждение, должным образом сформулированное в рамках F, всегда оказывается либо ИСТИННЫМ, либо ЛОЖНЫМ (т. е. НЕРАЗРЕШИМЫХ утверждений система F не содержит).

Для строгого формалиста вопрос о том, является ли то или иное утверждение о бесконечных множествах действительно истинным в сколько угодно абсолютном смысле, не обязательно имеет смысл и, уж конечно же, не имеет никакого существенного отношения к процедурам формалистской математики. Таким образом, поиски абсолютной математической истины в отношении утверждений, связанных с упомянутыми бесконечными величинами, заменяются стремлением продемонстрировать непротиворечивость и полноту соответствующих формальных систем. Какие же математические правила допустимо использовать для такой демонстрации? Достойные доверия, прежде всего, причем формулировка этих правил ни в коем случае не должна основываться на сомнительных рассуждениях с привлечением слишком вольно определяемых бесконечных множеств (типа множества Рассела). Была надежда на то, что в рамках некоторых сравнительно простых и очевидно обоснованных формальных систем (например, такой достаточно элементарной системы, как арифметика Пеано) отыщутся логические процедуры, которых будет достаточно для того, чтобы доказать непротиворечивость других, более сложных, формальных систем - скажем, системы F, - непротиворечивость которых уже не столь бесспорна и в рамках которых допускаются формальные рассуждения об очень "больших" бесконечных множествах. Если принять философию формалистов, то подобное доказательство непротиворечивости для F, как минимум, даст основание для использования методов рассуждения, допустимых в рамках системы F. Затем можно доказывать математические теоремы, применяя концепцию бесконечных множеств тем или иным непротиворечивым образом, а может, удастся и вовсе избавиться от необходимости отвечать на вопрос о реальном "смысле" таких множеств. Более того, если