Часть I. ПОЧЕМУ ДЛЯ ПОНИМАНИЯ РАЗУМА НЕОБХОДИМА НОВАЯ ФИЗИКА? Невычислимость сознательного мышления

Из коллекции сайта «РазныеРазности»

Http://hotmix.narod.ru

РОДЖЕР ПЕНРОУЗ

«Тени разума. В поисках науки о сознании.»

Часть I. ПОЧЕМУ ДЛЯ ПОНИМАНИЯ РАЗУМА НЕОБХОДИМА НОВАЯ ФИЗИКА? Невычислимость сознательного мышления

СОЗНАНИЕ И ВЫЧИСЛЕНИЕ

Разум и наука

Кое-кто склонен верить, что мы действительно способны приблизиться к научному пониманию сознания, что в этом фе­номене вообще нет ничего… В этой книге я попытаюсь обратиться к вопросу сознания с научных позиций. При… Разумеется, некоторые из приводимых мной аргументов ока­жутся не совсем просты, однако я постарался сделать свое…

Спасут ли роботы этот безумный мир?

Впрочем, нельзя забывать и о положительных достижениях нашего интеллекта. Среди них — весьма впечатляющие наука и технология. В самом деле,… Благодаря технологиям — как древним, так и современ­ным — существенно… Я практически не сомневаюсь, что в нашем технологическом (часто сплошь компьютеризованном) обществе в неявном виде…

Вычисление и сознательное мышление

Мне кажется, что можно говорить, как минимум, о четырех различных точках зрения) — или даже крайностях, — которых разумный индивид может… Всякое мышление есть вычисление; в частности, ощущение осмысленного осознания… Осознание представляет собой характерное проявление фи­зической активности мозга; хотя любую физическую актив­ность…

Физикализм и ментализм

Вычисление: нисходящие и восходящие процедуры

