Текст книги "Тени разума. В поисках науки о сознании"

Автор книги: Роджер Пенроуз

сообщить о нарушении

Текущая страница: 11 (всего у книги 49 страниц)

А может ли число  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 ₂( α+ 336) – а это число, в свою очередь, оказывается лишь очень ненамного больше собственно α, да и то только тогда, когда число а очень велико.

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

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

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

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

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

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

Для того чтобы лучше разобраться в значении гёделевского доказательства, полезно будет вспомнить, с какой, собственно, целью оно было первоначально предпринято. На рубеже веков ученые, деятельность которых была связана с фундаментальными математическими принципами, столкнулись с весьма серьезными проблемами. В конце XIX века – в значительной степени благодаря глубоко оригинальным математическим трудам Георга Кантора (с «диагональным доказательством» которого мы уже познакомились) – математики получили в распоряжение эффективные методы доказательства некоторых наиболее фундаментальных своих результатов, основанные на свойствах  бесконечных множеств. Однако с этими преимуществами оказались связаны и не менее фундаментальные трудности, проистекающие из чересчур вольного обращения с концепцией бесконечного множества. Особо отметим парадокс Рассела (на который я уже ссылался в комментарии к Q9, см. также §3.4– Кантор о нем также упоминает), обозначивший некоторые препятствия, подстерегающие склонных к опрометчивым умозаключениям. Тем не менее, все понимали, что если вопрос о допустимости тех или иных методов рассуждения продумать с достаточной тщательностью, то можно добиться очень и очень впечатляющих математических результатов. Проблема, по всей видимости, сводилась к отысканию способа, посредством которого можно было бы в каждом конкретном случае абсолютно точноопределить, была ли соблюдена при выборе метода рассуждения «достаточная тщательность».

Одной из главных фигур движения, поставившего перед собой цель достичь этой точности, был великий математик Давид Гильберт. Движение окрестили формализмом; в соответствии с его основополагающим принципом, следовало однозначно определить все допустимые методы математического рассуждения в пределах той или иной конкретной области раз и навсегда, включая и те, что связаны с понятием бесконечного множества. Такая совокупность правил и математических утверждений называется формальной системой. После того как определены правила формальной системы F, решение вопроса о корректности применения этих правил – количество которых непременно является конечным [14]14
  Представление некоторых формальных систем включает в себя бесконечное количество аксиом (они описываются через посредство структур, называемых «схемами аксиом»), однако, чтобы оставаться «формальной» в том смысле, какой вкладываю в это понятие я, система должна быть выразима в каком-то конечном виде – например, упомянутая система с бесконечным количеством аксиом должна порождаться конечным набором вычислительных правил. Это вполне возможно, и именно так и обстоит дело со стандартными формальными системами, которые применяются в математических доказательствах, – одной из таких систем является, например, знаменитая «формальная система Цермело—Френкеля» ZF, описывающая традиционную теорию множеств.


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

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

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

Однако в 1930 году (публикация состоялась в 1931) Гёдель взорвал свою «бомбу», раз и навсегда показав, что идеал формалистов принципиально недостижим. Он продемонстрировал, что не может существовать формальной системы F, которая была бы одновременно и непротиворечивой (в некоем «сильном» смысле, который мы рассмотрим в следующем разделе), и полной, – при условии, что Fсчитается достаточно мощной, чтобы сочетать в себе формулировки утверждений обычной арифметики и стандартную логику. Таким образом, теорема Гёделя справедлива для таких систем F, в рамках которых арифметические утверждения типа теоремы Лагранжа и гипотезы Гольдбаха (см. §2.3) формулируются как утверждения математические.

В дальнейшем мы будем рассматривать только те формальные системы, которые являются достаточно обширными, чтобы содержать в себе необходимые для действительной формулировки теоремы Гёделя арифметические операции (а также, в случае нужды, и операции какой угодно машины Тьюринга; см. ниже). Говоря о какой-либо формальной системе F, я обычно буду  подразумевать, что она действительно достаточно обширна в этом смысле. Это допущение не отразится на наших рассуждениях сколько-нибудь существенным образом. (Тем не менее, рассматривая формальные системы в таком контексте, я, для пущей ясности, буду иногда снабжать их эпитетом «достаточно обширная» или иным подобным.)

2.8. Условие ω-непротиворечивости