А что такое машина Тьюринга? По сути, это и есть матема­тически идеализированный компьютер (теоретический предше­ственник современного… Для описания деятельности машины Тьюринга нередко ис­пользуют термин… Мы говорим, что вычислительная процедура имеет нисхо­дящую организацию, если она построена в соответствии с неко­торой…

Противоречит ли точка зрения В тезису Черча—Тьюринга?

Вполне вероятно, однако, что сам Тьюринг имел в виду нечто большее: вычислительные возможности любого физиче­ского устройства должны (в идеале) быть…  

Хаос

В последние годы ученые проявляют огромный интерес к ма­тематическому феномену, известному под названием «хаос», — феномену, в рамках которого физические системы оказываются способными на якобы аномальное и непредсказуемое поведение (рис. 1.1). Образует ли феномен хаоса необходимую невычисли­мую физическую основу для такой точки зрения, как ?

Хаотические системы — это динамически развивающиеся физические системы, математические модели таких физических систем или же просто математические модели, не описываю­щие никакой реальной физической системы и интересные сами по себе; характерно то, что будущее поведение такой системы чрезвычайно сильно зависит от ее начального состояния, причем определяющими могут оказаться самые незначительные факто­ры. Хотя обыкновенные хаотические системы являются полно­стью детерминированными и вычислительными, на деле может показаться, что в их поведении ничего детерминированного нет и никогда не было. Это происходит потому, что для сколько-нибудь надежного детерминистического предсказания будущего поведения системы необходимо знать ее начальное состояние с такой точностью, которая может оказаться просто недостижимой не только для тех измерительных средств, которыми мы распола­гаем, но также и для тех, которые мы только можем вообразить.

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

С другой стороны, подобное — так называемое хаотиче­ское — поведение может иметь место и в случае очень простых систем; примером тому служат системы, состоящие из малого количества частиц. Вообразите, что от вас требуется загнать в лузу бильярдный шар Е, расположенный пятым в некоторой из­вилистой и очень растянутой цепочке шаров ; вам нужно ударить кием по шару А так, чтобы тот ударил шар В, который, в свою очередь, ударил бы шар С, который ударил бы шар D, который ударил бы шар Е, который, наконец, по­пал бы в лузу. В общем случае необходимая для этого точность значительно превышает способности любого профессионального игрока в бильярд. Если бы цепочка состояла из 20 шаров, то тогда — даже допустив, что эти шары представляют собой иде­ально упругие точные сферы — задача загнать в лузу последний шар оказалась бы не под силу и самому точному механизму из всех доступных современной технологии. Поведение последних шаров цепочки было бы, в сущности, случайным, несмотря на то, что управляющие поведением шаров ньютоновы законы матема­тически абсолютно детерминированы и, в принципе, эффективно вычислимы. Никакое вычисление не смогло бы предсказать ре­альное поведение последних шаров цепочки просто потому, что нет никакой возможности добиться достаточно точного определения реального начального положения и скорости движения кия или положений первых шаров цепочки. Более того, даже самые незначительные внешние воздействия, вроде дыхания человека в соседнем городе, могут нарушить эту точность до такой степени, которая полностью обесценит результаты любого подобного вы­числения.

Здесь необходимо пояснить, что, несмотря на столь серьез­ные трудности, встающие перед детерминистическим предска­занием, все нормальные системы, к которым применим термин «хаотические», следует относить к категории систем, которые я называю «вычислительными». Почему? Как и в других ситуаци­ях, которые мы рассмотрим позднее, для того, чтобы определить, является ли та или иная процедура вычислительной, достаточно задать себе вопрос: выполнима ли она на обычном универсальном компьютере? Очевидно, что в данном случае ответ может быть только утвердительным, по той простой причине, что математиче­ски описываемые хаотические системы и в самом деле изучаются, как правило, с помощью компьютера!

Разумеется, если мы попытаемся создать компьютерную мо­дель для подробного предсказания погоды в Европе в течение недели или же для описания последовательных столкновений расположенных вдоль некоторой кривой на достаточно большом расстоянии друг от друга двадцати бильярдных шаров после того, как по первому из них резко ударили кием, то можно почти с пол­ной определенностью утверждать, что результаты, полученные с помощью нашей модели, и близко не будут похожи на то, что произойдет в действительности. Такова природа хаотических систем. На практике бесполезно пытаться с помощью вычисле­ний предсказать реальное конечное состояние системы. Тем не менее, моделирование типичного конечного состояния вполне возможно. Предсказанная погода может и не совпасть с реаль­ной, но она абсолютно правдоподобна как погода вообще! Точно так же и предсказанный результат столкновений бильярдных ша­ров абсолютно приемлем как возможный исход, даже несмотря на то, что на самом деле шары могут повести себя совершенно не так, как предсказано вычислением, — однако и при этом их поведение остается в равной степени приемлемым. Упомянем еще об одном обстоятельстве, которое подчеркивает идеально вы­числительную природу таких операций: если запустить процесс компьютерного моделирования вторично, задав те же входные

данные, что и ранее, то результат моделирования будет точно таким же, как и в первый раз! (Здесь предполагается, что сам компьютер не ошибается; впрочем, надо признать, что современ­ные компьютеры и в самом деле крайне редко совершают при вычислениях реальные ошибки.)

Возвращаясь к искусственному интеллекту, отметим, что ни­кто пока и не пытается воспроизвести поведение какого-то кон­кретного индивидуума; нас бы прекрасно устроила модель инди­видуума вообще! В этом контексте моя позиция вовсе не пред­ставляется такой уж неразумной: хаотические системы следует безусловно относить к категории систем, которые мы называем «вычислительными». Компьютерная модель такой системы и в самом деле выглядела бы как абсолютно приемлемый «типичный случай», даже и не совпадая при этом ни с каким «реальным случаем». Если внешние проявления человеческого разума суть результаты некоей хаотической динамической эволюции (эволю­ции вычислительной в том смысле, о котором мы только что го­ворили), то это вполне согласуется с точками зрения , но никак не

Время от времени выдвигаются предположения, что, воз­можно, именно феномен хаоса — если, конечно, он действительно имеет место в деятельности мозга как физической сущности — позволяет человеческому мозгу симулировать поведение, якобы отличное от вычислительно-детерминированного функциониро­вания машины Тьюринга, хотя, как подчеркивалось выше, фор­мально его активность является целиком и полностью вычисли­тельной. К этому вопросу мне еще придется вернуться несколько позднее . Пока же достаточно уяснить лишь то, что хаотические системы относятся к категории систем, называемых мною «вычислительными» или «алгоритмическими». Вопрос же о том, можно ли смоделировать какую-нибудь из таких систем на практике, не входит в круг принципиальных вопросов, которые мы здесь рассматриваем.

Аналоговые вычисления

В случае аналоговых систем необходимо учитывать одно формальное обстоятельство: стандартные понятия вычисления и вычислимости применимы, строго… В принципе, ничто не мешает повысить точность до уровня, адекватного для… Существуют, однако, и другие подходы к проблемам вычис­лений в случае непрерывных систем; например, такие, в кото­рых…

Невычислительные процессы

А что нам известно о роли окружения? По мере развития каждого индивидуума у него или у нее формируется уникаль­ное окружение, отличное от окружения… А может быть, численное моделирование пусть даже все­го лишь правдоподобного… мозгов. Признание возможности внешней невычислимой физи­ческой активности лишает всякой силы главный аргумент про­тив…

Завтрашний день

А вот сторонники точки зрения подобным оптимизмом похвастаться не могут. Они вполне согласны с приверженцами А относительно перспектив развития… примириться с тем, что нашей планетой, в конечном итоге, будут править абсолютно бесчувственные машины! Мне…

Обладают ли компьютеры правами и несут ли ответственность?

ровать поведение человека, то человек может оказаться в весьма затруднительном… Подобного затруднения, по всей видимости, не возникнет у сторонников точки зрения (а также, возможно, ), поскольку,…

Доказательство Джона Серла

Дана некая компьютерная программа, которая демонстри­рует имитацию «понимания», отвечая на вопросы о какой-то рассказанной ей предварительно… Доказательство Серла направлено против точки зрения (согласно которой любая…

Некоторые проблемы вычислительной

Модели

Прежде чем перейти к вопросам, отражающим специфиче­ские отличия точки зрения , рассмотрим некоторые другие трудности, с которыми непременно сталкивается любая попытка объяснить феномен сознания в соответствии с точкой зрения . Согласно , для возникновения осознания необходи­мо лишь простое «выполнение» или воспроизведение надлежа­щих алгоритмов. Что же это означает в действительности? Сле­дует ли под «воспроизведением» понимать, что в соответствии с последовательными шагами алгоритма должны перемещаться с места на место некие физические материальные объекты? Пред­положим, что эти последовательные шаги записываются строка за строкой в огромную книгу. Являются ли «воспроизведени­ем» действия, посредством которых осуществляется запись или печать этих строк? Достаточно ли одного лишь статического су­ществования такой книги для осознания? А если просто водить пальцем от строчки к строчке — можно ли это считать «воспро­изведением»? Или если водить пальцем по символам, набранным шрифтом Брайля? А если проецировать страницы книги одну за другой на экран? Является ли воспроизведением простое пред­ставление последовательных шагов алгоритма? С другой сто­роны, необходимо ли, чтобы кто-нибудь проверял, на самом ли деле каждая последующая линия надлежащим образом следует из предыдущей (в соответствии с правилами рассматриваемо­го алгоритма)? Последнее предположение способно, по крайней мере, разрешить все наши сомнения, поскольку данный процесс должен, по всей видимости, обходиться без участия (сознатель­ного) каких бы то ни было ассистентов. И все же нет совершенно никакой ясности относительно того, какие именно физические действия следует считать действительными исполнителями алго­ритма осознания. Быть может, подобные действия не требуются вовсе, и можно, не противореча точке зрения , утверждать, что для возникновения «осознания» вполне достаточно одного лишь теоретического математического существования соответствую­щего алгоритма (см. § 1.17).

Как бы там ни было, можно предположить, что, даже соглас­но , далеко не всякий сложный алгоритм может обусловить возникновение осознания (ощущения осознания). Наверное, для того, чтобы можно было считать состоявшимся сколько-нибудь заметное осознание, алгоритм, судя по всему, должен обладать некоторыми особенными свойствами — такими, например, как «высокоуровневая организация», «универсальность», «самоот-носимость», «алгоритмическая простота/сложность» и тому подобными. Кроме того, донельзя скользким представляется вопрос о том, какие именно свойства алгоритма отвечают в этом случае за различные (ощущения), формирующие осознание. Например, какое конкретно вычисление вызывает ощу­щение «красного»? Какие вычисления дают ощущения «боли», «сладости», «гармоничности», «едкости» и т.д.? Сторонники время от времени предпринимают попытки разобраться в подоб­ного рода проблемах (см., например, [80]), однако пока что эти попытки выглядят весьма и весьма неубедительными.

Более того, любое четко определенное и достаточно про­стое алгоритмическое предположение (подобное всем тем, что до сих пор выдвигались в соответствующих исследованиях) об­ладает одним существенным недостатком: этот алгоритм мож­но без особых усилий реализовать на современном электронном компьютере. А между тем, согласно утверждению автора такого предположения, реализация его алгоритма неизбежно вызывает реальное ощущение того или иного Мне думается, что даже самому стойкому приверженцу точки зрения будет слож­но всерьез поверить, что такое вычисление — да и вообще любое вычисление, которое можно запустить на современном компью­тере, работа которого основывается на современных представ­лениях об ИИ, — может действительно обусловить мышление хотя бы даже и в самой зачаточной степени. Так что сторонникам подобных предположений остается, по всей видимости, уповать лишь на то, что всеми мыслительными ощущениями мы обязаны не чему иному, как банальной сложности сопровождающих де­ятельность мозга вычислений (выполняющихся в соответствии с упомянутыми предположениями).

В связи с этим возникает еще несколько проблем, которых, насколько мне известно, всерьез пока не касался никто. Если предположить, что необходимым условием сознательной мыс­лительной деятельности является, главным образом, огромная сложность «соединений», формирующих в мозге сеть из взаимо­связанных нейронов и синапсов, то придется каким-то образом примириться и с тем, что сознание свойственно не всем отделам головного мозга человека в равной степени. Когда термин «мозг» употребляют без каких-либо уточнений, вполне естественно (по крайней мере, для неспециалиста) представлять себе обширные, покрытые извилинами внешние области, образующие так назы­ваемую кору головного мозга, — состоящий из серого вещества наружный слой головного мозга. В коре головного мозга содержится приблизительно сто тысяч миллионов нейронов, что и в самом деле дает ощутимый простор для формирования структур огромной сложности, однако кора — это еще далеко не весь мозг. В задней нижней части мозга находится еще один весьма важный сгусток спутанных нейронов, известный как. моз­жечок (см. рис. 1.6). Мозжечок, судя по всему, неким критическим образом связан с процессом выработки двигательных на­выков; его действие можно наблюдать, когда человек овладевает тем или иным движением в совершенстве, т. е. когда движение перестает требовать сознательного обдумывания, как не требует обдумывания, скажем, ходьба. Сначала, когда мы еще только учимся какому-то новому навыку, нам необходимо контролиро­вать свои действия сознательно, и этот контроль, по-видимому, требует существенного участия коры головного мозга. Однако впоследствии, по мере того, как необходимые движения стано­вятся «автоматическими», управление ими постепенно переходит к мозжечку и осуществляется, по большей части, бессознательно. Учитывая, что деятельность мозжечка является, по всей видимо­сти, абсолютно бессознательной, весьма примечателен тот факт,

что количество нейронов в мозжечке может достигать полови­ны того их количества, что содержится в коре головного мозга. Более того, именно в мозжечке располагаются такие нейроны, как клетки Пуркинье (те самые, что имеют до синаптических связей, о чем я уже упоминал в ), так что общее число связей между нейронами в мозжечке может оказаться ничуть не меньше аналогичного числа в головном мозге. Если необходимым условием возникновения сознания считать одну лишь сложность нейронной сети, то неплохо было бы выяснить, почему же со­знание никак, на первый взгляд, не проявляется в деятельности мозжечка. (Несколько дополнительных замечаний на эту тему приведены в )

Разумеется, затронутые в этом разделе проблемы, с которы­ми приходится иметь дело сторонникам точки зрения , имеют свои аналоги и применительно к точкам зрения . Какой бы научной позиции вы ни придерживались, вам в конечном итоге все равно придется как-то решать вопрос о том, что же лежит в основе феномена сознания и как возникают В последних разделах второй части книги я попытаюсь наметить некоторые пути к пониманию сознания с точки зрения

Свидетельствуют ли ограниченные возможности сегодняшнего ИИ в пользу ?

Какой же должна быть мыслительная деятельность, чтобы ее невычислимость можно было явственно продемонстрировать? В качестве возможного пути к ответу… Как ни удивительно, главную неудачу современный искус­ственный интеллект… Как бы то ни было, вряд ли можно утверждать, что во всех вышеперечисленных ситуациях компьютер и впрямь понимает, что…

Доказательство на основании теоремы

Гёделя

Как можем мы быть уверены в том, что вышеописанное по­нимание не может, в сущности, быть сведено к набору вычис­лительных правил? Несколько позже (в главах 2 и 3) я приведу некоторые очень серьезные доводы в пользу того, что проявления

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

Существует, по меньшей мере, логическая возможность то­го, что обладающий сознанием мозг (или сознательный разум) может функционировать в соответствии с такими невычислитель­ными законами . Однако так ли это? Представленные в следующей главе рассуждения содержат, как мне кажет­ся, весьма четкое доказательство наличия в нашем сознатель­ном мышлении невычислительной составляющей. Основаны эти рассуждения на знаменитой и мощной теореме математической логики, сформулированной великим логиком, чехом по происхо­ждению, Куртом Гёделем. Для моих целей будет вполне доста­точно существенно упрощенного варианта этой теоремы, который не потребует от читателя слишком обширных познаний в мате­матике (что касается математики, то я также позаимствую кое-что из одной важной идеи, высказанной несколько позднее Ала­ном Тьюрингом). Любой достаточно серьезно настроенный чита­тель без труда разберется в моих рассуждениях. Доказательства гёделевского типа, да еще и примененные в подобном контек­сте, подвергаются время от времени решительным нападкам. Вследствие этого у некоторых читателей может сложиться впе­чатление, что мое основанное на теореме Гёделя доказательство было полностью опровергнуто. Должен заметить, что это дале­ко не так. За прошедшие годы действительно выдвигалось множество контраргументов. Мишенью для многих из них послу­жило одно из самых первых таких доказательств (направленное в поддержку ментализма и против физикализма), предложенное оксфордским философом Джоном Лукасом [245]. Опираясь на результаты теоремы Гёделя, Лукас доказывал, что мыслительные процессы невозможно воспроизвести вычислительными метода­ми. (Подобные соображения выдвигались и ранее; см., напри­мер, [270].) Мое доказательство, пусть и построенное на том же фундаменте, выдержано все же в несколько ином духе, нежели доказательство Лукаса; кроме того, в число моих задач не входи­ла непременная поддержка ментализма. Я думаю, что моя форму­лировка способна лучше противостоять различным критическим замечаниям, выдвинутым в свое время против доказательства Лукаса, и во многих отношениях выявить их несостоятельность. Ниже (в главах 2 и 3) мы подробно рассмотрим все контр­аргументы, которые когда-либо попадались мне на глаза. На­деюсь, что мои сопутствующие комментарии не только помогут прояснить некоторые, похоже, широко распространившиеся за­блуждения относительно смысла доказательства Гёделя, но и до­полнят, по-видимому, неудовлетворительно краткое рассмотре­ние этого вопроса, предпринятое в НРК. Я намерен показать, что большая часть этих контраргументов произрастает, в сущности, из банальных недоразумений, тогда как остальные, основанные на более или менее осмысленных и требующих детального рас­смотрения возражениях, представляют собой, в лучшем случае, не более чем возможные «лазейки» в духе взглядов при этом они не дают — в чем у нас еще будет возможность убедить­ся — сколько-нибудь правдоподобного объяснения действи­тельным последствиям наличия у нас способности «понимать», да и в любом случае эти лазейки не представляют особой ценно­сти для развития идеи ИИ. Так что тем, кто по-прежнему полага­ет, что все внешние проявления процессов сознательного мышле­ния можно адекватно воспроизвести вычислительными метода­ми, в рамках положений , я могу лишь порекомендовать повнимательнее следить за предлагаемой ниже аргументацией.

Платонизм или мистицизм?

С другой стороны, следует понимать, что наука (и, в част­ности, математика) и сама по себе являет нам мир, исполненный тайн. Чем глубже мы проникаем…

Почему именно математическое понимание?

Может показаться, что представленное в главе 2 математи­ческое доказательство, устанавливающее необходимую нам фор­му теоремы Гёделя, не имеет… Почему же в таком случае я решил рассмотреть вопрос со­знания прежде всего в… А разве не очевидно, возразят мне, что восприятие того же красного цвета никак не может быть вызвано просто…

Какое отношение имеет теорема Гёделя к «бытовым» действиям?

Что же заставляет меня утверждать, будто упомянутое осо­знание, что бы оно из себя ни представляло, должно быть невы­числимым — иначе говоря, таким,… Возможно, кто-то усмотрит здесь некий налет мистики, од­нако в… Я утверждаю, что точно так же мы не пользуемся вычис­лительными правилами при визуализации движений деревянного…

Мысленная визуализация и виртуальная

Реальность

Здесь уместно провести аналогию с феноменом, именуе­мым «виртуальной реальностью». Феномен этот, согласно рас­пространенному мнению, имеет самое… Можно также предположить, что внутри мозга функциони­рует нечто вроде «аналогового компьютера», в котором…

Является ли невычислимым математическое

Воображение?

Дело в том, что «предметом» рассматриваемой выше «ви­зуализации» является «визуальное» в буквальном смысле этого слова, т. е. мысленные образы,… Переходя от общего к частному, я утверждаю, что наше по­нимание, например,… Следует отметить, что всякий раз, как мы получаем дей­ствительно эффективную цифровую (или аналоговую) компью­терную…

Примечания

1. См., в частности, [161], [262], [266].

2. Моравек [266] основывает свои доводы в пользу такого срока на том, какая, по его мнению, часть коры головного мозга успешно ре­ализована в виде модели (речь, в основном, идет о нейронах, расположенных в сетчатке), и на оценке темпов развития компьютерной технологии в ближайшем будущем. Любопытно, что к началу 1994 года он своего мнения не изменил; см. [267].

3. Эти четыре точки зрения были подробно описаны, например, в [214], с. 252 (следует, впрочем, отметить, что условие, называемое авто­ром статьи «тезисом Черча—Тьюринга», является, по своей сути, скорее «тезисом Тьюринга» (в том смысле, в каком я употребляю этот термин в § 1.6), нежели «тезисом Черча»).

4. Например, Д.Деннет, Д. Хофштадтер, М. Мински, X. Моравек, Г. Саймон; подробнее о терминах можно прочесть в [339], [242].

5. См. [266].

6. [368]; см. также НРК, с. 5-14.

7. См. [339], [340].

8. Вопрос осложняется тем, что современная физика рассматривает, по большей части, непрерывные, а не дискретные(цифровые) про­цессы. Самый смысл термина «вычислимость» в данном контексте можно трактовать по-разному. С некоторыми рассуждениями на данную тему можно ознакомиться в [311], [345], [312], [313], [314], [315], [29], [326], [327]. К этому вопросу я еще вернусь в

9. Этой замечательной фразой я обязан диктору ВВС Radio 4, веду­щему программу «Мысль дня».

10. Исследования в области создания ИИ начались в 1950-е годы с весьма успешного применения сравнительно элементарных нисхо­дящих процедур (например, Грей Уолтер, 1953). Распознающий об­разы «перцептрон» Фрэнка Розенблатта [322] стал в 1959 году пер­вым удачным «связным» устройством (искусственной нейронной сетью), вызвав тем самым значительный интерес к схемам восходя­щего типа. В 1969 году Марвин Мински и Сеймур Пейперт указали на некоторые существенные ограничения, присущие данному типу восходящей организации (см. [263]). Способ обойти эти ограниче­ния предложил некоторое время спустя Хопфилд [206], и в насто­ящий момент искусственными устройствами, функционирующими по типу нейронной сети, активно занимаются ученые всего мира. (О применении таких устройств, например, в физике высоких энер­гий см. [19] и [141].) Что касается ИИ нисходящего типа, то здесь важными вехами стали работы Джона Маккарти [247] и Алана Ньюэлла в сотрудничестве с Гербертом Саймоном [271]. Впечатля­ющее изложение истории исследований проблемы ИИ можно найти в [123]. Из прочей литературы порекомендую [174], [15] (относи­тельно недавние размышления о процедурах и перспективах ИИ); [97] (классическая критика идеи ИИ); [139] (свежий взгляд на про­блему от пионера ИИ); также см. статьи в сборниках[40] и [220].

11. Описание лямбда-исчисления см. в [52] и [222].

12. Из различных публикаций, посвященных данной проблематике, могу порекомендовать, например, [311], [345], [315], [29]. Вопрос о функционировании мозга в связи с упомянутыми проблемами рас­смотрен, в частности, в [325].

13. В действительности Роберт Бергер доказал, что общего алгорит­мического решения не имеет лишь задача о замощении плоскости плитками Вана. Плитки Вана (названные так в честь математи­ка Хао Вана) представляют собой единичные квадраты с окра­шенными краями; при замощении цвета соседних плиток должны совпадать, сами же плитки при этом нельзя ни вращать, ни пере­ворачивать. Впрочем, для любого набора плиток Вана несложно составить такой набор полиомино, которым можно будет замостить плоскость тогда и только тогда, когда ее можно замостить соответ­ствующим набором плиток Вана. Таким образом, неразрешимость вычислительными методами задачи о замощении плоскости набо­ром полиомино непосредственно следует из неразрешимости задачи о замощении плоскости набором плиток Вана.

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

14. О некоторых чересчур оптимистичных прогнозах относительно ИИ можно прочесть в [ 123].

15. Своим знакомством с этими вопросами я обязан очень многим людям, среди которых хочу особо поблагодарить Ли Левингера. Замечательное исследование связи современной физики и вычис­лительных методов с проблемами человеческого поведения можно найти в книге [199].

16. Сломен [343], например, пеняет мне на то, что в НРК я слишком часто прибегаю к такому неопределенному термину, как «созна­ние», в то время как сам он весьма свободно оперирует еще более неопределенным (на мой взгляд) термином «разум»!

17. См. [339], [340].

18. См. статью Серла [339] (ее также можно найти в сборнике [202], с. 372). Мне, правда, не совсем ясно, к какой точке зрения Серл склонился бы сейчас, к В или все же к В.

19. Занимательное рассмотрение подобного предположения представлено в [201]; см. также НРК, с. 21-22.

20. Суть понятия «алгоритмической сложности» доступным языком изложена в [45].

21. См. [207].

22. См. [123].

23. См..например,[267].

24. О доказательстве Лукаса см. [319], [344], [24], [162], [163], [235], [236], [201], [37]; см. также [246]. Что касается моей версии, кратко представленной в НРК, с. 416—418, то где только ее не критикова­ли: см., в особенности, [343] и многочисленные статьи в Behavioral and Brain Sciences: [36], [42], [46], [72], [73], [79], [96], [153], [198], [219], [250], [249], [252], [268], [306], [323], [365], [385]; мои ответы на критику см. в [291 ], [297] и [ 177]; см. также [94], [293].

25. Примеры взяты из какой-то английской телевизионной програм­мы; возможно, из «Машины мечты» (The Dream Machine, декабрь 1991 г.) — четвертой из цикла программ ВВС «Мыслящая маши­на» (The Thinking Machine). О последних достижениях в области «искусственного понимания», а в особенности, о захватывающем проекте Дугласа Лената «CYC» можно прочесть в [123].

26. Весьма живо и популярно все это описано в [388].

27. Подобное предположение выдвинул, например, Ричард Доукинс в своих «Рождественских лекциях» (ВВС, 1992 г.).

28. См., например, рассказ Фридмена [123] о работе Лената и других исследователей в этом направлении.

 

 

ГЕДЕЛЕВСКОЕ ДОКАЗАТЕЛЬСТВО

Теорема Гёделя и машины Тьюринга

Прежде чем мы начнем, мне бы хотелось хоть как-то успо­коить читателя в отношении математических формул, которые встретятся нам в нескольких… Так что же такое теорема Гёделя? В 1930 году на конферен­ции в Кенигсберге… Среди положений, которые со всей неоспоримостью доказал Гёдель, имеется следующее: нельзя создать такую формальную…

Вычисления

(А) Найти число, не являющееся суммой квадратов трех чисел. Под «числом» в данном случае я подразумеваю «натуральное число», т. е. число… 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ....

Незавершающиеся вычисления

(B) Найти число, не являющееся суммой квадратов четырех чи­сел. На этот раз, добравшись до числа 7, мы находим, что в виде суммы квадратов… Я, разумеется, не собираюсь докучать читателю подробно­стями доказательства Лагранжа, вместо этого рассмотрим одну не…

Как убедиться в невозможности завершить вычисление?

1,7, 19,37,61,91, 127, ..., иными словами, числа, из которых можно строить шестиугольные матрицы (пустую… Каждое такое число, за исключением начальной единицы, по­лучается добавлением к предыдущему числу соответствующего…

Семейства вычислений; следствие Гёделя — Тьюринга

В терминах машин Тьюринга это всего лишь означает, что C(n) есть действие, производимое некоей машиной Тьюринга над числом п. Иными словами, число n… Для того чтобы пояснить, что именно понимается под вы­числением, зависящим от… (F)Найти число, не являющееся суммой квадратов n чисел,

Q2. Мы, безусловно, должны допустить, что алгоритм А может оказаться и не фиксированным. Лю­ди, в конце концов, обладают способностью к обучению, а значит, применяемый ими при этом алгоритм вполне может претерпевать непрерывные из­менения.

Для описания изменяющегося алгоритма необходимо каким-то образом задать правила, согласно которым он, собственно, изменяется. Если сами по себе эти правила являются полностью алгоритмическими, то мы уже включили их в описание нашей гипотетической процедуры «А», иначе говоря, такой «изменя­ющийся алгоритм» на деле представляет собой всего-навсего еще один пример единичного алгоритма, и на наши рассужде­ния подобное допущение никак не влияет. С другой стороны, можно вообразить средства для изменения алгоритма, предпо­ложительно не являющиеся алгоритмическими: такие, например, как введение в алгоритм каких-то случайных составляющих или неких процедур взаимодействия его с окружением. «Неалгорит­мический» статус подобных средств изменения алгоритма мы еще будем рассматривать несколько позднее (см. §§ 3.9, 3.10); можно также вернуться к § 1.9, где было показано, что ни одно из этих средств не позволяет сколько-нибудь убедительно избавиться от алгоритмизма (как того требует точка зрения ^). В данном слу­чае, т. е. в рамках чисто математических рассуждений, нас зани­мает лишь возможность того, что такое изменение действительно будет носить алгоритмический характер. Если же предположить, что алгоритмическим оно быть никак не может, то мы, без­условно, придем к полному согласию с выводом &.

Пожалуй, следует немного подробнее остановиться на том, что может обозначать определение «алгоритмически изменяю­щийся» применительно к алгоритму А. Допустим, что алгоритм А зависит не только от q и п, но и еще от одного параметра t, который можно рассматривать как «время», а можно как просто количество предшествующих настоящему моменту случаев ак­тивации нашего алгоритма. Как бы то ни было, мы можем так­же предположить, что параметр t является натуральным числом, и записать следующий ряд алгоритмов A_t (<J, n):

A₀(q,n), Ai(q,n), A₂(q,n), A₃(q, n), ..., каждый элемент которого предположительно является обосно­ванной процедурой для установления незавершаемости вычисле­ния C_q (n), при этом мы будем считать, что мощность этих проце­дур возрастает по мере увеличения t. Предполагается также, что способ, посредством которого увеличивается мощность этих про­цедур, является алгоритмическим. Возможно, этот «алгоритми­ческий способ» зависит некоторым образом от «опыта» выпол­нения предыдущих алгоритмов A_t (q, n), однако в данном случае мы предполагаем, что этот «опыт» порождается также алгорит­мически (в противном случае мы снова приходим к согласию с ), т.е. мы имеем полное право включить «опыт» (или способы его порождения) в перечень операций, составляющих следующий ал­горитм (т.е., собственно, в A_t (q. n)). Действуя таким образом, мы опять-таки получаем единичный алгоритм (At (q, n)), кото­рый зависит алгоритмически от всех трех параметров: t, q, п. На его основе можно построить алгоритм Л*, столь же мощный, что и весь ряд A_t (q, п), однако зависящий только от двух натуральных чисел: q и п. Для получения такого A* (q, n) нам, как и преж­де, необходимо лишь выполнить первые десять шагов алгорит­ма ао (q, n) и запомнить результат; затем первые десять шагов алгоритма А1 (q, n) и вторые десять шагов алгоритма ао (q, n), запоминая получаемые результаты; затем первые десять шагов алгоритма A2 (q, n), вторые десять шагов алгоритма А1(q, n), третьи десять шагов алгоритма A₀ (q, n) и т. д., "запоминая по­лучаемые на каждом шаге вычисления результаты. В конечном итоге, сразу после завершения любого из составляющих алго­ритм вычислений завершается выполнение и всей процедуры в целом. Замена процедуры А процедурой А* никак не влияет на ход рассуждений, посредством которых мы пришли к выводу .

Q3. Не был ли я излишне категоричен, утверждая, что в тех случаях, когда уже можно определенно утверждать, что данное вычисление Сq(п) и вправду завершается, алгоритм А все равно должен вы­полняться бесконечно? Допусти мы, что А в таких случаях также завершается, все наше рассужде­ние оказалось бы ложным. В конце концов, обще­известно, что присущая людям способность к ин­туитивному пониманию позволяет им порой делать заключение о возможности завершения того или иного вычисления, однако я, судя по всему, здесь этой способностью пренебрег. Не слишком ли мно­го искусственных ограничений?

Вовсе нет. Предполагается, что наше рассуждение применимо лишь к тому пониманию, которое позволяет заключить, что вычисление не завершается, но никак не к тому пониманию, бла­годаря которому мы приходим к противоположному выводу. Ги­потетический алгоритм А вовсе не обязан достигать «успешного завершения», обнаружив что то или иное вычисление заверша­ется. Не в этом заключается его смысл.

Если вас такое положение дел не устраивает, попробуйте представить алгоритм А следующим образом: пусть А объединя­ет в себе оба вида понимания, но в том случае, когда выясняется, что вычисление C_q(n) действительно завершается, алгоритм А искусственно зацикливается (т. е. выполняет какую-то операцию снова и снова, бесконечное количество раз). Разумеется, на са­мом деле математики работают иначе, однако дело не в этом. Наше рассуждение построено как redactio ad absurdum, т.е. начав с допущения, что для установления математической исти­ны используются заведомо обоснованные алгоритмы, мы в итоге приходим к противоположному выводу. Такое доказательство не требует, чтобы гипотетическим алгоритмом непременно оказался какой-то конкретный алгоритм А, мы вполне можем заменить его на другой алгоритм, построенный на основе А, — как, например, в только что упомянутом случае.

Этот комментарий применим и к любому другому возраже­нию вида: «А что если алгоритм А завершится по какой-либо совершенно посторонней причине и не даст нам доказательства того, что вычисление C_q (n) не завершается?». Если нам вдруг придется иметь дело с алгоритмом «Л», который ведет себя по­добным образом, то мы просто применим представленное в §2.5 обоснование к немного другому А — а именно, к такому, который зацикливается всякий раз, когда исходный «Л» завершается по любой из упомянутых посторонних причин.

Q4. Судя по всему, каждое вычисление Cq в пред­ложенной мною последовательности С0, С1, С2,… является вполне определенным, тогда как при лю­бом прямом переборе (численном или алфавит­ном) компьютерных программ ситуация, конечно же, была бы иной?

В самом деле, было бы весьма затруднительно однознач­но гарантировать, что каждому натуральному числу q в нашей последовательности действительно соответствует некое рабочее вычисление C_q. Например, описанная в НРК последователь­ность машин Тьюринга Т_д этому условию, конечно же, не удовле­творяет; см. НРК, с. 54. При определенных значениях q маши­ну Тьюринга T_q можно назвать «фиктивной» по одной из четырех причин: ее работа никогда не завершается; она оказывается «некорректно определенной», поскольку представление числа n в виде двоичной последовательности содержит слишком много (пять или более) единиц подряд и, как следствие, не имеет интер­претации в данной схеме; она получает команду, которая вводит ее в нигде не описанное внутреннее состояние; или же по за­вершении работы она оставляет ленту пустой, т. е. не дает ника­кого численно интерпретируемого результата. (См. также При­ложение А.) Для приведенного в §2.5 доказательства Гёделя-Тьюринга вполне достаточно объединить все эти причины в одну категорию под названием «вычисление не завершается». В част­ности, когда я говорю, что вычислительная процедура А «завер­шается» (см. также примечание на с. 122), я подразумеваю, что она «завершается» как раз в вышеупомянутом смысле (а пото­му не содержит неинтерпретируемых последовательностей и не оставляет ленту пустой), — иными словами, «завершиться» мо­жет только действительно корректно определенное рабочее вы­числение. Аналогично, фраза «вычисление C_q (n) завершается» означает, что данное вычисление корректно завершается именно в этом смысле. При такой интерпретации соображение Q4не имеет совершенно никакого отношения к представленному мною доказательству.

Q5. Не является ли мое рассуждение лишь демонстрацией неприменимости некоей частной алго­ритмической процедуры (А) к выполнению вычис­ленияCq (n)? И каким образом оно показывает, что я справлюсь с задачей лучше, чем какая бы то ни было процедура A?

Оно и в самом деле вполне однозначно показывает, что мы справляемся с такого рода задачами гораздо лучше любого ал­горитма. Поэтому, собственно, я и воспользовался в своем рас­суждении приемом reductio ad absurdum. Пожалуй, в данном случае уместно будет привести аналогию. Читателям, вероятно, известно о евклидовом доказательстве невозможности отыскать наибольшее простое число, также основанном на reductio ad absurdum. Доказательство Евклида выглядит следующим обра­зом. Допустим, напротив, что такое наибольшее простое число нам известно; назовем его р. Теперь рассмотрим число N, кото­рое представляет собой сумму произведения всех простых чисел вплоть до р и единицы:

N = 2*3*5* ... * р + 1.

Число N, безусловно, больше р, однако оно не делится ни на одно из простых чисел 2, 3, 5, ..., р (поскольку при делении получаем единицу в остатке), откуда следует, что N либо и есть искомое наибольшее простое число, либо оно является составным, и тогда его можно разделить на простое число, большее р. И в том, и в другом случае мы находим простое число, большее р, что проти­воречит исходному допущению, заключавшемуся в том, что р есть наибольшее простое число. Следовательно, наибольшее простое число отыскать нельзя.

Такое рассуждение, основываясь на reductio ad absurdum, не просто показывает, что требуемому условию не соответству­ет некое частное простое число р, поскольку можно отыскать число больше него; оно показывает, что наибольшего простого числа просто не может существовать в природе. Аналогично, представленное выше доказательство Гёделя—Тьюринга не про­сто показывает, что нам не подходит тот или иной частный алго­ритм А, оно демонстрирует, что в природе не существует алго­ритма (познаваемо обоснованного), который был бы эквивален­тен способности человека к интуитивному пониманию, которую мы применяем для установления факта незавершаемости тех или иных вычислений.

Q6. Можно составить программу, выполняя кото­рую компьютер в точности повторит все этапы пред­ставленного мною доказательства. Не означает ли это, что компьютер оказывается в состоянии само­стоятельно прийти к любому заключению, к какому бы ни пришел я сам?

Отыскание конкретного вычисления Ck (k) при заданном алгоритме А, безусловно, представляет собой вычислительный процесс. Более того, это можно достаточно явно показать. Означает ли это, что предположительно неалгоритмическая математи­ческая интуиция — интуиция, благодаря которой мы определяем, что вычисление Ck (k) никогда не завершается — на деле явля­ется все же алгоритмической?

Думаю, данное суждение следует рассмотреть более подроб­но, поскольку оно представляет собой одно из наиболее рас­пространенных недоразумений, связанных с гёделевским доказа­тельством. Следует особо уяснить, что оно не сводит на нет ничего из сказанного ранее. Хотя процедуру отыскания вычис­ления Ck (k) с помощью алгоритма А можно представить в виде вычисления, это вычисление не входит в перечень процедур, со­держащихся в Л. И не может входить, поскольку самостоятель­но алгоритм А не способен установить истинность Ck (k), тогда как новое вычисление (вкупе с А], судя по всему, вполне на это способно. Таким образом, несмотря на то, что с помощью нового вычисления действительно можно отыскать вычисление Ck (k), членом клуба «официальных установителей истины» оно не яв­ляется.

Изложим все это несколько иначе. Вообразите себе управ­ляемого компьютером робота, способного устанавливать мате­матические истины с помощью алгоритмических процедур, со­держащихся в А. Для большей наглядности я буду пользоваться антропоморфной терминологией и говорить, что робот «знает» те математические истины (в данном случае — связанные с установ­лением факта незавершаемости вычислений), которые он может вывести, применяя алгоритм А. Однако если наш робот «знает» лишь А, то он никак не сможет «узнать», что вычисление Ck (k) не завершается, даже если процедура отыскания Ck (k) с по­мощью А является целиком и полностью алгоритмической. Мы, разумеется, могли бы сообщить роботу о том, что вычисле­ние Ck (k} и в самом деле не завершается (воспользовавшись для установления этого факта собственными пониманием и ин­туицией), однако, если робот примет это утверждение на «веру», ему придется изменить свои собственные правила, присоединив полученную новую истину к тем, что он уже «знает». Мы можем пойти еще дальше и каким-либо способом сообщить нашему ро­боту о том, что для получения новых истин на основании старых ему, помимо прочего, необходимо «знать» и общую вычислитель­ную процедуру отыскания Ck (k) посредством алгоритма А. К запасу «знаний» робота можно добавить все, что является вполне определенным и вычислительным по своей природе. Однако в ре­зультате у нас появляется новый алгоритм «Л», и доказательство Гёделя следует применять уже к нему, а не к старому А. Иначе говоря, везде вместо старого А нам следовало бы использовать новый «Л», поскольку менять алгоритм «Л» посреди доказатель­ства есть не что иное, как жульничество. Таким образом, как мы видим, изъян возражения Q6очень похож на рассмотренный выше изъян Q5. В нашем reductio ad absurdum мы полагаем, что алгоритм А (под которым понимается некая познаваемая и обоснованная процедура для установления факта незавершаемости вычислений) в действительности представляет собой всю совокупность известных математикам подобных процедур, из чего и следует противоречие. Попытку введения еще одной вы­числительной процедуры для установления истины — процеду­ры, не содержащейся в А, — после того как мы договорились, что А представляет собой всю их совокупность, я расцениваю как жульничество.

Беда нашего злосчастного робота в том, что, не обладая ка­ким бы то ни было пониманием гёделевской процедуры, он не располагает ни одним надежным и независимым способом уста­новления истины — истину ему сообщаем мы. (Эта проблема, вообще говоря, не имеет никакого отношения к вычислитель­ным аспектам доказательства Гёделя.) Для того чтобы достичь чего-то большего, ему, как и всем нам, необходимо понимание смысла операций, которые ему велено выполнять. Если тако­го понимания нет, то он вполне может «знать» (ошибочно), что вычисление Ck (k} завершается, а вовсе не наоборот. Заклю­чение (ошибочное) «вычисление Ck (&) завершается» выводится точно так же алгоритмически, как и заключение (правильное) «вычисление Ck (k) не завершается». Таким образом, дело во­все не в алгоритмическом характере этих операций, а в том, что для различения между алгоритмами, приводящими к истинным заключениям, и теми, что приводят к заключениям ложным, наш робот нуждается в способности выносить достоверные сужде­ния об истинности. Далее, на данной стадии рассуждения, мы все еще допускаем возможность того, что процесс «понимания» представляет собой некую разновидность алгоритмической дея­тельности, которая не содержится ни в одной из точно заданных и «заведомо» обоснованных процедур типа А. Например, пони­мание может осуществляться посредством выполнения какого-то необоснованного или непознаваемого алгоритма. В дальнейшем (см. главу 3) я попробую убедить читателя в том, что в действи­тельности понимание вообще не является алгоритмической дея­тельностью. На настоящий же момент нас интересуют всего лишь строгие следствия из доказательства Гёделя—Тьюринга, а на них возможность получения вычисления С^ (k) из процедуры А вы­числительным путем никоим образом не влияет.

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

Несмотря на кажущуюся логичность этого утверждения, здесь упущен из виду один очень существенный момент, а именно: способ, посредством которого мы (или компьютеры) определяем, какие математические утверждения истинны, а какие — ложны. (Во всяком случае, на простое хранение математических утвер­ждений способны и системы, гораздо менее сложные, нежели универсальный компьютер — например, фотоаппараты.) Прин­цип использования компьютера в Q7 совершенно не учитывает критического вопроса о наличии у этого самого компьютера спо­собности суждения об истинности. С равным успехом мож­но вообразить и компьютеры, в памяти которых не содержится ничего, кроме перечня абсолютно ложных математических «тео­рем», либо случайным образом перемешанных истинных и лож­ных утверждений. Откуда мы узнаем, какому компьютеру можно доверять? Я отнюдь не утверждаю, что эффективное моделиро­вание результатов сознательной интеллектуальной деятельности человека (в данном случае, в области математики) абсолютно невозможно, поскольку по одной лишь чистой случайности ком­пьютер может «умудриться» сделать все правильно, пусть и не обладая каким бы то ни было пониманием. Однако шансы на это до абсурдного малы, в то время как те вопросы, на которые мы здесь пытаемся найти ответ (например, каким таким образом мы определяем, что вот это математическое утверждение истинно, а вот это — ложно?), в возражении Q7 и вовсе не затрагиваются. С другой стороны, Q7все же напоминает об одном более существенном соображении. Имеет ли непосредственное отно­шение к нашему исследованию обсуждение бесконечных струк­тур (всех натуральных чисел или всех вычислений), если учесть, что совокупность всех результатов, полученных на тот или иной момент времени всеми людьми и компьютерами, имеет конечную величину? В следующем комментарии мы рассмотрим этот без­условно важный вопрос отдельно.

Q8. Незавершающиеся вычисления суть идеализи­рованные математические конструкции, по опре­делению бесконечные. Вряд ли подобные вопросы могут иметь сколько-нибудь непосредственное от­ношение к изучению конечных физических объек­тов — таких, как компьютеры или мозг.

Все верно, рассуждая в идеализированном ключе о машинах Тьюринга, незавершающихся вычислениях и т. п., мы рассматри­вали бесконечные (потенциально) процессы, тогда как в случае людей или компьютеров нам приходится иметь дело с системами конечными. И, разумеется, применяя подобные идеализирован­ные доказательства к реальным и конечным физическим объек­там, следует быть готовыми к тому, что такая операция непре­менно окажется связанной с теми или иными ограничениями и оговорками. Однако, как выясняется, учет конечной природы ре­альных объектов не изменяет сколько-нибудь существенно сути доказательства Гёделя—Тьюринга. Нет ничего странного в том, что мы рассуждаем об идеализированных вычислениях, обосно­вываем те или иные умозаключения и выводим, математически, их теоретические ограничения. Можно, к примеру, обсуждать в аб­солютно конечных терминах вопрос о том, существует ли нечет­ное число, являющееся суммой двух четных чисел, или существу­ет ли натуральное число, не являющееся суммой четырех квад­ратов (как в приведенных выше задачах (С)и (В)),нисколько не смущаясь тем, что при рассмотрении этих вопросов мы неявно учитываем бесконечное множество всех натуральных чисел. Мы имеем полное право рассуждать о незавершающихся вычисле­ниях или машинах Тьюринга вообще, как о математических структурах, пусть и не в силах создать на практике бесконеч­но работающую машину Тьюринга. (Отметим, в частности, что действие машины Тьюринга, занятой поисками нечетного числа, являющегося суммой двух четных чисел, строго говоря, практи­чески реализовать невозможно, так как ее детали износятся го­раздо раньше, чем минет вечность.) Описание любого единичного вычисления (или действия машины Тьюринга) — задача вполне конечная, а вопрос о том, завершится ли в конечном итоге это вычисление, можно полагать вполне определенным. Сначала мы доводим до логического завершения теоретические рассуждения, связанные с теми или иными идеализированными вычислениями, и лишь затем пытаемся разглядеть, каким образом наши рассу­ждения применимы к конечным физическим системам — таким, как реально существующие компьютеры или люди.

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

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

, , , , ,…,

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

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

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

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

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

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

А(n,n) = C_k(n).

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

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

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

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

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

Не помешает несколько более подробно остановиться на сравнительно незначительном увеличении сложности, сопрово­ждающем переход от А к C_k(k). Помимо прочего, это существен­но поможет нам в нашем дальнейшем исследовании (в §§3.19 и 3.20). В Приложении А (с. 191) предложено явное описание вычисления Ck(k) в виде предписаний для машины Тьюринга, рассмотренных в НРК (глава 2). Согласно этим предписаниям, под обозначением Т_т понимается «m-я машина Тьюринга». Для большего удобства и упрощения рассуждений здесь мы также будем пользоваться этим обозначением вместо «С_m», в част­ности, для определения степени, сложности вычислительной процедуры или отдельного вычисления. В соответствии с выше­сказанным, определим степень сложности машины Тьюрин­га Т_т как количество знаков в двоичном представлении числа т (см. НРК, с. 39); при этом степень сложности некоторого вы­числения Т_т (п) определяется как большее из двух чисел и v, где v — количество двоичных знаков в представлении числа п. Рассмотрим далее приведенное в Приложении А явное предпи­сание для составления вычисления Ck(k) на основании алгорит­ма А, заданного в упомянутых спецификациях машины Тьюринга. Полагая степень сложности А равной а, находим, что степень сложности явного вычисления Ck (k) не превышает числа а + 210 log₂ (а + 336) — а это число, в свою очередь, оказывается лишь очень ненамного больше собственно а, да и то только тогда, когда число а очень велико.

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

ВЗГЛЯНУТЬ.

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

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

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

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

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

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

выражает отрицание того, что высказывание Р (п) справедливо для всех… Условие же -непротиворечивости гласит, что если выска­зывание можно доказать с помощью методов фор­мальной системы F,…

Формальные системы и алгоритмическое доказательство

Напротив, располагая некоторой заданной вычислитель­ной процедурой Е, предназначенной для установления истинно­сти определенных математических… (Среди таких логических операций могут, к примеру, ока­заться следующие: «если… Поставив перед собой задачу построить на основе проце­дуры Е формальную систему Е, мы можем начать с некоторой в…

Q10. Абсолютна ли математическая истина? Как мы уже видели, существуют различные мнения относительно абсолютной истинности утверждений о » бесконечных множествах. Можем ли мы доверять доказательствам, опирающимся на какую-то рас­плывчатую концепцию «математической истины», а не на, скажем, четко определенное понятие формальной ИСТИНЫ?

Что касается формальной системы F, описывающей общую теорию множеств, то, действительно, не всегда ясно, можно ли вообще говорить о каком-то абсолютном смысле, в котором то или иное утверждение о множествах является либо «истинным», либо «ложным», — вследствие чего под сомнение может попасть и само понятие «обоснованности» формальной системы, подоб­ной F. В качестве поясняющего примера приведем один извест­ный результат, полученный Гёделем (1940) и Коэном (J 966). Они показали, что определенные математические утверждения (так называемые континуум-гипотеза Кантора и аксиома выбо­ра) никак не зависят от теоретике-множественных аксиом си­стемы Цермело--Френкеля — стандартной формальной систе­мы, обозначаемой здесь через ZF. (Аксиома выбора гласит, что для любой совокупности непустых множеств существует еще од­но множество, которое содержит ровно один элемент из каждо­го множества совокупности^. Согласно же континуум-гипотезе Кантора, количество подмножеств натуральных чисел — рав­ное количеству вещественных чисел — представляет собой вторую по величине бесконечность после множества собствен­но натуральных чисел^. Читателю нет нужды вникать в скры­тый смысл этих утверждений прямо сейчас. Равно как нет ну­жды и мне углубляться в подробное изложение аксиом и пра­вил процедуры системы ZF.) Некоторые математики убеждены в том, что система ZF охватывает все методы математического рассуждения, необходимые для обычной математики. Некоторые даже утверждают, будто приемлемым математическим доказа­тельством можно считать только такое доказательство, какое можно, в принципе, сформулировать и доказать в рамках систе­мы ZF. (См. комментарий к возражению Q14, где дается оценка применимости к таким субъектам гёделевского доказательства.) Иными словами, эти математики настаивают на том, что ИСТИННЫМИ, ЛОЖНЫМИ и НЕРАЗРЕШИМЫМИ в рамках систе­мы ZF математическими утверждениями можно считать только те утверждения, истинность, ложность и неразрешимость, соответ­ственно, которых, в принципе, устанавливается математически­ми средствами. Для таких людей аксиома выбора и континуум-гипотеза являются математически неразрешимыми (что, по их мнению, и доказывается выводом Гёделя—Коэна), и они наверня­ка будут утверждать, что истинность или ложность этих двух ма­тематических утверждений суть предметы достаточно условные. Влияют ли эти кажущиеся неопределенности в отношении абсолютного характера математической истины на выводы, ко­торые мы сделали из доказательства Гёделя—Тьюринга? Никоим образом, так как мы имеем здесь дело с классом математиче­ских проблем гораздо более ограниченной природы, нежели те, что, подобно аксиоме выбора и континуум-гипотезе, относятся к неконструктивно-бесконечным множествам. В данном случае нас занимают лишь утверждения вида

«такое-то вычисление никогда не завершается»,

причем рассматриваемые вычисления можно задать совершен­но точно через действия машины Тьюринга. Такие утвержде­ния в логике называются Hi-высказываниями (или, точнее, П5-высказываниями). В пределах формальной системы F утвержде­ние G (F) является Щ-высказыванием, а вот П (F) таковым не является (см. §2.8). По всей видимости, не существует каких-либо разумных доводов против того, что истинный/ложный ха­рактер любого Щ-высказывания есть предмет абсолютный и никак не зависит от избранного нами мнения относитель­но предположений, касающихся неконструктивно-бесконечных множеств — таких, например, как аксиома выбора и континуум-гипотеза. (С другой стороны, как мы вскоре убедимся, выбор метода рассуждения, принимаемого нами в качестве инструмента для получения убедительных доказательств hi -высказываний, действительно может определяться мнением, которого мы при­держиваемся в отношении неконструктивно-бесконечных мно­жеств; см. возражение Q11.) Очевидно, если не считать крайней позиции, занимаемой отдельными интуиционистами(см. коммен­тарий к Q9), единственное здравое возражение по поводу абсо­лютного характера истинности таких утверждений может быть связано с тем обстоятельством, что некоторые принципиально завершающиеся вычисления могут потребовать для своего вы­полнения столь непомерно долгого времени, что на практике, вполне возможно, не завершатся и, скажем, за все время жизни вселенной; может случиться и так, что для записи самого вычис­ления (пусть и конечного) потребуется так много символов, что физически невозможным окажется составить даже его описание. Впрочем, все эти вопросы были исчерпывающим образом про­анализированы выше, в обсуждении возражения Q8, там же мы выяснили, что на наш основной вывод <£ они никоим образом не влияют. Вспомним и о возражении Q9, рассмотрение которого показало, что позиция интуиционистов в этом случае также не избегает вывода Ш.

Кроме того, концепция (весьма ограниченная, надо сказать) математической истины, необходимая мне для доказательства Гёделя—Тьюринга, определена, вообще говоря, не менее четко, нежели концепции ИСТИННОГО, ЛОЖНОГО и НЕРАЗРЕШИМО­ГО для любой формальной системы F. Из сказанного выше (§ 2.9) нам известно, что существует некий алгоритм F, эквивалентный системе F. Если алгоритму F предстоит обработать некое пред­положение Р (формулируемое на языке системы F), то выпол­нение этого алгоритма может быть успешно завершено только в том случае, если предположение Р доказуемо в соответствии с правилами системы F, т.е. когда предположение Р ИСТИН­НО. Соответственно, предположение Р является ложным, если алгоритм F успешно завершается при обработке предположе­ния ~ Р, и НЕРАЗРЕШИМЫМ, если не завершается ни одно из упомянутых вычислений. Вопрос о том, является ли математи­ческое утверждение Р истинным, ложным или НЕРАЗРЕ­ШИМЫМ, в точности совпадает по своей природе с вопросом о реальной истинности утверждений о завершаемости или незавершаемости вычислений — иными словами, о ложности или ис­тинности определенных hi-высказываний — а кроме этого для нашего «гёделевско—тьюринговского» доказательства ничего и не требуется.

Q11. Существуют определенные П1-высказывания, которые можно доказать с помощью теории беско­нечных множеств, однако не известно ни одного до­казательства, которое использовало бы стандарт­ные «конечные» методы. Не означает ли это, что даже к таким четко определенным проблемам ма­тематики, на деле, подходят субъективно? Различ­ные математики, придерживающиеся в отношении теории множеств разных убеждений, могут применять к оценке математической истинности П1-высказываний неэквивалентные критерии.

Этот момент может оказаться существенным в том, что касается моих собственных выводов из доказательства Гёделя (—Тьюринга), и я, возможно, уделил ему недостаточно много вни­мания в кратком изложении, представленном в НРК. Как ни странно, но возражение QM, похоже, никого, кроме меня, не обеспокоило — по крайней мере, никто мне на него не указал! В НРК (с. 417, 418), как и здесь, я сформулировал доказатель­ство Гёделя(—Тьюринга) исходя из того, что посредством разума и понимания способны установить все «математики» или «мате­матическое сообщество». Преимущество подобной формулиров­ки, в отличие от рассмотрения вопроса о способности какого-либо конкретного индивидуума к установлению математиче­ских истин посредством своего разума и понимания, заключается в том, что первый способ позволяет избежать некоторых воз­ражений, которые нередко выдвигают в отношении той версии доказательства Гёделя, которую предложил Лукас (196 J). Самые разные ученые^³-¹ указывали, к примеру, на то, что «сам Лукас» никак не мог обладать знанием о своем собственном алгоритме. (Некоторые из них говорили то же самое и о варианте дока­зательства, предложенном много-, не обратив, судя по всему, внимания на тот факт, что моя формулировка вовсе не настолько «личностна».) Именно возможность сослаться на способности к рассуждению и пониманию, присущие всем «математикам» вооб­ще или «математическому сообществу», позволяет нам избежать необходимости считаться с предположением о том, что различные индивидуумы могут воспринимать математическую истину по-разному, каждый в соответствии с личным непознаваемым алго­ритмом. Значительно сложнее смириться с тем, что результатом выполнения некоего непостижимого алгоритма может оказаться коллективное понимание математического сообщества в целом, нежели с тем, что этот самый алгоритм обусловливает матема­тическое понимание всего лишь какого-то конкретного индиви­дуума. Суть возражения QJI как раз и заключается в том, что упомянутое коллективное понимание может оказаться совсем не таким универсальным и безличным, каким счел его я.

Утверждения, о каких говорится в Q11, действительно, су­ществуют. То есть существуют Щ -высказывания, единственные известные доказательства которых опираются на то или иное применение теории бесконечных множеств. Такое Щ -высказы­вание может быть результатом арифметического кодирования утверждения типа «аксиомы формальной системы F являются непротиворечивыми», где система F подразумевает манипуля­ции обширными бесконечными множествами, само существова­ние которых может быть сомнительным. Математик, убежденный в реальном существовании некоторого достаточно обширного неконструктивного множества S, придет к выводу, что система F действительно непротиворечива, тогда как другой математик, ко­торый полагает, что множества S не существует, вовсе не обя­зан считать систему F непротиворечивой. Таким образом, даже ограничив рассмотрение одним вполне определенным вопросом о завершении или незавершении работы машины Тьюринга (т. е. ложности или истинности П₁-высказываний), мы не можем се­бе позволить не учитывать субъективности убеждений в от­ношении, скажем, существования некоторого обширного некон­структивно-бесконечного множества S. Если различные матема­тики используют для установления истинности определенных П₁ -высказываний неэквивалентные «персональные алгоритмы», то, по-видимому, с моей стороны несправедливо говорить о про-. сто «математиках» или «математическом сообществе».

Полагаю, что в строгом смысле это действительно может быть несколько несправедливо; и читатель может при желании перефразировать вывод следующим образом:

* Для установления математической истины ни один отдельно взятый математик не применяет только те алгоритмы, какие он (или она) полагает обоснованными. j

Представленные мною доводы по-прежнему остаются в силе, од­нако, мне кажется, некоторые из более поздних утратят значи­тельную часть своей силы, если представить ситуацию в таком виде. Более того, в случае формулировки * все доказатель­ство уходит в направлении, на мой взгляд, бесперспективном, сосредоточенном, в большей степени, на конкретных механизмах, управляющих действиями конкретных индивидуумов, нежели на принципах, лежащих в основе действий любого из нас. Меня же на данном этапе интересует не столько различия подходов от­дельных математиков к той или иной математической проблеме, сколько то общее, что есть между нашим пониманием и нашим математическим восприятием.

Попытаемся разобраться, действительно ли мы вынужде­ны принять формулировку *. В самом ли деле суждения мате­матиков настолько субъективны, что они могут принципиально расходиться при установлении истинности какого-то конкрет­ного III-высказывания? (Разумеется, доказательство, устанав­ливающее истинность hi-высказывания, может быть просто-напросто быть слишком громоздким или слишком сложным, что­бы его мог воспроизвести тот или иной математик (см. ниже по тексту возражение Q12),т.е. на практике математики вполне могут разойтись во мнениях. Однако в данном случае нас ин­тересует вовсе не это. Мы занимаемся исключительно принци­пиальными вопросами.) Вообще говоря, математическое дока­зательство есть вещь не настолько субъективная, как может по­казаться на основании вышесказанного. Математики могут при­держиваться самых разных — и, на их взгляд, неопровержимо истинных — точек зрения по тем или иным фундаментальным вопросам и во всеуслышание объявлять об этом, однако едва дело доходит до доказательств или опровержений каких-либо вполне определенных конкретных hi-высказываний, все разно­гласия тут же куда-то исчезают. Никто не воспримет всерьез доказательство hi-высказывания, утверждающего, по сути сво­ей, непротиворечивость некоторой формальной системы F, если математик будет основывать его только лишь на существовании некоего спорного бесконечного множества S. То, что при этом в действительности доказывается, можно сформулировать следу­ющим, куда более приемлемым, образом: «Если множество S су­ществует, то формальная система F является непротиворечивой, и в этом случае данное П₁-высказывание истинно».

Тем не менее, могут быть и исключения: например, один ма­тематик полагает, что некоторое неконструктивно-бесконечное множество S «с очевидностью» существует — или, по крайней мере, что допущение о его существовании никоим образом не приводит к противоречию, — другой же математик никакой оче­видности здесь не усматривает. Дискуссии математиков по таким фундаментальным вопросам могут порой принимать поистине неразрешимый характер. При этом обе стороны могут оказаться, в принципе, неспособны сколько-нибудь убедительно изложить свои доказательства, даже в отношении П₁-высказываний. Воз­можно, каждому математику и в самом деле присуще некое осо­бое внутреннее восприятие истинности утверждений, связанных с неконструктивно-бесконечными множествами. Конечно же, ма­тематики нередко заявляют о том, что их восприятие таких вещей в корне отличается от восприятия коллег. Однако я по­лагаю, что такие различия, по сути своей, подобны различиям в ожиданиях, которые различные математики могут иметь и в отношении истинности обычных математических высказываний. Эти ожидания суть всего лишь предварительные предположения. До тех пор, пока не представлено убедительного доказательства или опровержения, математики могут спорить друг с другом об ожидаемой или предполагаемой истинности того или иного по­ложения, однако представление такого доказательства одним из математиков убеждает (в принципе) всех. Что до фундаменталь­ных вопросов, то там этих доказательств как раз нет. Возможно, и не будет. Быть может, их нельзя отыскать по той причине, что их просто-напросто нет, а фундаментальные вопросы допускают существование различных, но равно справедливых точек зрения. Здесь, однако, следует подчеркнуть еще один связанный с hi-высказываниями момент. Возможность наличия у матема­тика ошибочной точки зрения — т. е. такой точки зрения, кото­рая вынуждает его делать неверные выводы в отношении истин­ности тех или иных П₁-высказываний, — нас в данный момент не интересует. Нет ничего невероятного в том, что математики порой опираются на неверное в фактическом отношении «пони­мание» — а то и на необоснованные алгоритмы, — только к настоящему обсуждению это никакого отношения не имеет, поскольку согласуется с выводом У. Впрочем, эту ситуацию мы подробно рассмотрим ниже, в § 3.4. Следовательно, дело в данном случае заключается не в том, могут ли разные математи­ки придерживаться противоречащих, одна другой точек зрения, а скорее в том, может ли одна точка зрения оказаться, в принципе, мощнее другой. Каждая такая точка зрения будет совершенно справедлива в том, что касается установления истинности П₁-высказываний, однако какая-то из них сможет, в принципе, дать своим последователям возможность установить, что те или иные вычисления не завершаются, тогда как другие, более слабые, точки зрения на это неспособны; то есть одни математики будут обладать существенно большей способностью к пониманию, нежели другие.

Не думаю, что такая возможность представляет собой сколь­ко-нибудь серьезную угрозу для моей первоначальной формули­ровки . Хотя в отношении бесконечных множеств математики и вправе придерживаться различных точек зрения, этих самых точек зрения вовсе не так много: по всей видимости, не бо­лее пяти. Существенные в этом смысле расхождения могут быть обусловлены лишь утверждениями, подобными аксиоме выбора (о ней говорилось в комментарии к возражению Q10),которую одни полагают «очевидной», другие же напрочь отвергают свя­занную с ней неконструктивность. Любопытно, что эти различ­ные точки зрения на собственно аксиому выбора не приводят непосредственно к тому П₁-высказыванию, относительно спра­ведливости которого возникают разногласия. Ибо, независимо от своей предполагаемой «истинности» или «ложности», аксиома выбора, как показывает теорема Гёделя—Коэна(см. комментарий к Q10),не вступает в противоречие со стандартными аксиома­ми системы ZF. Могут, однако, существовать и другие спорные аксиомы, соответствующей теоремы для которых нет. Впрочем, обыкновенно, когда речь заходит о принятии или опровержении той или иной теоретико-множественной аксиомы — назовем ее аксиомой Q, — утверждения математиков принимают следую­щий вид: «Из допущения справедливости аксиомы Q следует, что ... ». Такое утверждение при всем желании не сможет стать предметом спора между математиками. Аксиома выбора, похоже, является исключением в том смысле, что ее справедливость часто подразумевается без приведения упомянутой оговорки, однако это обстоятельство, по-видимому, никак не противоречит моей общей объективной формулировке вывода — при условии, что мы ограничимся только П₁-высказываниями:

Для установления истинности П₁-высказываний математики-люди не применяют заведомо обоснован­ные алгоритмы, а этого нам в любом случае вполне достаточно.

Есть ли другие спорные аксиомы, которые одни математи­ки считают «очевидными», а другие ставят под сомнение? Ду­маю, будет огромным преувеличением сказать, что имеется хотя бы десять существенно различных точек зрения на теоретико-множественные допущения, которые в явном виде как допущения не формулируются. Положим, что их не более десяти, и рассмот­рим следствия из этого допущения. Это означает, что существует порядка десяти, по сути, различных классов математиков, раз­личаемых по типу рассуждения в отношении бесконечных мно­жеств, который они полагают «очевидно» истинным. Каждого та­кого математика можно назвать математиком n-го класса, где n изменяется в весьма узком диапазоне — не более десяти значе­ний. (Чем больше номер класса, тем мощнее будет точка зрения принадлежащих к нему математиков.) Вывод ** принимает в этом случае следующий вид:

Для установления истинности ГЦ –высказываний математики-люди n-го класса (где n может принимать лишь несколько значений) не применяют только те алгоритмы, какие они полагают обоснованными.

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

Q12. Вне зависимости оттого, насколько различных точек зрения придерживаются математики в прин­ципе, на практике те же математики обладают весьма разными способностями к воспроизведению доказательств, разве не так? Не менее различны и их способности к пониманию, позволяющие им совершать математические открытия.

Безусловно, так оно и есть, однако к рассматриваемому во­просу все эти вещи не имеют ну абсолютно никакого отноше­ния. Меня не интересует, какие именно и насколько сложные до­казательства математик способен воспроизвести на практике. Еще меньше меня занимает вопрос о том, какие доказательства математик может на практике открыть или какие понимание и вдохновение могут ему в этом способствовать. Здесь мы говорим исключительно о том, доказательства какого типа математики могут, в принципе, воспринимать как обоснованные.

Оговорка «в принципе» используется в наших рассужде­ниях отнюдь не просто так. Если допустить, что некий матема­тик располагает доказательством или опровержением некоторо­го III -высказывания, то его разногласия с другими математиками касательно обоснованности данного доказательства разрешимы только в том случае, если у этих самых других математиков хватит времени, терпения, объективности, способностей и решимости с вниманием и пониманием воспроизвести всю — возможно, длин­ную и хитроумную — цепочку его рассуждений. На практике же математики вполне могут отказаться от всех этих трудов еще до полного разрешения спорных вопросов. Однако подобные про­блемы к данному исследованию отношения не имеют. Так как, по всей видимости, существует все же некий вполне определенный смысл, в котором то, что в принципе постижимо для одного мате­матика, оказывается равным образом (если отвлечься на время от возражения Q11) постижимо и для другого, — вообще, для лю­бого человека, способного мыслить. Рассуждения бывают весьма громоздкими, а участвующие в них концепции могут показаться чересчур тонкими или туманными, и тем не менее существуют достаточно убедительные основания полагать, что способность к пониманию одного человека не включает в себя ничего такого, что в принципе недоступно другому человеку. Это применимо и к тем случаям, когда для воспроизведения во всех подробностях чисто вычислительной части доказательства может потребовать­ся помощь компьютера. Возможно, не совсем разумно ожидать, что математик-человек будет лично выполнять все необходимые для такого доказательства вычисления, и все же он, вне всякого сомнения, сможет без особого труда понять и проверить каждый отдельный его этап.

Здесь я говорю исключительно о сложности математическо­го доказательства и ни в коем случае не о возможных существен­ных и принципиальных вопросах, которые могут вызвать среди математиков разногласия в отношении выбора допустимых ме­тодов рассуждения. Разумеется, я встречал математиков, утвер­ждавших, что они в своей практике сталкивались с такими ма­тематическими доказательствами, которые были совершенно вне их компетенции: «Я уверен, что, сколько бы я ни старался, мне никогда не понять того-то или такого-то; этот метод рассужде­ния мне не по зубам». В каждом конкретном случае подобного заявления необходимо индивидуально решать, действительно ли данный метод рассуждения в принципе выходит за рамки систе­мы убеждений этого математика — каковой случай мы рассмат­ривали в комментарии к возражению Q11, — или он вообще-то смог бы разобраться в принципах, на которых основано это доказательство, если бы только приложил больше сил и затра­тил больше времени. Как правило, справедливым оказывается последнее. Более того, источником отчаяния нашего математи­ка чаще всего становится туманный стиль изложения или огра­ниченные лекторские способности «такого-то», а вовсе не то, что какие-то существенные и принципиальные моменты «того-то» действительно выходят за рамки его способностей. Толковое изложение, на первый взгляд, непонятного предмета чудесным образом устраняет все прежние недоразумения.

Чтобы еще раз подчеркнуть, что я имею в виду, скажу сле­дующее: сам я часто посещаю математические семинары, на ко­торых не слежу (а иногда и не пытаюсь следить) за подробно­стями представляемых доказательств. Наверное, если бы я сел где-нибудь и обстоятельно изучил эти самые доказательства, я и в самом деле смог бы проследить за мыслью автора — хотя, возможно, это удалось бы мне лишь при наличии дополнитель­ной литературы или устных пояснений, которые восполнили бы возможные пробелы в моем образовании или же в материалах самого семинара. Я знаю, что в действительности я этого делать не стану. У меня почти наверняка не окажется на это ни време­ни, ни достаточного количества внимания, ни, впрочем, особого желания. Но при этом я вполне могу принять представленный на семинаре результат на веру по всевозможным «несущественным» причинам — например, потому что полученный результат правдоподобно «выглядит», или потому что у лектора надежная репутация, или потому что другие слушатели, которых я считаю более сведущими в таких делах, нежели я сам, этот результат оспаривать не стали. Конечно, я могу ошибиться во всех своих умозаключениях, а результат вполне может оказаться ложным — либо истинным, но никоим образом не следующим из представ­ленного доказательства. Все эти тонкости никак не влияют на ту принципиальную позицию, которую я здесь представляю. Ре­зультат может оказаться истинным и адекватно доказанным, и в таком случае я, в принципе, могу проследить за ходом всего доказательства — или же ошибочным, в каковом случае, как уже упоминалось, он нас в данном контексте не интересует (см. § 3.2 и § 3.4). Возможные исключения могут составить лишь те случаи, когда представляемый материал касается каких-либо спорных аспектов теории бесконечных множеств или опирается на какой-то необычный метод рассуждения, который может быть признан сомнительным в соответствии с теми или иными математически­ми воззрениями (что, само по себе, может заинтриговать меня до такой степени, что я впоследствии действительно попытаюсь это доказательство повторить). Как раз такие исключительные ситуации мы обсуждали выше, в комментарии к возражению Q11. Что касается подобных соображений относительно природы математической точки зрения, на практике многие математики могут и не иметь четкого представления о том, каких именно фундаментальных принципов они в действительности придержи­ваются. Однако, как уже было сказано выше, в комментарии к QI1, если математик, у которого нет определенной позиции в отношении того, следует ли принимать, скажем, некую «аксиому Q», желает проявить осмотрительность, то ничто не мешает ему изложить требующие принятия аксиомы Q результаты в следую­щем виде: «Из принятия аксиомы Q следует, что... ». Разумеет­ся, математики, несмотря на всю их пресловутую педантичность, проявляют в подобных вопросах должную осмотрительность да­леко не всегда. Нельзя отрицать и того, что время от времени им удается допускать и вовсе очевидные ошибки. И все же все эти ошибки — если они допущены по недосмотру, а не следуют из тех или иных непоколебимых принципов — являются исправимыми. (Как упоминалось ранее, возможность действительного примене­ния математиками в качестве основы для своих решений необоснованного алгоритма будет подробно рассмотрена в §3.2 и §3.4. Поскольку эта возможность не противоречит выводу , она не является предметом настоящего обсуждения.) В данном слу­чае нас не занимают исправимые ошибки, так как к вопросу о принципиальной достижимости тех или иных результатов они ни­какого отношения не имеют. А вот возможные неопределенно­сти в действительных взглядах математиков, безусловно, требуют дальнейшего обсуждения, которое и приводится ниже.

QI3. У математиков нет абсолютно определен­ных убеждений относительно обоснованности или непротиворечивости используемых ими формальных систем — как нет и однозначного ответа на вопрос о том, «пользователями» каких именно формальных систем они себя полагают. Не подвергаются ли их убеждения постепенному размыванию по мере того, как формальные системы все более удаляются от области феноменов, доступных непосредственному интуитивному или эксперименталь­ному восприятию?

И правда, нечасто встретишь математика, способного по­хвалиться прочно устоявшимися и непоколебимо непротиворе­чивыми убеждениями, когда речь заходит об основах предмета. Кроме того, по мере накопления опыта математик вполне может изменить свои взгляды относительно того, что считать неопро­вержимо истинным, если он вообще склонен считать неопровер­жимо истинным что бы то ни было. Можно ли, например, быть совершенно и полностью уверенным в том, что число 1 отлично от числа 2? Если говорить о некоей абсолютной человеческой уверенности, то не совсем ясно, можно ли подобное понятие как-то однозначно определить. Однако какую-то точку опоры все же выбрать необходимо. Вполне приемлемой точкой опоры может стать принятие в качестве неопровержимо истинной некоторой системы убеждений и принципов, от которой уже можно двигать­ся в своих рассуждениях дальше. Разумеется, нельзя забывать и о том, что многие математики вовсе не имеют определенного мнения относительно того, что именно можно считать неопро­вержимо истинным. Таких математиков я попросил бы какую-никакую опору для себя все же выбрать и просто быть готовы­ми при необходимости впоследствии ее сменить. Как показывает доказательство Гёделя, какую бы позицию математик в этом случае ни занял, ее все равно невозможно полностью уместить в рамки правил любой постижимой формальной системы (а если и возможно, то этот факт невозможно однозначно установить). И дело даже не в том, что та или иная конкретная позиция по­стоянно изменяется; система убеждений, полностью охватыва­емая рамками любой (достаточно обширной) формальной си­стемы F, неизбежно должна также простирается и за пределы доступной F области. Любая позиция, среди неопровержимых убеждений которой имеется и убеждение в обоснованности си­стемы F, должна также включать в себя и убежденность в ис­тинности гёделевского предположения G(F). Убежденность в истинности G(F) не представляет собой изменения позиции; эта убежденность уже подразумевается неявно в исходной позиции, допускающей принятие истинности формальной системы F, пусть даже поначалу это и не очевидно.

Безусловно, всегда существует возможность того, что в вы­воды, получаемые математиком на основании исходных посылок какой-либо конкретной точки зрения, закрадется ошибка. Од­на только возможность возникновения такой ошибки — даже если в действительности никакой ошибки допущено не было — может привести к уменьшению степени убежденности, которую математик питает в отношении своих выводов. Однако такое «по­степенное размывание» нас, вообще говоря, не занимает. По­добно действительным ошибкам, оно «исправимо». Более того, если доказательство было проведено действительно корректно, то чем дольше его изучаешь, тем, как правило, более убедитель­ными представляются полученные в нем выводы. «Постепенное размывание» математик может испытать на практике, но не в принципе, что возвращает нас к обсуждению возражения Q12.

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

Однако следует ли считать высказывание G(F) неопровер­жимо истинным всякий раз, когда мы признаем неопровержимо обоснованной формальную систему F? Полагаю, утвердительный ответ на этот вопрос не должен вызывать никаких сомнений; и это тем более так, если придерживаться в отношении воспро­изведения математического доказательства той «принципиаль­ной» позиции, которой мы придерживались до сих пор. Един­ственная возникающая в этой связи реальная проблема касает­ся деталей фактического кодирования утверждения «система F непротиворечива» в форме арифметического утверждения (IIi-высказывания). Сама по себе базовая идея неопровержимо оче­видна: если система F является обоснованной, то она, безуслов­но, непротиворечива. (Так как если бы она не была непротиво­речивой, то среди ее утверждений присутствовало бы утвержде­ние «1 = 2», т.е. система была бы необоснованной.) Что касается деталей этого самого кодирования, то здесь нам вновь предстоит иметь дело с различием между «принципиальным» и «практи­ческим» уровнями. Не составит особого труда убедиться в том, что такое кодирование в принципе возможно (хотя сам процесс убеждения может занять некоторое время), однако убедиться в корректном выполнении того или иного конкретного действи­тельного кодирования — дело совсем другое. Детали кодиро­вания, как правило, бывают в известной степени произвольными и в разных изложениях могут весьма значительно отличаться. Возможно, где-то закрадется незначительная ошибка или просто опечатка, которая, в формальном смысле, должна бы сделать недействительным данное конкретное предназначенное для вы­ражения «G(F)» теоретико-числовое предположение, однако в действительности этого не происходит.

Надеюсь, читатель понимает, что возможность возникнове­ния таких ошибок не существенна, когда речь заходит о том, что мы подразумеваем здесь под принятием предположения G (F) в качестве неопровержимой истины. Я, разумеется, говорю о дей­ствительном предположении G (F), а не о возможном случай­ном предположении, непреднамеренно сформулированном бла­годаря опечатке или незначительной ошибке. В этой связи мне вспоминается одна история о великом американском физике Ри­чарде Фейнмане. Фейнман, по-видимому, объяснял одному из студентов какое-то понятие, но оговорился. Когда студент выра­зил недоумение, Фейнман вспылил: «Не слушайте, что я говорю; слушайте, что я имею в виду!».

Один из возможных способов такого явного кодирования состоит в использовании представленных еще в НРК специфика­ций машин Тьюринга и точном воспроизведении доказательства гёделевского типа, описанного в §2.5 (пример такого кодиро­вания приводится в Приложении А). Впрочем, даже и в этом случае об абсолютной «явности» говорить нельзя, поскольку нам понадобится еще и каким-то явным образом закодировать пра­вила формальной системы F в системе обозначений действий ма­шин Тьюринга; обозначим такой код, скажем, через Ту. (Код tf должен удовлетворять определенному свойству: если некоторому высказыванию Р, выводимому в рамках системы F, ставится в соответствие некоторое число р, то необходимо, скажем, чтобы равенство tf (р) — 1 выполнялось всякий раз, когда высказы­вание Р является теоремой системы F, в противном же случае вычисление Tf(p) не должно завершаться вовсе.) Безусловно, все это открывает широкий простор для формальных ошибок. Помимо возможных трудностей, связанных с практическим по­строением кода Ту на основе системы F и отысканием числа р на основе высказывания Р, отсутствует ясность и в отношении другого вопроса: а не ошибся ли я сам где-нибудь в специфи­кациях машин Тьюринга, — иными словами, можем ли мы быть полностью уверены в корректности приведенного в Приложении А этой книги кода, если вдруг решим использовать для отыска­ния вычисления Ck (k) именно это определение? Лично я думаю, что ошибок там нет, однако в собственной непогрешимости я уверен куда как меньше, нежели в первоначальных построениях Гёделя (пусть и более сложных). Впрочем, всякому дочитавшему до этого места, смею надеяться, уже ясно, что возможные ошибки подобного рода существенной роли здесь не играют. Помните, что говорил Фейнман?

Что же касается собственно моих спецификаций, следует упомянуть еще один формальный момент. Представленный мною в §2.5 вариант доказательства Гёделя(-Тьюринга) опирается не на непротиворечивость системы F, а на обоснованность алго­ритма А, и являет собой критерий для установления незавершаемости вычислений (т.е. истинности ГЦ-высказываний). Этот вариант подходит нам ничуть не хуже любых других, посколь­ку известно, что из обоснованности алгоритма А следует ис­тинность утверждения о незавершаемости вычисления Ck (k), каковое явное утверждение (тоже П₁-высказывание) мы име­ем полное право использовать вместо высказывания G(F). Бо­лее того, как отмечали выше (см. §2.8), доказательство, вообще говоря, зависит не от непротиворечивости формальной систе­мы F, а от ее -непротиворечивости. Из обоснованности систе­мы F очевидно следует ее непротиворечивость, равно как и -непротиворечивость. Если допустить, что система F обоснована, то ни fi (F), ни G (F) из ее правил (см. §2.8) не следуют, однако оба эти высказывания являются истинными.

Думаю, можно с уверенностью заключить, что какое бы «по­степенное размывание» убежденности того или иного матема­тика ни сопровождало переход от убеждения в обоснованности формальной системы F к убеждению в истинности высказыва­ния G(F) (или О (F)), оно будет целиком и полностью обуслов­лено возможностью ошибки в точной формулировке получен­ного им высказывания «G(F)». (To же применимо и к выска­зыванию fi(F).) Все это не имеет непосредственного отноше­ния к настоящему обсуждению — при наличии подлинной (не случайной) формулировки высказывания G (F) никакого размы­вания убежденности происходить не должно. Если формальная система F неопровержимо обоснована, то ее высказывание G (F) столь же неопровержимо истинно. Все формы заключения ( , ) остаются неизменными при условии, что под «истин­ностью» подразумевается «неопровержимая истинность».

Q14. Нет никаких сомнений в том, что формальная система ZF — или некоторая стандартная ее модификация (обозначим ее через ZF*)—действительно включает в себя все необходимое для серьезной математической деятельности. Почему бы просто не принять эту систему за основу, смириться с недоказуемостью ее непротиворечивости и продолжить свои математические изыскания?

Полагаю, такая точка зрения весьма и весьма распростра­нена среди практикующих математиков, особенно тех, кто не слишком углубляется в фундаментальные основы или филосо­фию своего предмета. Подобное отношение вполне естественно для людей, главной заботой которых является просто хорошее выполнение серьезной, пусть и математической, работы (хотя в действительности такие люди крайне редко выражают свои результаты в рамках строгих правил формальных систем, по­добных ZF). Согласно этой точке зрения, математика имеет де­ло лишь с тем, что можно доказать или опровергнуть в рам­ках некоей конкретной формальной системы — такой, напри­мер, как ZF (или какая-либо ее модификация ZF*). С высоты такой позиции математическая деятельность и в самом деле на­поминает своего рода «игру». Назовем ее ZF-игрой (или ZF*-игрой), причем играть в эту игру следует в соответствии с пра­вилами, установленными в рамках данной системы. Такой подход характерен для формалиста, подлинный же формалист мыслит исключительно в терминах ИСТИННОГО и ЛОЖНОГО, которые не обязательно совпадают с истинным и ложным в их повсе­дневном смысле. Если формальная система обоснованна, то все, что является ИСТИННЫМ, и будет истинным, а все, что ЛОЖ­НО, будет ложным. Однако наверняка найдутся высказывания, формализуемые в рамках данной системы, которые, будучи ис­тинными, не являются ИСТИННЫМИ, и другие, которые, буду­чи ложными, не являются ЛОЖНЫМИ, иными словами, в обо­их случаях эти высказывания оказываются НЕРАЗРЕШИМЫМИ. Если система ZF непротиворечива, то в ZF-игре гёделевское высказывание G (ZF) и его отрицание ~ G (ZF) принадле­жат, соответственно, к этим двум категориям. (Более того, ока­жись система ZF противоречивой, то и высказывание G(ZF), и его отрицание ~ G(ZF) были бы истинными и ложными одновременно!)

ZF-игра, судя по всему, представляет собой исключитель­но разумный подход, позволяющий реализовать большую часть того, что нас интересует в обычной математике. Однако по при­чинам, которые обозначены выше, я совершенно не в состоянии понять, каким же образом из нее может «произрасти» реаль­ная точка зрения в отношении чьих бы то ни было математи­ческих убеждений. Ибо если кто-то считает, что с помощью «практикуемой» им математики он устанавливает исключительно подлинные математические истины — скажем, истинность IIi-высказываний, — то он должен верить и в то, что используемая им система обоснована; а если он верит в ее обоснованность, то он должен также верить в ее непротиворечивость, то есть в то, что IIi-высказывание, утверждающее истинность G (F), дей­ствительно истинно, несмотря на то, что оно НЕРАЗРЕШИ­МО. Таким образом, математические убеждения человека долж­ны включать в себя нечто, что в рамках ZF-игры невыводимо. С другой стороны, если человек не верит в обоснованность фор­мальной системы ZF, то он не может верить и в подлинную ис­тинность ИСТИННЫХ результатов, полученных с помощью ZF-игры. В обоих случаях сама по себе ZF-игра не в состоянии снабдить нас удовлетворительной позицией в том, что касается математической истинности. (Это равным образом применимо к любой формальной системе ZF*.)

Q15. Выбранная нами формальная система F может и не оказаться непротиворечивой — по крайней ме­ре, мы не можем быть вполне уверены в ее непро­тиворечивости; по какому же, в таком случае, праву мы утверждаем, что высказывание G (F) «очевидно» истинно?

Хотя этот вопрос был достаточно исчерпывающе рассмотрен в предыдущих обсуждениях, я полагаю, что суть того рассмот­рения полезно будет изложить еще раз, поскольку возражения, подобные Q15,чаще всего оказываются среди нападок на наше с Лукасом приложение теоремы Гёделя. Суть же в том, что мы вовсе не утверждаем, что высказывание G(F) непременно ис­тинно для любой формальной системы F, мы утверждаем лишь, что высказывание G (F) настолько же достоверно, насколько до­стоверна любая другая истина, получаемая применением правил самой системы F. (Вообще говоря, высказывание G (F) оказыва­ется более достоверным, нежели утверждения, получаемые дей­ствительным применением правил F, так как система F, даже будучи непротиворечивой, не обязательно будет обоснованной!) Если мы верим в истинность любого утверждения Р, выводимого исключительно с помощью правил системы F, то мы должны верить и в истинность G (F), по крайней мере, в той же степени, в какой мы верим в истинность Р. Таким образом, ни одна по­стижимая формальная система F — или эквивалентный ей алго­ритм F — не может послужить абсолютно полной основой для подлинного математического познания или формирования убе­ждений. Как отмечалось в комментариях к Q5 и Q6, наше дока­зательство построено как reductio ad absurdum: мы выдвигаем предположение, что система F действительно является абсолют­ной основой для формирования убеждений; а затем показываем, что такое предположение приводит к противоречию, т. е. является неверным.

Мы, конечно же, можем, как в Q14, выбрать для удобства какую-то конкретную систему F, хотя уверенности в том, что она обоснована, а потому непротиворечива, это нам не добавит. Впрочем, при наличии действительных сомнений в обоснован­ности системы F любой получаемый в рамках F результат Р сле­дует формулировать в виде

«высказывание Р выводимо в рамках системы F»

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

«высказывание Р невыводимо в рамках системы F».

Такие утверждения имеют вид: «такое-то вычисление не завер­шается» (или, по сути, «будучи примененным к высказыванию Р, алгоритм F не завершается»), что в точности совпадает с формой рассматриваемых нами di-высказываний. Вопрос: какие сред­ства мы полагаем допустимыми в процессе получения подобных утверждений? Каковы, наконец, те математические процедуры, в которые мы действительно верим и применяем при установлении математических истин? Такая система убеждений, при условии, что они достаточно разумны, никак не может быть эквивалент­на всего лишь убежденности в обоснованности и непротиворечи­вости формальной системы, какой бы эта формальная система ни была.

Q16. Заключение об истинности высказывания G(F) для непротиворечивой формальной системы F мы делаем, исходя из допущения, что те символы системы F, которые, как мы полагаем, служат для представления натуральных чисел, действително представляют натуральные числа. Окажись на их месте другие числа — скажем, некие экзотические «сверхнатуральные» числа, — мы вполне могли бы обнаружить, что высказывание G(F) ложно. Откуда мы знаем, что в нашей системе F мы имеем дело с натуральными, а не со сверхнатуральными числами?

В самом деле, конечного аксиоматического способа убедить­ся в том, что «числа», о которых идет речь, и есть те самые подразумеваемые натуральные числа, а не какие-то посторон­ние «сверхнатуральные», не существует^⁵'. Однако, в некотором смысле, в этом и состоит вся суть гёделевского рассуждения. Неважно, какую именно схему аксиом формальной системы F мы построим, пытаясь охарактеризовать натуральные числа, одних лишь правил системы F будет недостаточно, чтобы определить, является ли высказывание G (F) действительно истинным или же ложным. Полагая систему F непротиворечивой, мы знаем, что в высказывании G (F) подразумевается все же наличие некоего истинного смысла. Это, однако, происходит лишь в том случае, если символы, составляющие в действительности формальное выражение, обозначаемое «G (F)», имеют подразумеваемые зна­чения. Если эти символы интерпретировать как-либо иначе, то полученная в результате интерпретация «G(F)>> вполне может оказаться ложной.

Для того чтобы разобраться, откуда берутся все эти дву­смысленности, рассмотрим новые формальные системы F* и F**, где F* получается путем присоединения к аксиомам системы F высказывания G (F), a F** — путем аналогичного присоединения высказывания ~ G (F). Если система F обоснована, то обе систе­мы F* и F** непротиворечивы (т. к. высказывание G(F) истинно, а ~ G (F) из правил системы F) вывести невозможно. При этом в случае подразумеваемой (или стандартной) интерпретации символов F из обоснованности системы F следует, что система F* обоснована, а система F** — нет. Впрочем, одним из харак­терных свойств непротиворечивых формальных систем являет­ся возможность отыскания так называемых нестандартных реинтерпретаций символов таким образом, что высказывания, которые являются ложными в стандартной интерпретации, ока­зываются истинными в нестандартной; соответственно, в такой нестандартной интерпретации обоснованными могут быть систе­мы F и F**, а система F* обоснованной не будет. Можно вообра­зить, что такая реинтерпретация может повлиять на смысл логи­ческих символов (таких как «~» и «&», которые в стандартной интерпретации означают, соответственно, «не» и «и»), однако в данном случае нас занимают символы, обозначающие неопре­деленные числа («от», «у», «z», «ж'», «х"» и т.д.), и значения применяемых к ним логических кванторов (V, 3). В стандартной интерпретации символы «Vx» и «Эх» означают, соответственно, «для всех натуральных чисел х» и «существует такое натураль­ное число х, что»; в нестандартной же интерпретации эти симво­лы могут относится не к натуральным числам, а к числам какого-то иного вида с иными свойствами упорядочения (такие числа действительно можно назвать «сверхнатуральными», или даже «ультранатуральными», как это сделал Хофштадтер [200]).

Дело, однако, в том, что мы-то знаем, что такое на самом деле представляют собой натуральные числа, и для нас не со­ставит никакого труда отличить от каких-то непонятных сверхна­туральных чисел. Натуральные числа суть самые обыденные ве­щи, обозначаемые, как правило, символами 0, 1, 2, 3, 4, 5, 6, — С этой концепцией мы знакомимся еще в детском возрасте и легко отличим ее от надуманной концепции сверхнатурального числа (см. § 1.21). Есть что-то таинственное в том, что мы, по­хоже, и впрямь обладаем каким-то инстинктивным пониманием действительного смысла понятия натурального числа. Все, что мы получаем в этом смысле в детском (или уже взрослом) возра­сте, сводится к сравнительно небольшому количеству описаний понятий «нуля», «единицы», «двух», «трех» и т.д. («три апель­сина», «один банан» и т.п.), однако при этом, несмотря на всю неадекватность такого описания, мы как-то умудряемся постичь всю концепцию в целом. В некотором платоническом смысле на­туральные числа видятся своего рода категориями, обладающи­ми абсолютным концептуальным существованием, от нас никак не зависящим. И все же, несмотря на «человеконезависимость» натуральных чисел, мы оказываемся способны установить ин­теллектуальную связь с действительной концепцией натуральных чисел, опираясь лишь на неоднозначные и, на первый взгляд, неадекватные описания. С другой стороны, не существует ко­нечного набора аксиом, с помощью которого можно было бы провести четкую границу между множеством натуральных чисел и альтернативным ему множеством так называемых «сверхнату­ральных» чисел.

Более того, такое специфическое свойство всей совокупно­сти натуральных чисел, как их бесконечное количество, мы так­же можем каким-то образом воспринимать непосредственно, то­гда как система, действие которой ограничено точными конечны­ми правилами, не способна отличить данную конкретную беско­нечность натуральных чисел от других возможных («сверхнату­ральных») вариантов. Мы же легко понимаем бесконечность, ха­рактеризующую натуральные числа, пусть и обозначаем ее про­сто точками «...» —

«0, 1,2,3,4,5,6,...»,

либо сокращением «и т. д.»—

«ноль, один, два, три и т. д.».

Нам не нужно объяснять на языке каких-то точных правил, что именно представляет собой натуральное число. В этом смысле можно считать, что нам повезло, так как такое объяснение дать невозможно. Как только нам приблизительно укажут верное на­правление, мы тут же обнаруживаем, что уже откуда-то знаем, что это за штука такая — натуральное число!

Возможно, некоторые читатели знакомы с аксиомами Пеано для арифметики натуральных чисел (об арифметике Пеано я вкратце упоминал в §2.7), и, возможно, теперь эти читатели находятся в некотором недоумении: почему же аксиомы Пеано не да­ют адекватного определения натуральных чисел. Согласно опре­делению Пеано, мы начинаем ряд натуральных чисел с символа О и затем добавляем слева особый «оператор следования», обо­значаемый S и осуществляющий простое прибавление единицы к числу, над которым совершается действие, т. е. I определяется как SO, 2 как S1 или SSO и т. д. В качестве правил мы располагаем следующими утверждениями: если Sa=Sb, то а=Ь; и ни при ка­ком х число 0 нельзя записать в виде Sx (последнее утверждение служит для характеристики числа 0). Кроме того, имеется «прин­цип индукции», согласно которому некое свойство чисел (ска­жем, Р) должно быть истинным в отношении всех чисел п, если оно удовлетворяет двум условиям: (i) если истинно Р(п), то для всех п истинно также и Р (Sn); (ii) P (0) истинно. Сложности на­чинаются, когда дело доходит до логических операций, символы которых V и 3 в стандартной интерпретации означают, соответ­ственно, «для всех натуральных чисел...» и «существует такое натуральное число..., что». В нестандартной интерпретации смысл этих символов соответствующим образом изменяется, так что они квантифицируют уже не натуральные числа, а «числа» какого-то другого типа. Хотя математические спецификации Пе­ано, задающие оператор следования S, действительно описы­вают отношение упорядочения, отличающее натуральные числа от разных прочих «сверхнатуральных» чисел, эти определения невозможно записать в терминах формальных правил, которым удовлетворяют кванторы V и 3. Для того чтобы передать смысл математических определений Пеано, необходимо перейти к так называемой «логике второго порядка», в которой кванторы ти­па V и 3 также вводятся, но только теперь они оперируют не над отдельными натуральными числами, а над множествами (бесконечными) натуральных чисел. В «логике первого порядка» арифметики Пеано кванторы оперируют над отдельными числа­ми, и в результате получается формальная система в обычном смысле этого слова. Логика же второго порядка нам формальной системы не дает. В случае строгой формальной системы вопрос о правильности применения правил системы решается чисто ме­ханическими (т. е. алгоритмическими) способами — в сущности, именно это свойство формальных систем и послужило причиной их рассмотрения в настоящем контексте. В рамках логики второ­го порядка упомянутое свойство не работает.

Многие ошибочно полагают (в духе приведенных в возра­жении Q16 соображений), что из теоремы Гёделя следует суще­ствование множества различных арифметик, каждая из которых в равной степени обоснована. Соответственно, та частная ариф­метика, которую мы, возможно, по чистой случайности избра­ли для своих нужд, определяется просто какой-то произволь­но взятой формальной системой. В действительности же теоре­ма Гёделя показывает, что ни одна из этих формальных систем (будучи непротиворечивой) не может быть полной; поэтому (как доказывается далее) к ней можно непрерывно добавлять какие угодно новые аксиомы и получать всевозможные альтернатив­ные непротиворечивые системы, которыми при желании можно заменить ту, в рамках которой мы работаем в настоящий момент. Эту ситуацию нередко сравнивают с той, что сложилась некогда с евклидовой геометрией. На протяжении двадцати одного ве­ка люди верили, что евклидова геометрия является единственно возможной геометрией. Но, когда в восемнадцатом веке сразу несколько великих математиков (таких как Гаусс, Лобачевский и Бойяи) показали, что существуют в равной степени возмож­ные альтернативы общепринятой геометрии, геометрии пришлось отступить с абсолютных позиций на произвольные. Аналогично, нередко можно услышать, будто Гёдель показал, что арифметика также представляет собой предмет произвольного выбора, при этом один набор непротиворечивых аксиом оказывается ничуть не хуже любого другого.

Однако подобная интерпретация того, что доказал Гёдель, абсолютно неверна. Согласно Гёделю, само по себе понятие фор­мальной системы аксиом не подходит для передачи даже самых элементарных математических понятий. Когда мы употребляем термин «арифметика» без дальнейших пояснений, мы подразу­меваем обычную арифметику, которая работает с обычными на­туральными числами О, 1, 2, 3, 4, ... (и, быть может, с их от­рицаниями), а вовсе не со «сверхнатуральными» числами, что бы это понятие ни означало. Мы можем, если пожелаем, иссле­довать свойства формальных систем, и это, конечно же, станет ценным вкладом в процесс математического познания. Однако такое предприятие несколько отличается от исследования обыч­ных свойств обычных натуральных чисел. В некотором отноше­нии данная ситуация весьма напоминает ту, что сложилась в по­следнее время с геометрией. Изучение неевклидовых геометрий интересно с математической точки зрения, да и сами геометрии имеют ряд важных областей применения (например, в физике, см. НРК, глава 5, особенно рис. 5.1 и 5.2, а также §4.4), но, когда термин «геометрия» используется в обычном языке (в отличие от жаргона математиков или физиков-теоретиков), подразумевает­ся, как правило, обычная евклидова геометрия. Однако имеется и разница: то, что логик может назвать «евклидовой геометрией», действительно можно определить (с некоторыми оговорками^) через определенную формальную систему, тогда как обычную «арифметику», как показал Гёдель, определить таким образом нельзя.

Гёдель доказал не то, что математика (в особенности ариф­метика) — это произвольные поиски, направление которых опре­деляется прихотью Человека; он доказал, что математика — это нечто абсолютное, и в ней мы должны не изобретать, но откры­вать (см. § 1.17). Мы открываем, что такое натуральные числа и без труда отличаем их от любых сверхнатуральных чисел. Гёдель показал, что ни одна система «искусственных» правил не способ­на сделать это за нас. Такая платоническая точка зрения была существенна для Гёделя, не менее существенной она будет и для нас в последующих рассуждениях (§8.7).

Q17. Допустим, что формальная система F предна­значена для представления тех математических истин, что, в принципе, доступны человеческому ра­зуму. Не можем ли мы обойти проблему невозмож­ности формального включения в систему F гёделевского высказывания G (F), включив вместо него что-либо, имеющее смысл G(F), воспользовавшись при этом новой интерпретацией смысла символов системы F?

Определенные способы представления примененного к F гёделевского доказательства в рамках формальной системы F (до­статочно обширной) действительно существуют, коль скоро но­вый, реинтерпретированный, смысл символов системы F пола­гается отличным от исходного смысла символов этой системы. Однако если мы пытаемся таким образом интерпретировать си­стему F как процедуру, с помощью которой разум приходит к тем или иным математическим выводам, то подобный подход являет­ся не чем иным, как шулерством. Если мы намерены толковать мыслительную деятельность исключительно в рамках системы F, то ее символы не должны изменять свой смысл «на полпути». Если же мы принимаем, что мыслительная деятельность может содержать что-то помимо операций самой системы F — а именно, изменение смысла символов, — то нам необходимо знать и пра­вила, управляющие подробным изменением. Либо эти правила окажутся неалгоритмическими, и это сыграет в пользу 'S, либо для них найдется какая-то конкретная алгоритмическая проце­дура, и тогда нам следовало бы изначально включить эту про­цедуру в нашу систему «F» — обозначим ее через F⁺ — с тем, чтобы она представляла собой полную совокупность процедур, обусловливающих наши с вами понимание и проницательность, а значит, необходимости в изменении смысла символов не воз­никло бы вовсе. В последнем случае вместо гёделевского вы­сказывания G(F) из предыдущего рассуждения нам предстоит разбираться уже с высказыванием G(F⁺), так что ничего мы в результате не выигрываем.

Q18. Даже в такой простой системе, как арифметика Пеано, можно сформулировать теорему, интерпретация которой имеет следующий смысл: «система F обоснована» следовательно «высказывание G (F) истинно». Разве это не все, что нам нужно от теоремы Гёделя? Значит, теперь, полагая обоснованной какую угод­но формальную систему F, мы вполне можем по­верить и в истинность ее гёделевского высказыва­ния — при условии, разумеется, что мы готовы при­нять арифметику Пеано, разве не так?

Подобную теорему⁽⁷⁾ действительно можно сформулировать в рамках арифметики Пеано. Точнее (поскольку мы не можем в пределах какой бы то ни было формальной системы должным образом выразить понятие «обоснованности» или «истинности», как это следует из знаменитой теоремы Тарского), мы, в сущно­сти, формулируем более сильный результат:

«система F непротиворечива» следовательно «высказывание G (F) истинно»,

либо иначе:

«система F -непротиворечива» следовательно «высказывание f2 (F) истинно».

Из этих высказываний следует вывод, необходимый для Q18, по­скольку если система F обоснована, то она, разумеется, непроти­воречива или омега-непротиворечива, в зависимости от обстоя­тельств. Понимая смысл присутствующего здесь символизма, мы и в самом деле можем поверить в истинность высказывания G (F) на основании одной лишь веры в обоснованность системы F. Это, впрочем, мы уже приняли. Если понимать смысл, то действитель­но возможно перейти от F к G (F). Сложности возникнут лишь к том случае, если нам вздумается исключить необходимость ин­терпретаций и сделать переход от F к G (W) автоматическим. Будь это возможно, мы смогли бы автоматизировать общую про­цедуру «гёделизации» и создать алгоритмическое устройство, ко­торое действительно будет содержать в себе все, что нам нужно от теоремы Гёделя. Однако такой возможности у нас нет — захоти мы добавить эту предполагаемую алгоритмическую процедуру в какую угодно формальную систему F, выбранную нами в каче­стве отправной, в результате просто-напросто получилась бы, по сути, некоторая новая формальная система F", а ее гёделевское высказывание G'(F^tJ) оказалось бы уже за ее рамками. Таким образом, согласно теореме Гёделя, какой-то аспект понимания всегда остается «за нами», независимо от того, какая доля его оказалась включена в формализованную или алгоритмическую процедуру. Это «гёделево понимание» требует постоянного со­отнесения с действительным смыслом символов какой бы то ни было формальной системы, к которой применяется процедура Гёделя. В этом смысле ошибка Q18 весьма похожа на ту, что мы обнаружили, комментируя возражение Q17. С невозможностью автоматизации процедуры гёделизации также тесно связаны рас­суждения по поводу Q6 и Q19.

В возражении Q J 8 присутствует еще один аспект, который стоит рассмотреть. Представим себе, что у нас есть обоснован­ная формальная система Н, содержащая арифметику Пеано. Те­орема, о которой говорилось в Q18, окажется среди следствий системы Н, а частным ее примером, применимым к конкретной системе F (т. е., собственно, Н), будет теорема системы Н. Таким образом, можно сформулировать один из выводов формальной системы И:

«система H обоснована» следовательно «высказывание G (H) истинно»;

Или точнее, скажем так

«система Н непротиворечива» следовательно «высказывание G(Н) истинно».

Если говорить о реальном смысле этих утверждений, то из них, в сущности, следует, что высказывание G (H) также утверждает­ся системой. А так как (что касается первого из двух вышеприве­денных утверждений) истинность любого производимого систе­мой Н утверждения, во всяком случае, обусловлена допущением, что система И обоснована, то получается, что если система Н утверждает нечто, явно обусловленное ее собственной обосно­ванностью, то она вполне может утверждать это напрямую. (Из утверждения «если мне можно верить, то X истинно» следует более простое утверждение, исходящее из того же источника: «X истинно».) Однако в действительности обоснованная фор­мальная система Н не может утверждать истинность высказы­вания б? (И), что является следствием ее неспособности утвер­ждать собственную обоснованность. Более того, как мы видим, она не может включать в себя и смысл символов, которыми опе­рирует. Те же факты годятся и для иллюстрации второго утвер­ждения, причем в этом случае ко всему прочему добавляется и некоторая ирония: система Н не способна утверждать собствен­ную непротиворечивость лишь в том случае, если она действи­тельно непротиворечива, если же формальная система непро­тиворечивой не является, то подобные ограничения ей неведо­мы. Противоречивая формальная система Н может утверждать (в качестве «теоремы») вообще все, что она в состоянии сформу­лировать! Она вполне может, как выясняется, сформулировать и утверждение: «система Н непротиворечива». Формальная систе­ма (достаточно обширная) утверждает собственную непротиво­речивость тогда и только тогда, когда она противоречива!.

QI9. Почему бы нам просто не учредить процеду­ру многократного добавления высказывания G (F) к любой системе F, какой мы в данным момент поль­зуемся, и не позволить этой процедуре выполняться бесконечно?

Когда нам дана какая-либо конкретная формальная систе­ма F, достаточно обширная и полагаемая обоснованной, мы в состоянии понять, как добавить к ней высказывание G (F) в ка­честве новой аксиомы и получить тем самым новую систему fi , которая также будет считаться обоснованной. (Для согласования обозначений в последующем изложении систему F можно так­же обозначить через fq.) Теперь мы можем добавить к систе­ме fi высказывание G(Fi), получив в результате новую систе­му ¥2, также, предположительно, обоснованную. Повторив дан­ную процедуру, т. е. добавив к системе F2 высказывание G (F₂), получим систему fs и т. д. Приложив еще совсем немного усилий, мы непременно сообразим, как построить еще одну формальную систему ¥_ш, аксиомы которой позволят нам включить в систему в качестве дополнительных аксиом для F все бесконечное мно­жество высказываний {G (F₀), G (Fi), G (F₂), G (F₃), ...}. Оче­видно, что система ¥_ш также будет обоснованной. Этот процесс можно продолжить и дальше: к системе ¥_ш добавляется выска­зывание G(F_W), в результате чего получается система F_w+1, к которой затем добавляется высказывание G (F_w+i), что дает си­стему ¥_ш+2, и т.д. Далее, как и в предыдущий раз, мы можем построить формальную систему ¥_ш2 (= ¥_ш+ш), включив в нее весь бесконечный набор соответствующих аксиом, каковая система опять-таки окажется очевидно обоснованной. Добавлением к ней высказывания G (F^), получим систему F_w2+i и т. д., а потом по­строим новую систему F_w3(= ¥_ш2+ш}, включив в нее опять-таки бесконечное множество аксиом. Повторив всю вышеописанную процедуру, мы сможем получить формальную систему ¥_ш±, после следующего повтора — систему ¥_ш5 и т. д. Еще чуть-чуть потру­диться, и мы обязательно увидим, как можно включить уже это множество новых аксиом {G (F^), G (F^), G (F_w3), G (F^), ...} в новую формальную систему ¥_шз(= ¥_шш). Повторив всю про­цедуру, мы получим новую систему ¥_шг_+шз, затем — систе­му ¥_Ш2_+Ш2_+Ш2 и т.д.; в конце концов, когда мы сообразим, как связать все это вместе (разумеется, и на этот раз не без неко­торого напряжения умственных способностей), наши старания приведут нас к еще более всеобъемлющей системе ¥_шз, которая также должна быть обоснованной.

Читатели, которые знакомы с понятием канторовых транс­финитных ординалов, несомненно, узнают индексы, обычно используемые для обозначения таких чисел. Тем же, кто от по­добных вещей далек, не стоит беспокоиться из-за незнания точ­ного значения этих символов. Достаточно сказать, что описан­ную процедуру «гёделизации» можно продолжить и далее: мы получим формальные системы F_w<, F^s, ..., после чего придем к еще более обширной системе F_w«/, затем процесс продол­жается до еще больших ординалов, например, ш^ш" и т. д. — до тех пор, пока мы все еще способны на каждом последую­щем этапе понять, каким образом систематизировать все мно­жество гёделизации, которые мы получили на данный момент. В этом и заключается основная проблема: для упомянутых на­ми «усилий, трудов и напряжений» требуется соответствую­щее понимание того, как должно систематизировать предыду­щие гёделизации. Эта систематизация выполнима при условии, что достигаемый к каждому последующему моменту этап бу­дет помечаться так называемым рекурсивным ординалом, что, в сущности, означает, что должен существовать определенный алгоритм, способный такую процедуру генерировать. Однако ал­горитмической процедуры, которую можно было бы заложить заранее и которая позволила бы выполнить описанную систе­матизацию для всех рекурсивных ординалов раз и навсегда, просто-напросто не существует. Нам снова придется прибегать к пониманию.

Вышеприведенная процедура была впервые предложена Аланом Тьюрингом в его докторской диссертации (а опубликова­на в [367])'⁸); там же Тьюринг показал, что любое истинное Щ-высказывание можно, в некотором смысле, доказать с помощью многократной гёделизации, подобной описанной нами. (См. так­же [116].) Впрочем, воспользоваться этим для получения меха­нической процедуры установления истинности ГЦ -высказываний нам не удастся по той простой причине, что механически система­тизировать гёделизацию невозможно. Более того, невозможность «автоматизации» процедуры гёделизации как раз и выводится из результата Тьюринга. А в §2.5 мы уже показали, что об­щее установление истинности (либо ложности) ГЦ-высказываний невозможно произвести с помощью каких бы то ни было алго­ритмических процедур. Так что, в поисках систематической про­цедуры, не доступной тем вычислительным соображениям, ко­торые мы рассматривали до настоящего момента, многократная гёделизация нам ничем помочь не сможет. Таким образом, для вывода £f возражение Q19 угрозы не представляет.

••(;->Ж

Q20. Реальная ценность математического понимания состоит, безусловно, не в том, что благодаря ему мы способны выполнять невычислимые действия, а в том, что оно позволяет нам заменить невероятно сложные вычисления сравнительно простым пониманием? Иными словами, разве не правда, что, используя разум, мы, скорее, «срезаем углы» в смысле теории сложности, а вовсе не «выскакиваем» за пределы вычислимого?

Я вполне готов поверить в то, что на практике интуиция математика гораздо чаще используется для «обхода» вычисли­тельной сложности, чем невычислимости. Как-никак математи­ки по природе своей склонны к лени, а потому зачастую стара­ются изыскать всяческие способы избежать вычислений (пусть даже им придется в итоге выполнить значительно более слож­ную мыслительную работу, нежели потребовало бы собственно вычисление). Часто случается так, что попытки заставить ком­пьютеры бездумно штамповать теоремы даже умеренно слож­ных формальных систем быстро загоняют эти самые компьюте­ры в ловушку фактически безнадежной вычислительной слож­ности, тогда как математик-человек, вооруженный пониманием смысла, лежащего в основе правил такой системы, без особо­го труда получит в рамках этой системы множество интересных результатов⁽⁹⁾.

Причина того, что в своих доказательствах я рассматривал не сложность, а невычислимость, заключается в том, что только с помощью последней мне удалось сформулировать необходимые для доказательства сильные утверждения. Не исключено, что в работе большинства математиков вопросы невычислимости иг­рают весьма незначительную роль, если вообще играют. Однако суть не в этом. Я глубоко убежден, что понимание (в частности, математическое) представляет собой нечто, недоступное вычис­лению, а одной из немногих возможностей вообще подступиться ко всем этим вопросам является как раз доказательство Гёделя (—Тьюринга). Никто не отрицает, что наши математические инту­иция и понимание нередко используются для получения результатов, достижимых, в принципе, и вычислительным путем, — но и здесь слепое, не отягощенное пониманием, вычисление может оказаться неэффективным настолько, что попросту не будет работать (см. §3.26). Однако рассмотрение всех таких случаев представляется мне неизмеримо более сложным подходом, неже­ли обращение к общей невычислимости.

 

Как бы то ни было, высказанные в возражении Q20сообра­жения, пусть и справедливые, все же ни в коей мере не противо­речат выводу Sf.

 

Примечания

1. Кому-то, возможно, покажется, что это совершенно «очевидно» и уж никак не может служить предметом спора среди математиков! Проблема, однако, существует, и возникает она в связи с понятием «существования» применительно к большим бесконечным множе­ствам. (См., например, [349], [328], [265].) На примере парадокса Рассела мы уже убедились, что в таких вопросах необходимо про­являть особую осторожность.
   Согласно одной точке зрения, множество не считается необходи­мо существующим, если нет четкого правила (не обязательно вы­числимого), устанавливающего, какие элементы в это множество следует включать, а какие — нет. Как раз этого правила аксиома выбора нам и не предоставляет, поскольку в ней нет правила, опре­деляющего, какой элемент следует взять из каждого множества со­вокупности. (Некоторые из следствий аксиомы выбора интуитивно не понятны и почти парадоксальны. Вероятно, в этом и состоит одна из причин возникновения разногласий по данному вопросу. Более того, я не совсем уверен, какой позиции придерживаюсь в этом отношении я сам!)
2. В заключительной главе своей книги, написанной в 1966 году, Коэн подчеркивает, что, хотя он и показал, что континуум-гипотеза яв­ляется НЕРАЗРЕШИМОЙ в рамках процедур системы ZF, вопрос о том, является ли она действительно истинной, был оставлен им без внимания, — и выдвигает некоторые предположения отно­сительно того, каким образом этот вопрос можно действительно решить То есть Коэн, со всей очевидностью, не считает, что выбор между принятием или непринятием континуум-гипотезы есть пред­мет абсолютно произвольный. Это расходится с нередко выска­зываемым относительно следствий из результатов Гёделя—Коэна мнением, суть которого сводится к тому, что существуют многочис­ленные «альтернативные теории множеств», для математики в рав­ной степени «справедливые». Такие замечания свидетельствуют о том, что Коэн, подобно Гёделю, является подлинным платонистом, для которого вопросы математической истины ни в коем случае не произвольны, но абсолютны. Очень похожих взглядов придержи­ваюсь и я, см. §8.7.
3. См., например, [201], [37].
4. См., например, различные комментарии, приведенные в Behavioral and Brain Sciences, 13 (1990), 643-705.
5. Терминология была предложена Хофштадтером в [201]. Согласно «другой» теореме Гёделя — так называемой теореме о полноте, — подобные нестандартные модели существуют всегда.
6. Вообще говоря, это зависит от того, какие именно утверждения считать частью так называемой «евклидовой геометрии». Если пользоваться обычной терминологией логиков, то система «евклидовой геометрии» включает только утверждения некоторого частного вида, причем оказывается, что истинность или ложность этих утвер­ждений можно определить с помощью алгоритмической процедуры, отсюда и утверждение, что евклидову геометрию можно описать с помощью формальной системы. Однако в других интерпретациях обычная «арифметика» тоже могла бы считаться частью «евклидовой геометрии», что допустило бы классы утверждений, которые невозможно разрешить алгоритмическим путем. То же самое про­изошло бы, если бы мы рассмотрели задачу о замощении плоскости полиомино как составляющую евклидовой геометрии, что, казалось
   бы, вполне естественно. В этом смысле описать геометрию Евклида формально ничуть не проще, чем арифметику!
7. См. комментарий М.Дэвиса в [73].
8. См. также [230], [231] и [162].
9. О некоторых проблемах, с которыми сталкивались компьютерные системы, пытавшиеся самостоятельно «делать математику», можно прочесть у Д. Фридмана [123]. Отметим, что в общем случае такие системы не слишком преуспели. Они по-прежнему остро нуждают­ся в помощи человека.

ПРИЛОЖЕНИЕ А:

ГЕДЕЛИЗИРУЮЩАЯ МАШИНА ТЬЮРИНГА В ЯВНОМ ВИДЕ

Для определенности я воспользуюсь спецификациями той конкретной машины Тьюринга, которую я описал в НРК. По­дробное описание этих спецификаций… Машина Тьюринга имеет конечное число внутренних состо­яний, но производит все… При представлении на ленте натуральных чисел (будь то входные или выходные данные) иногда удобнее использовать так…

N11111000...

(где П есть пятеричная запись числа п) в точности совпадает с действием алгоритма А на последовательность

N111110 n11111000...

при любом п. Таким образом, действие предписания К сводится к тому, чтобы взять число п (записанное в пятеричном выраже­нии) и однократно его скопировать, при этом два П разделяют­ся последовательностью 111110 (та же последовательность начинает и завершает всю последовательность отметок на лен­те). Следовательно, оно воздействует на получаемую в результате ленту точно так, как на эту же ленту воздействовал бы алго­ритм А.

Явную модификацию алгоритма А, дающую такое предпи­сание К, можно произвести следующим образом. Сначала на­ходим в определении А начальную команду Ol —> X и отмечаем для себя, что это в действительности за «X». Мы подставим это выражение вместо «X» в спецификации, представленной ниже. Один технический момент: следует, помимо прочего, положить, чтобы алгоритм А был составлен таким образом, чтобы машина, после активации команды Ol —* X, никогда больше не перешла во внутреннее состояние 0 алгоритма А. Это требование ни в коей мере не влечет за собой каких-либо существенных ограни­чений на форму алгоритма. (Ноль можно использовать только в командах-пустышках.)

Затем при определении алгоритма А необходимо устано­вить общее число N внутренних состояний (включая и состоя­ние 0, т. е. максимальное число внутренних состояний А будет равно N — 1). Если в определении А нет завершающей коман­ды вида (N — 1)1 —> Y, то в конце следует добавить команду-пустышку (N — 1)1 —» OUR. Наконец, удалим из определения А команду Ol —* X и добавим ее к приводимому ниже списку ма­шинных команд, а каждый номер внутреннего состояния, фигури­рующий в этом списке, увеличим на N (символом 0 обозначено результирующее внутреннее состояние 0, а символом «X» в за­писи «11 -> X» представлена команда, которую мы рассмотрели выше). (В частности, первые две команды из списка примут в данном случае следующий вид: 01->N1R, N0->(N+4)0R.)

o1->01R, 00->40R, 01->01R, 10-> 21R, 11->X, 20->31R, 21->o0R, 30->551R,
31->o0R, 40->40R, 41->51R, 50->40R, 51->61R, 60->40R, 61->71R, 70->40R,
71->81R, 80->40R, 81->91R, 90->100R, 91->o0R, 100->111R, 101->o0R, 110->121R,
111->120R, 120->131R, 121->130R, 130->141R, 131->140R, 140->151R, 141->10R, 150->00R,
151->o0R, 160->170L, 161->161L, 170->170L, 171->181L, 180->170L, 181->191L, 190->170L,
191->201L, 200->170L, 201->211L, 210->170L, 211->221L, 220->220L, 221->231L, 230->220L,
231->241L, 240->220L, 241->251L, 250->220L, 251->261L, 260->220L, 261->271L, 270->321R,
271->281L, 280->330R, 281->291L, 290->330R, 291->301L, 300->330R, 301->311L, 310->330R,
311->110R, 320->340L, 321->321R, 330->350R, 331->331R, 340->360R, 341->340R, 350->371R,
351->350R, 360->360R, 361->381R, 370->370R, 371->391R, 380->360R, 381->401R, 390->370R,
391->411R, 400->360R, 401->421R, 410->370R, 411->431R, 420->360R, 421->441R, 430->370R,
431->451R, 440->360R, 441->461R, 450->370R, 451->471R, 460->480R, 461->461R, 470->490R,
471->471R, 480->480R, 481->490R, 490->481R, 491->501R, 500->481R, 501->511R, 510->481R,
511->521R, 520->481R, 521->531R, 530->541R, 531->531R, 540->160L, 541->o0R, 550->531R.

Теперь мы готовы точно определить предельную длину пред­писания К, получаемого путем вышеприведенного построения, как функцию от длины алгоритма А. Сравним эту «длину» со «степенью сложности», определенной в § 2.6 (в конце коммента­рия к возражению Q8). Для некоторой конкретной машины Тью­ринга Т_т (например, той, что выполняет вычисление А) эта ве­личина равна количеству знаков в двоичном представлении чис­ла т. Для некоторого конкретного машинного действия Т_т(п) (например, выполнения предписания К) эта величина равна ко­личеству двоичных цифр в большем из чисел тип. Обозначим через а и к количество двоичных цифр в а и ' k' соответственно, где

А = Т_а и K = T_k,(=C_k).

Поскольку алгоритм А содержит, как минимум, 2N — 1 команд (учитывая, что первую команду мы исключили) и поскольку для каждой команды требуется, по крайней мере, три двоичные циф­ры, общее число двоичных цифр в номере его машины Тьюринга а непременно должно удовлетворять условию

В вышеприведенном дополнительном списке команд для К есть 105 мест (справа от стрелок), где к имеющемуся там числу сле­дует прибавить N. Все получаемые при этом числа не превыша­ют N + 55, а потому их расширенные двоичные представления содержат не более 2 Iog₂ (N + 55) цифр, в результате чего общее количество двоичных цифр, необходимых для дополнительного определения внутренних состояний, не превышает 210 Iog₂ (N + + 55). Сюда нужно добавить цифры, необходимые для добавоч­ных символов 0, 1, R и L, что составляет еще 527 цифр (включая одну возможную добавочную «команду-пустышку» и, учитывая, что мы можем исключить шесть символов 0 по правилу, согласно которому 00 можно представить в виде 0). Таким образом, для определения предписания К требуется больше двоичных цифр, чем для определения алгоритма А, однако разница между этими двумя величинами не превышает 527 + 210 Iog₂ (N -f 55):

к < а + 527 + 210 Iog₂ (N + 55).

Применив полученное выше соотношение , получим (учитывая, что 210 Iog₂ 6 > 542)

к < а - 15 + 210 Iog₂ (a + 336).

Затем найдем степень сложности г? конкретного вычисле­ния Ck (k), получаемого посредством этой процедуры. Вспомним, что степень сложности машины Т_т (п) определяется как коли­чество двоичных цифр в большем из двух чисел т, п. В данной ситуации Ck = Tk, так что число двоичных цифр в числе «т» этого вычисления равно к. Для того, чтобы определить, сколько двоичных цифр содержит число «п» этого вычисления, рассмот­рим ленту, содержащую вычисление Ck (k). Эта лента начинается с последовательности символов 111110, за которой следует двоичное выражение числа k', и завершается последовательно­стью 11011111. В соответствии с предложенным в НРК соглашением всю эту последовательность (без последней циф­ры) следует читать как двоичное число; эта операция дает нам номер «п», который присваивается ленте машины, выполняющей вычисление Т_т (п). То есть число двоичных цифр в данном кон­кретном номере «п» равно к + 13, и, следовательно, число к + 13 совпадает также со степенью сложности г/ вычисления Ck (k), .благодаря чему мы можем записать г) = к + 13 < а — 2 4-+ 210 Iog₂ (а + 336), или проще:

?7<a + 2101og₂(a-l-336).

Детали вышеприведенного рассуждения специфичны для данного конкретного предложенного еще в НРК способа кодиро­вания машин Тьюринга, и при использовании какого-либо иного кодирования они также будут несколько иными. Основная же идея очень проста. Более того, прими мы формализм Х-исчисления, вся операция оказалась бы, в некотором смысле, почти тривиальной. (Достаточно обстоятельное описание Л-исчисления Черча можно найти в НРК., конец главы 2; см. также [52].) Пред­положим, например, что алгоритм А определяется некоторым А-оператором А, выполняющим действие над другими оператора­ми Р и Q, что выражается в виде операции (АР) Q. Оператором Р здесь представлено вычисление С_р, а оператором Q — число q. Далее, оператор А должен удовлетворять известному требова­нию, согласно которому для любых Р и Q должно быть истинным следующее утверждение:

Если завершается операция (АР) Q, то операция PQ не завершается.

Мы без труда можем составить такую операцию Л-исчисления, которая не завершается, однако этот факт невозможно устано­вить посредством оператора А. Например, положим

К = Ах.[(Ах)х], т.е. KY = (AY)Y для любого оператора Y. Затем рассмотрим

А-операцию

KK.

Очевидно, что эта операция не завершается, поскольку КК = = (АК) К, а завершение последней операции означало бы, что операция КК не завершается по причине принятой нами приро­ды оператора А. Более того, оператор А не способен установить этот факт, потому что операция (АК) К не завершается. Если мы полагаем, что оператор А обладает требуемым свойством, то мы также должны предположить, что операция КК не завершает­ся.

Отметим, что данная процедура дает значительную эконо­мию. Если записать операцию КК в виде

КК = Ау.(уу)(Ах.[(Ах)х]),

то становится ясно, что число символов в записи операции КК всего на 16 больше аналогичного числа символов для алгорит­ма А (если пренебречь точками, которые в любом случае избы­точны)!

Строго говоря, это не совсем законно, поскольку в выраже­нии для оператора А может также появиться и символ «х», и с этим нам придется что-то делать. Можно усмотреть сложность и в том, что генерируемое такой процедурой незавершающееся вычисление нельзя считать операцией над натуральными числами (поскольку вторая К в записи КК «числом» не является). Вообще говоря, А-исчисление не вполне подходит для работы с явными численными операциями, и зачастую бывает довольно сложно понять, каким образом ту или иную заданную алгоритмическую процедуру, применяемую к натуральным числам, можно выра­зить в виде операции А-исчисления. По этим и подобным при­чинам обсуждение с привлечением машин Тьюринга имеет, как нам представляется, более непосредственное отношение к теме нашего исследования и достигает требуемого результата более наглядным путем.

О НЕВЫЧИСЛИМОСТИ В МАТЕМАТИЧЕСКОМ МЫШЛЕНИИ

Гёдель и Тьюринг

Прежде всего следует указать на то, что тщательно вы­страивая последовательности умозаключений (вполне, заметим, осознанных) с целью установления… 'Здесь я предполагаю, что если процедура А вообще завершается, то это…  

О психофизи(ологи)ческой проблеме

Комментарии Ю.П.Карпенко к книге Р.Пенроуза: Тени ума: В поисках потерянной науки о сознании.   Как мы видим, выдающийся английский физик-теоретик Роджер Пенроуз полагает, что феномен сознания должен описываться на…

Р.Пенроуз. Тени ума: В поисках потерянной науки о сознании.

PENROSE R. Shadows of the mind: A search for the missing science of consciousness. - Oxford, 1994. - XVI, 457 p.

Реферат подготовлен Ю.П.Карпенко   В реферируемой книге крупного английского математика и физика-теоретика Роджера Пенроуза развиваются идеи его…

Http://hotmix.narod.ru