Наиболее известная форма теоремы Гёделя гласит, что формальная система F (достаточно обширная) не может быть одновременно полной и непротиворечивой. Это не совсем та знаменитая «теорема о неполноте», которую Гёдель первоначально представил на конференции в Кенигсберге (см. §§2.1и 2.7), а ее несколько более сильный вариант, который был позднее получен американским логиком Дж. Баркли Россером (1936). По своей сути, первоначальный вариант теоремы Гёделя оказывается эквивалентен утверждению, что система Fне может быть одновременно полной и ω– непротиворечивой. Условие же ω-непротиворечивости несколько строже, нежели условие непротиворечивости обыкновенной. Для объяснения его смысла нам потребуется ввести некоторые новые обозначения. В систему обозначений формальной системы Fнеобходимо включить символы некоторых логических операций. Нам, в частности, потребуется символ, выражающий отрицание(«не»); можно выбрать для этого символ «~». Таким образом, если Qесть некое высказывание, формулируемое в рамках F, то последовательность символов ~ Qозначает «не Q». Нужен также символ, означающий «для всех [натуральных чисел]» и называемый квантор общности; он имеет вид «∀». Если P( n) есть некое высказывание, зависящее от натурального числа  n(т.е.  Pпредставляет собой так называемую пропозициональную функцию), то строка символов ∀ n[ P( n)] означает «для всех натуральных чисел n высказывание P( n) справедливо». Например, если высказывание P( n) имеет вид «число  nможно выразить в виде суммы квадратов трех чисел», то запись ∀ n[ P( n)] означает «любое натуральное число является суммой квадратов трех чисел», – что, вообще говоря, ложно (хотя, если мы заменим «трех» на «четырех», то это же утверждение станет истинным). Такие символы можно записывать в самых различных сочетаниях; в частности, строка символов

~ ∀ n[ P( n)]

выражает отрицание того, что высказывание P( n) справедливо для всех натуральных чисел n.

Условие же ω-непротиворечивости гласит, что если высказывание ~ ∀ n[ P( n)] можно доказать с помощью методов формальной системы F, то это еще неозначает, что в рамках этой самой системы непременно доказуемы всеутверждения

P(0), P(1), P(2), P(3), P(4), ….

Отсюда следует, что если формальная система Fне является ω-непротиворечивой, мы оказываемся в аномальной ситуации, когда для некоторого  Pоказывается доказуемой истинность всех высказываний P(0), P(1), P(2), P(3), P(4), …; и  одновременнос этим можно доказать и то, что невсе эти высказывания истинны! Безусловно, ни одна заслуживающая доверия формальная система подобного безобразия допустить не может. Поэтому если система Fявляется обоснованной, то она непременно будет и ω-непротиворечивой.

В дальнейшем утверждения «формальная система F является непротиворечивой» и «формальная система Fявляется ω-непротиворечивой» я буду обозначать, соответственно, символами « G( F)» и «Ω( F)». В сущности (если полагать систему F достаточно обширной), сами утверждения G( F) и Ω( F) формулируются как операции этой системы. Согласно знаменитой теореме Гёделя о неполноте, утверждение Ω( F) не является теоремойсистемы F(т.е. его нельзя доказать с помощью процедур, допустимых в рамках системы F); не является теоремой и утверждение Ω( F) – если, разумеется, система F действительно непротиворечива. Несколько более строгий вариант теоремы Гёделя, сформулированный позднее Россером, гласит, что если система Fнепротиворечива, то утверждение ~ G( F) также не является теоремой этой системы. В оставшейся части этой главы я буду формулировать свои доводы не столько исходя из утверждения Ω( F), сколько на основе более привычного нам G( F), хотя для большей части наших рассуждений в равной степени сгодится любое из них. (В некоторых наиболее явных аргументах главы 3я буду иногда обозначать через « G( F)» конкретное утверждение «вычисление C _k( k) не завершается» (см. §2.5); надеюсь, никто не сочтет это слишком большой вольностью с моей стороны.)

В большей части предлагаемых рассуждений я не стану проводить четкую границу между непротиворечивостью и ω-непротиворечивостью, однако тот вариант теоремы Гёделя, что представлен в §2.5, по сути, гласит, что если формальная система Fнепротиворечива, то она не может быть полной, так как не может включать в себя в качестве теоремы утверждение G( F). Здесь я всего этого демонстрировать не буду (интересующиеся же могут обратиться к [ 223]). Вообще говоря, для того чтобы эту форму гёделевского доказательства можно было свести к доказательству в моей формулировке, система Fдолжна содержать в себе нечто большее, нежели просто «арифметику и обыкновенную логику». Необходимо, чтобы система Fбыла обширной настолько, чтобы включать в себя действия любой машины Тьюринга. Иначе говоря, среди утверждений, корректно формулируемых с помощью символов системы F, должны присутствовать утверждения типа: «Такая-то машина Тьюринга, оперируя над натуральным числом n, дает на выходе натуральное число p». Более того, имеется теорема (см. [ 223], главы 11 и 13), согласно которой так оно само собой и получается, если, помимо обычных арифметических операций, система Fсодержит следующую операцию (так называемую μ-операцию, или операцию минимизации): «найти наименьшее натуральное число, обладающее таким-то арифметическим свойством». Вспомним, что в нашем первом вычислительном примере, (A), предложенная процедура действительно позволяла отыскать наименьшеечисло, не являющееся суммой трех квадратов. То есть, вообще говоря, право на подобные вещи за вычислительными процедурами следует сохранить. С другой стороны, именно благодаря этойих особенности мы и сталкиваемся с вычислениями, которые принципиально не завершаются, – например, вычисление (В), где мы пытаемся отыскать наименьшее число, не являющееся суммой четырехквадратов, а такого числа в природе не существует.