«Том 22. Сон разума. Математическая логика и ее парадоксы»

Том 22. Сон разума. Математическая логика и ее парадоксы (fb2) - Том 22. Сон разума. Математическая логика и ее парадоксы 1448K скачать: (fb2) - (epub) - (mobi) - Хавьер Фресан

Хавьер Фресан «Мир математики» № 22 «Сон разума Математическая логика и ее парадоксы»

Посвящается Хосе Антонио Паскуалю и Розе Наварро Дюран

Предисловие

Супруги спорят между собой: «Ты всегда мне перечишь», — говорит жена. «Это не так», — возражает муж. «Видишь? Ты сам же это подтверждаешь», — снова критикует его жена. «Милая, ты права, я всего лишь тебе перечу», — признает муж в попытках положить конец спору. «Вот! Ты сам в этом признался!» — кричит жена и хлопает дверью. От подобных сцен не застрахован ни один, даже самый счастливый брак. Если бы философ и математик Бертран Рассел никогда не переживал подобные моменты, он бы не женился четыре раза. И все же его семейные ссоры, должно быть, завершались совершенно не так, как у других людей: после фразы «Ты сам же это подтверждаешь» Рассел, должно быть, помолчал несколько секунд и, сказав: «Да, дорогая, это очень интересно», закрылся в своем кабинете.

Зачем? Чтобы подумать об утверждениях, которые описывают сами себя, об истинном и ложном и осознать парадокс, который ставил под сомнение то, что математика последних двух тысяч лет является завершенным воплощением «сна разума».

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

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

Мы решили не ограничиваться нулями и единицами машин Тьюринга, а попытались сделать еще один шаг вперед и описать множество оттенков одного из последних «снов разума» — нечеткой логики.

Я хочу поблагодарить редакцию издательской компании RBA за предложение написать такую книгу. Именно слова «изложить популярным языком», упомянутые в одном из писем редактора, побудили меня начать каждую главу с небольшой художественной зарисовки. Без историй моей подруги Лауры Касильес, этой Шахерезады XXI века, я никогда не смог бы связать нечеткую логику и десерт в японском ресторане. Эпиграф к пятой главе родился благодаря Патрисии Фернандес де Лис, очарованной личностью Алана Тьюринга. Подробные комментарии Хесуса Фресана, Давида Гарсеса, Мигеля Эрнаиса, Виктории Лей Вега де Сеоане, Хавьера Мартинеса и Лус Рельо помогли мне существенно улучшить книгу.

Также я благодарен Марии Агирре Рокеро, Луису Аскарате, Ноэлю Гарридо, Хено Галарса, Марии Анхелес Леаль, Карлосу Мадриду, Хосе Марии Матеос, Гильермо Рей, Роберто Рубио, Марии Хосе Солер, Лукасу Санчесу и Микелю Тамайо за ценный вклад, который они внесли в создание этой книги.

Глава 1 Аксиоматический метод

Со времен греков говорить «математика» — значит говорить «доказательство».

Николя Бурбаки

Энтузиазм, с которым адвокат Тауринус разорвал конверт, не теряя времени на поиски ножа, сменялся разочарованием по мере того, как он строчка за строчкой читал убористо исписанные две страницы. В этом письме, полученном одним ноябрьским утром 1824 года, содержался ответ Карла Фридриха Гаусса на заявление об открытии чрезвычайной важности — доказательстве пятого постулата Евклида.

К тому времени не осталось такого раздела физики и математики, куда Гаусс, которому исполнилось почти пятьдесят, не внес бы свой вклад, за что получил титул princeps mathematicorum — «король математиков». Однако ни в одной из его работ не был затронут важнейший вопрос того времени: верен ли пятый постулат? Можно ли через точку, не лежащую на данной прямой, провести одну и только одну прямую, параллельную данной? Ответ на этот вопрос в некотором роде позволил бы понять, какую форму имеет наш мир.

История Евклида и его труда, «Начал», где он изложил свои идеи, восходит к 300 году до н. э. Именно тогда этот древнегреческий математик, о котором нам почти ничего не известно, составил учебник по геометрии, где систематизировал все знания, которые до этого из уст в уста передавались пифагорейцами и учениками Платона. В то время как над входом в Академию Платона можно было прочесть фразу «Да не войдет сюда не знающий геометрии», «Начала» Евклида были предназначены для неподготовленного читателя и помогали понять науку о формах и фигурах с помощью простейших формулировок. Чтобы сделать свой труд более понятным и одновременно подчеркнуть четкость и строгость геометрии, Евклид начал изложение с ряда определений и аксиом, из которых, запасясь терпением, логически можно было вывести любое из сотен предложений, записанных в книге. Возможно, создание никакого другого учебника не имело столь радикальных последствий для развития всей человеческой мысли на протяжении последующих двух тысяч лет.

Евклид на картине Рафаэля «Афинская школа». Греческий математик изображен в окружении учеников, с циркулем в руках.

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

Две прямые пересекаются в той части плоскости, где углы меньше двух прямых.

Возможно, что первое впечатление современного читателя будет таким же, как и у современников Евклида: пятый постулат не столь очевиден, как предыдущие, и чтобы понять его, не обойтись без карандаша и бумаги. Именно поэтому очень скоро геометры начали ставить под сомнение его принадлежность к аксиомам и пытались доказать его исходя из остальных постулатов. Однако все подобные попытки оставались безрезультатными, хотя и позволяли получить утверждения, эквивалентные пятому постулату, которые помогали лучше понять его следствия. Наиболее известные следствия пятого постулата гласят, что сумма углов треугольника равна 180°, а через точку, не лежащую на данной прямой, можно провести одну и только одну прямую, параллельную данной. Независимо от точной формулировки постулата о параллельности прямых ученые сомневались, является ли он самостоятельным относительно других постулатов или же, напротив, выводится из них с помощью искусных рассуждений и его можно исключить из списка аксиом. Через эти сомнения прошли все греческие и арабские комментаторы «Начал» и исследователи эпохи Возрождения.

Каково же было удивление Франца Адольфа Тауринуса в то ноябрьское утро, когда он, вместо того чтобы, превзойдя лучшие умы в истории, довольствоваться заслуженной славой, получил письмо, в котором Гаусс признавался, что после тридцати лет размышлений пришел к выводу: может существовать геометрия, в которой пятый постулат не выполняется. Однако эту новую, неевклидову науку следовало сохранять в тайне до тех пор, пока не будут уточнены все детали ряда теорем, которые, казалось, противоречили общепринятым убеждениям, незыблемым на протяжении двух тысячелетий. Новую геометрию не приняли бы те, кто считал, что треугольники и круги, описанные в книге природы, выглядят именно так, как их описал Евклид, и никак иначе. Ведь, подобно Аристотелю для схоластиков, Евклид был не просто человеком, но источником почти священного знания.

* * *

ДИАЛОГ ИЗ ФИЛЬМА «АГОРА»

(РЕЖИССЕР АЛЕХАНДРО АМЕНАБАР, АВТОР СЦЕНАРИЯ МАТЕО ХИЛЬ, 2009)

Гипатия: Синезий, каково первое правило Евклида?

Синезий: Почему ты спрашиваешь меня?

Гапатия: Просто ответь мне.

Синезий: «Равные одному и тому же равны и между собой».

Гипатия: Хорошо. Разве не подобны мне вы оба?

Синезий: Да.

Гипатия: А ты, Орест?

Орест: Да.

Гипатия: Хочу сказать всем, кто находится в этой комнате: у нас больше сходств, чем различий, и что бы ни произошло на улицах, мы останемся братьями и сестрами. Мы братья и сестры. Запомните, что ссоры — удел простолюдинов и рабов.

Афиша фильма «Агора», главной героиней которого является Гипатия Александрийская.

* * *

От неевклидовой геометрии — к теории относительности

Так могла бы начаться история, основанная на реальных событиях, в которой рассказывалось бы о Гауссе (1777–1855), измеряющем размеры многокилометрового треугольника, вершинами которого стали три горы в Германии. Целью эксперимента было определить, является геометрия пространства евклидовой или нет. По ходу истории к «королю математиков» присоединились бы другие действующие лица, в частности венгр Янош Бойяи (1802–1860) и русский математик Николай Лобачевский (1792–1856), которые при публикации своих открытий не испытывали таких опасений, как Гаусс.

В аристократических салонах ученые Европы восхищали бы публику, демонстрируя макеты удивительных поверхностей, на которых сумма углов треугольника была меньше 180°. Некто наверняка прервал бы одну из таких демонстраций, вскричав «Евклид умер!», а тот, кому были чужды революционные настроения, схватился бы за голову, потому что «никто не может одновременно служить двум господам: если геометрия Евклида истинна, то нужно исключить неевклидову геометрию из списка наук и поместить ее рядом с алхимией и астрологией»[1].

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

Тем не менее когда ученые обнаружили, что на некоторых поверхностях через данную точку можно провести бесконечно много прямых, параллельных одной и той же прямой, а на других поверхностях нельзя провести ни одной прямой, параллельной данной, вопрос о том, какие аксиомы являются истинными, утратил смысл. Почему постулат о параллельности прямых должен быть более истинным, чем постулаты, отрицающие его? В действительности корректность того или иного постулата будет зависеть только от того, какие объекты мы изучаем.

Альберт Эйнштейн (1879–1955) сумел извлечь пользу из сложившейся ситуации и благодаря неевклидовой геометрии решил задачу, не дававшую покоя самому Исааку Ньютону (1643–1727). Согласно закону всемирного тяготения, открытому Ньютоном в 1685 году, два тела притягиваются друг к другу с силой, которая увеличивается с ростом произведения их масс и с уменьшением квадрата расстояния между ними. Этот закон позволил описать движение планет и траекторию падения яблок с деревьев, однако важнейший вопрос по-прежнему оставался без ответа: как может Земля воздействовать на Луну, если их разделяет почти 400 тысяч километров? Действие, совершаемое на расстоянии, считалось чем-то относящимся к алхимии и ни в коем случае не могло быть принято научной школой того времени. Чтобы преодолеть это препятствие, был даже воскрешен эфир, упоминавшийся в греческой мифологии, — летучая субстанция, заполняющая промежутки в пустоте, благодаря которой сила тяготения распространяется от одного тела к другому. Однако различные эксперименты поставили под сомнение существование эфира или чего-то подобного.

И тогда на сцену вышел Эйнштейн. Любой может представить себе, что произойдет с простыней, которую натянули два человека, если в ее центр бросить мяч, однако предположить, что точно так же ведут себя планеты в космосе, смог лишь этот гениальный сотрудник патентной конторы в Берне. Тело столь большой массы, как Земля, искажает пространство вокруг себя, и гравитация есть не что иное, как мера кривизны пространства. Если маленький шарик бросить на простыню, деформированную под весом мяча, он немедленно скатится к ее центру. Аналогично, тело в состоянии свободного падения притянется к поверхности Земли в результате искажения пространства вокруг нее. Если тело находится далеко от Земли и при этом движется, как, например, Луна, то благодаря искажению пространства оно не притянется к Земле, а будет удерживаться на земной орбите. Таким образом, в той геометрии, где гравитация является мерой кривизны пространства, пятый постулат Евклида не выполняется.

Графическое изображение деформации пространства, вызванной силой земного тяготения.

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

Эйнштейн продолжал: бесполезно пытаться доказать, действительно ли через две точки можно провести только одну прямую. Все, что нам известно, — это то, что в геометрии идет речь о понятиях «точка» и «прямая линия», которые связаны следующим образом: две различные «точки» определяют единственную «прямую».

Чтобы спор об истинности аксиом имел смысл, сначала нужно установить их соответствие с реальностью: если всякий раз, когда Евклид упоминает «точку» и «прямую линию», мы будем трактовать эти понятия привычным нам способом, то аксиома «через две точки можно провести прямую» будет корректной, и мы сможем подтвердить ее истинность экспериментально. Однако ничто не указывает, что в геометрии эти понятия нужно понимать точно так же, как и в обычной жизни, — напротив, геометрия есть не более чем множество абстрактных идей и отношений между ними.

Одна из последних фотографий Альберта Эйнштейна, сделанная около 1950 года.

Рассмотрим пример, который впервые упоминается в статьях итальянского геометра Эудженио Бельтрами (1835–1900). Пусть пространство, в котором находятся объекты, заключено внутри круга (не включая его границу). Предложим следующее простое соответствие: когда Евклид говорит о «точке», мы будем представлять точки внутри круга, а когда он говорит о «прямой линии», мы будем представлять себе отрезки, начало и конец которых лежат на границе круга. В такой трактовке две «точки» определяют единственную «прямую линию» и, следовательно, первый постулат Евклида будет выполняться. Перед тем как рассмотреть пятый постулат, напомним, что две «прямые» параллельны, если они никогда не пересекаются.

Возьмем произвольную «точку» внутри круга, например его центр, и произвольную «прямую линию». Соединив «точку» с концами отрезка («прямой линии»), получим две «прямые», которые проходят через нее и параллельны исходной прямой, так как гипотетические точки пересечения этих прямых находятся на границе круга, а она не принадлежит пространству! Следовательно, в модели Бельтрами постулат о параллельности прямых не выполняется.

Неевклидова модель Эудженио Бельтрами.

Обратите внимание, что выше слова «точка» и «прямая линия» в одних случаях заключены в кавычки, а в других — нет. Таким образом мы проводим различие между абстрактными понятиями «точки» и «прямой линии», которые могут иметь различные толкования, и реальными точками и прямыми, на основе которых были определены эти понятия. Тот, кто считает, что описанная нами неевклидова модель не более чем математическая игра, возможно, изменит свою точку зрения после краткого экскурса в биологию. Расстояние, видимое человеческим глазом, в лучшем случае составляет несколько километров. Как следствие, все прямые, которые пересекаются за границей видимой нами области, выглядят для нас одинаково, а все, что мы видим вокруг себя, в достаточной мере соответствует модели, предложенной Бельтрами. В конце концов, какой будет разница между двумя прямыми, которые пересекаются в Нью-Йорке, и прямыми, которые пересекаются в Лос-Анджелесе, для европейца? Маленький мир человека не описывается законами геометрии Евклида. Однако человеческая философия не ограничивается этим маленьким миром.

Мы выбрали модель Бельтрами произвольно, из множества возможных. В том же самом пространстве мы можем назвать «прямыми» дуги окружности — в этом случае не будет выполняться первый постулат, так как две данные точки можно будет соединить неограниченным числом способов. Чтобы однозначно определить окружность, требуются три точки, и именно возможность выбрать третью точку произвольно и будет препятствовать выполнению постулата. Если в некоторых моделях первый постулат выполняется, а в других — нет, то истинность утверждения, согласно которому через две «точки» проходит единственная «прямая», зависит от значения понятий «точка» и «прямая», и задаваться вопросом о его истинности столь же нелепо, как и размышлять об истинности пророчества «В году А родится В», где читатель может заменить А и В произвольными значениями.

Пространство, в котором две разные прямые соединяют точки А и В и в котором не выполняется первый постулат Евклида.

Именно это мы имели в виду, когда говорили, что Эйнштейн очень четко понимал исключительно формальный характер геометрии. Несмотря на это его интересовали не логические отношения между понятиями, а конкретный вопрос о том, как объяснить действие сил на расстоянии, не используя понятие эфира. Для Эйнштейна «точками» были точки пространства, положение которых определялось координатами, указывающими их местоположение и момент времени, когда мы их рассматриваем. «Прямыми» для него были кратчайшие пути между двумя точками, вдоль которых движется луч света. Если для того чтобы объяснить природу пространства, физику нужно отказаться от постулата о параллельности прямых, то почему бы не сделать этого? В мае 1919 года, спустя четыре года после того, как Эйнштейн определил тяготение как меру кривизны Вселенной, экспедиции на африканский остров Принсипи удалось обнаружить, как отклоняется луч света звезд, близких к Солнцу и видимых только во время солнечных затмений. Именно эти эксперименты вкупе с теоретическими исследованиями, а не использование неевклидовой геометрии, позволили подтвердить корректность теории относительности.

Разумеется, когда Евклид работал над «Началами», он не думал о том, что его «точки» и «прямые» можно заменить чем-то другим. Для него все составляющие геометрии были наполнены физическим значением. Доказательством этому служат формулировки аксиом, которые, в частности, гласят, что для двух данных точек можно провести соединяющую их прямую, а не что для всякой пары «точек» существует единственная «прямая», их содержащая, — как мы обычно понимаем эту аксиому. Различие между двумя этими формулировками заключается в этом едва заметном переходе от точек к «точкам» и от «можно провести» к «существует». Именно этот переход привел к тому, что геометрия обрела абстрактный характер, и родилась математическая логика.

Новые системы аксиом

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

Классический пример подобного правила — modus ponens, «утверждающий модус», который заключается в следующем: «Если А, то В» и если А истинно, то В истинно. Вновь отметим, что значение правил логического вывода, как и значение аксиом, исключительно формально. Так, силлогизм: «Все люди могут летать.

Икар — человек, следовательно, он может летать» — корректен, в то время как высказывание: «Если идет дождь, земля мокрая. Земля мокрая, следовательно, прошел дождь» корректным не является. Хотя высказывание о мокрой земле после дождя выглядит разумным, а высказывание о летающих людях — совершенно абсурдным, первое высказывание корректно, а во втором перепутаны причина и следствие. Действительно, после дождя земля мокрая, однако если земля мокрая, это необязательно связано с дождем: например, по улице просто могла пройти поливальная машина. Также существует modus tollens (от лат. modus tollendo tollens — «путь исключения исключений»), который гласит, что из утверждения «Если А, то В» при ложном В выводится ложность А, как в высказывании «Если что-то неизвестно, об этом лучше промолчать. Если я говорю, то я знаю, о чем говорю».

* * *

ОБОЗНАЧЕНИЯ ОСНОВНЫХ ЛОГИЧЕСКИХ ОПЕРАЦИЙ

Структуру modus ponens и modus tollens удобнее запомнить, если записать их в виде схем, в которых посылки и заключение разделены линией. Если мы обозначим через ¬А и ¬В отрицания А и В, то есть утверждения, противоположные им по смыслу, то modus ponens и modus tollens будут описываться следующими схемами:

* * *

В общем случае правило вывода верно, когда его результат является истинным вне зависимости от толкования посылок. Так, высказывание «Если Р и Q, то R» корректно вне зависимости от значений Р, Q и R: всякий раз, когда Р и Q одновременно будут истинными, R также будет истинным. И вновь речь идет о формальном критерии, который подразумевает, например, что высказывание «Если ноль отличается от единицы и если единица равна нулю, то вы мой отец» является корректным. Так как ни в одном из возможных миров ноль не может отличаться от единицы и одновременно быть равным ей, исходные посылки никогда не будут верными. Это понимали уже схоластики, которые сформулировали выражение ех contradictione sequitur quodlibet, то есть «из противоречия следует все что угодно».

* * *

MODUS TОLLENS И ФАЛЬСИФИЦИРУЕМОСТЬ

Согласно философу Карлу Попперу (1902–1994), modus tollens — это единственное корректное правило вывода в естественных науках. Когда мы пытаемся объяснить какое-то явление, то научный метод, который Поппер назвал гипотетико-дедуктивным, заключается в том, чтобы выдвинуть гипотезу и провести эксперимент, который позволит опровергнуть ее. Если из гипотезы Н следует наблюдаемое следствие 0, которое неизменно повторяется в лабораторных условиях, то Н становится научным законом. Однако если мы не можем поочередно проверить все возможные ситуации, в которых применима наша гипотеза, то мы никогда не сможем быть уверенными в ее истинности. Чтобы быть уверенными в том, что все лебеди — белые, нужно исследовать все уголки планеты, однако достаточно увидеть всего одного черного лебедя, как это произошло с первыми поселенцами в Австралии, чтобы опровергнуть гипотезу. Этот принцип известен под названием принципа фальсифицируемости и является не чем иным, как modus tollens: «Если гипотеза Н верна, то из нее следует следствие 0. Так как мы наблюдаем противоположное 0, то гипотеза Н ложна».

Философ Карл Поппер в 1980-е годы.

* * *

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

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

Аксиомы арифметики

В свете всего вышесказанного для определения арифметики нужно прежде всего найти ее аксиомы. В конце XIX века эти поиски занимали умы многих ученых, поскольку в первой половине столетия их мечтой было описать окружающий мир, а во второй — точно определить, что же такое натуральные числа. А уже на основе этих чисел нетрудно найти определение для других видов чисел, например отрицательных или дробных: так, число —1 получается добавлением знака «минус» к натуральному числу 1 и используется, когда мы хотим указать на различие между двумя направлениями, например на шкале термометра или при движении средств на банковском счете. В свою очередь, 2/3 получается делением 2 на 3 и используется, когда одно число нельзя нацело разделить на другое. Но как определить числа, не определяемые на основе других?

Ученые давали различные ответы на этот вопрос. Георг Кантор (1845–1918) предложил определять натуральные числа как числа, описывающие количество элементов множества, однако, как вы увидите в следующей главе, это «лекарство» только ухудшило положение «больного». Неудача Кантора, несомненно, обрадовала его заклятого врага Леопольда Кронекера (1823–1891), для которого вопрос об описании натуральных чисел был закрыт с формулировкой: «Бог создал натуральные числа. Всё остальное — работа человека». Джузеппе Пеано (1858–1932) был не настолько экзальтированным и предложил новую точку зрения, которую впервые представил в 1889 году в книге под названием «Начала арифметики, изложенные новым методом». До настоящего момента, рассуждал Пеано, предпринимались попытки сначала определить натуральные числа, а затем найти аксиомы, на основе которых можно было бы доказать теоремы. Почему бы не поступить наоборот? Сначала можно составить перечень аксиом, затем определить числа как объекты, удовлетворяющие им, и, возможно, в числе этих объектов будут не только привычные нам числа.

Обложка книги Джузеппе Пеано «Начала арифметики, изложенные новым методом».

Этот хитроумный шаг позволил Пеано возвести здание арифметики на основе всего пяти аксиом, пятая из которых, известная как аксиома индукции, вновь оказалась немного сложнее остальных. В основу новой арифметики легли особое число ноль и операция, ставящая в соответствие каждому натуральному числу другое, которое называется следующим за ним. Далее этот итальянский математик предложил описать на этом языке натуральные числа как объекты, обладающие следующими свойствами:

1) ноль есть натуральное число;

2) число, следующее за натуральным, тоже является натуральным;

3) ноль не следует ни за каким натуральным числом;

4) всякое натуральное число следует только за одним натуральным числом;

5) если множество А содержит ноль и содержит следующее число для любого числа, принадлежащего этому множеству, то А содержит все натуральные числа.

Первая теорема, которую можно доказать на основе аксиом Пеано, гласит, что единица отлична от нуля, однако сначала нужно объяснить, что такое «единица». Внимательно изучив доказательство этой теоремы, можно получить представление о том, как работать с аксиомами и правилами вывода. Как мы уже говорили, доказательство того, что единица отлична от нуля, обязательно должно начинаться с аксиомы, каковой является аксиома Пеано: «число, следующее за натуральным, тоже является натуральным» (1). Затем можно использовать другую аксиому или высказывание, получаемое из предыдущих согласно логическому правилу вывода.

На этом шаге мы выберем аксиому, которая звучит так: «Ноль есть натуральное число» (2). Теперь с помощью modus ponens из двух первых утверждений: «число, следующее за натуральным, тоже является натуральным» и «ноль есть натуральное число» — выведем третье высказывание доказательства: «существует число, следующее за нулем» (3). Для краткости будем называть это число единицей и будем обозначать его 1. На этом шаге можно перезаписать аксиому № 3, заменив ее эквивалентной формулировкой: «если число — ноль, то оно не является следующим ни для какого числа» (4), и применить высказывание (3), которое мы уже доказали выше и которое гласит: «следующее за нулем число есть единица». Использовав modus tollens, получим: «Если число — ноль, оно не является следующим ни для какого числа. Единица — следующее за нулем число, следовательно, единица — это не ноль». Именно так звучит наша теорема: «Единица отлична от нуля» (3).

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

После того как мы доказали, что существует натуральное число, отличное от нуля, которое называется единицей, эти же рассуждения можно повторить и показать, что существует еще одно число, отличное от нуля и единицы. И действительно, «число, следующее за натуральным, тоже является натуральным» (1) и «единица есть натуральное число» (2). Применив modus ponens, получим, что «существует число, следующее за единицей» (3). Это число мы назовем двойкой. Согласно аксиоме № 4, «всякое натуральное число следует только за одним натуральным числом» (4). Наша теорема гласит, что «ноль и единица — различные числа» (3), таким образом, вновь применив modus ponens, имеем: «число, следующее за нулем, отличается от числа, следующего за единицей» (6), и этими числами, о которых идет речь, являются единица и двойка. С другой стороны, двойка и ноль — различные числа, так как двойка следует за единицей, а ноль не следует ни за каким натуральным числом.

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

Читатель, дошедший до этих строк, усомнится, обязательно ли прибегать к такому многословию, чтобы убедиться в элементарном, а именно в том, что два натуральных числа различны. И он будет совершенно прав, поскольку ни один отец не станет таким способом объяснять сыну, что две карамельки в кармане не то же самое, что всего одна. Однако логика описывает не рассуждения обычной жизни, а способ, которым нужно рассуждать, чтобы гарантированно прийти к истинному заключению. Мы избавили термины «ноль», «число» и «следующее» от всех интуитивно понятных значений, сведя их к абстрактным понятиям, связанным между собой посредством аксиом и правил вывода.

Чего мы ожидаем от аксиом

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

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

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

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

* * *

В ПРОТИВОРЕЧИВОЙ СИСТЕМЕ АКСИОМ ЛЮБОЕ ВЫСКАЗЫВАНИЕ — ТЕОРЕМА

Допустим, что мы хотим доказать истинность высказывания Q. Так как система аксиом противоречива, существует теорема Р, отрицание которой, не-Р, также будет теоремой. Это означает, что можно найти доказательства Р и не-Р. Как мы уже говорили, когда речь шла о правилах вывода, заключение «Если Р и не-Р, то Q» является корректным, так как исходные посылки никогда не выполняются одновременно. Так как в противоречивой системе аксиом Р и не-Р — теоремы, объединив правило вывода «Если Р и не-Р, то Q» и доказательства Р и не-Р, с помощью modus ponens можно показать, что Q — теорема. Иными словами, сколь бы невероятным это ни казалось, в мире, где ноль равен единице и одновременно отличается от нее, вы — мой отец (даже если вы — женщина). Ex contradictione… — из противоречия следует все что угодно.

* * *

Чтобы объяснить понятие полноты, оставим в стороне научную фантастику и воспользуемся примером, который мне подсказало одно из произведений аргентинского писателя Гильермо Мартинеса. Представьте, что в закрытой комнате совершено убийство. Прибыв на место преступления, полиция обнаруживает рядом с трупом двух подозреваемых. Каждому из них известна вся правда о том, кто же убийца. Тем не менее если подозреваемые не признаются, полицейским придется начать поиски отпечатков пальцев, следов ДНК и любых других косвенных доказательств, которые позволят вынести обвинение. Если же эти поиски ни к чему не приведут, то подозреваемые будут выпущены на свободу.

Или: после тяжелого рабочего дня полицейские отправляются в бар, чтобы расслабиться. Один из них только что поступил на службу, и остальные едва знакомы с ним. Судя по тому, что он рассказывает сослуживцам, он родился в Саламанке, затем его семья сразу же переехала в Барселону, потому что его родители хотели жить у моря. При этом его коллеги не могут понять, женат он или нет. Нет сомнений в том, что на этот вопрос существует только один правильный ответ.

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

С большинством математических теорий дело обстоит так же, как в нашем первом примере: никто не может однозначно ответить, виновны подозреваемые или нет. Но не удивляйтесь, когда мы скажем, что всегда можно выбрать аксиомы так, чтобы теория была полной: для этого система аксиом должна содержать все истинные высказывания. В этом случае все доказательства будут выполняться в одну строчку, так как всё, что мы захотим доказать, уже будет аксиомой. Почему бы нам не поступить именно так, ведь полные теории — это настоящий рай для логиков?

Всё доказуемое будет совпадать с истинным, а доказательства будут максимально короткими. Однако множество всех возможных истинных высказываний слишком велико, чтобы его можно было выбрать в качестве множества аксиом. Нас интересует не столько длина доказательств, сколько возможность проверить их корректность каким-либо автоматическим методом. Так как в доказательстве каждое утверждение является либо аксиомой, либо выводится из предыдущих с помощью правил, чтобы узнать, доказывает ли перечень высказываний некоторую теорему, мы должны иметь возможность подтвердить, что некоторое высказывание является аксиомой. И если мы включим в систему слишком много аксиом, подобная проверка потребует бесконечно много времени.

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

* * *

РАЗРЕШИМАЯ СИСТЕМА С БЕСКОНЕЧНЫМ ЧИСЛОМ АКСИОМ

Одну из возможных рекурсивно перечислимых систем с бесконечным числом аксиом можно получить, если развернуть одну из аксиом Пеано в бесконечное число утверждений. Аксиому «О не следует ни за каким натуральным числом»» можно считать сжатой формой множества высказываний: «О не следует за нулем», «О не следует за единицей», «О не следует за двойкой» и т. д. до бесконечности. Предположим, что мы хотим определить, является ли некоторое высказывание одной из этих аксиом. Разумеется, оно будет принадлежать приведенному выше списку, если будет начинаться со слов «О не следует за…», а далее будет указано некоторое число. Напомним, что «единица»» в действительности означает «число, следующее за нулем», «два» — «число, следующее за числом, следующим за нулем» и т. д. Нам останется только подсчитать, сколько раз в нашем высказывании встречается слово «следующее». Следовательно, рассматриваемая нами система аксиом является рекурсивно перечислимой.

* * *

Подведем итог. Аксиоматический метод появился примерно в 300 году до н. э., с написанием «Начал». Евклид считал, что аксиомы являются очевидными истинами, соответствующими нашим представлениям о предметах в физическом мире, однако открытие новых геометрий в середине XIX века покончило с этим реалистическим подходом. С того времени аксиомами называются всего лишь высказывания, выбранные из соображений удобства в качестве основы математической теории.

Когда мы применяем к аксиомам определенные правила вывода, например modus ponens или modus tollens, мы получаем новые истинные высказывания, которые в математике называются теоремами. Истинность теорем определяется доказательствами — конечными последовательностями высказываний, первым из которых является аксиома, следующими — либо аксиомы, либо утверждения, полученные из предыдущих по правилам вывода. Теория представляет собой множество аксиом, правил вывода и всех теорем, которые можно доказать с помощью этих правил на основе аксиом.

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

В следующей главе мы рассмотрим ряд парадоксов, которые в конце XIX столетия пошатнули тысячелетние основы математики. К счастью, вскоре были предложены различные решения, для которых кажущейся непротиворечивости аксиом было недостаточно — ее еще нужно было доказать. Об этой формалистской программе мы поговорим в главе 3. Затем мы расскажем об одном из прекраснейших элементов логики — теореме Гёделя о неполноте, которая определяет равновесие между непротиворечивостью, полнотой и рекурсивной перечислимостью.

Глава 2 Парадоксы

Парадокс есть сама страсть мыслителя.

Сёрен Кьеркегор

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

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

Он не сделал этот последний шаг не потому, что ему не хватило духа, а потому, что когда Бертрану было 11 лет, его брат Фрэнк открыл ему врата рая, который стал для него настоящим спасением и о котором еще столько предстояло узнать. Знакомство юного Рассела с райским садом «Начал» Евклида, к которым он обращался всякий раз, когда враждебный мир делался невыносимым, было подобно первой любви. Однако счастье Бертрана было неполным — хотя, по рассказам, греческий мудрец доказал все, каждый, кто открывал страницы этой книги, должен был принять на веру следующее утверждение: «Точка есть то, что не имеет частей».

Бертран Рассел в 1893 году в возрасте 21 года, удостоенный степени бакалавра математики кембриджского Тринити-колледжа.

А если бы она имела части? «От всякой точки до всякой точки можно провести прямую». А если нельзя? Бертран неохотно прислушался к совету брата, говорившего, что если не принять аксиомы на веру, обучение продолжить нельзя.

Прошло время, и спустя 12 лет после приезда в Олд-Саутгейт Бертран снова оказался в тупике — как в те моменты, когда он думал о самоубийстве. За эти 12 лет успело произойти многое: он получил степень по математике и философии в Кембриджском университете, где тайное общество лучших студентов, называвшее себя «Апостолами», наконец подарило ему тысячи часов бесед, которые он надеялся найти во время учебы. Он успел совершить путешествие, опубликовать первые книги о немецкой социал-демократии и основах геометрии и сочетаться браком с Элис Пирсолл — дочерью американских квакеров. Основным занятием Рассела оставалась математика, а его целью было свести аксиомы геометрии к законам логики, чтобы никакое утверждение больше не требовалось принимать на веру.

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

Теория множеств

Чтобы понять, в чем заключается парадокс, который положил конец счастливой и спокойной жизни Бертрана Рассела, сначала в нескольких словах опишем основы теории множеств. В предыдущей главе мы хотели показать, что основы аксиоматического метода можно встретить уже в «Началах», однако для Евклида аксиомы были очевидными истинами, а не исходными утверждениями, выбранными из соображений удобства. Со временем языка Евклида оказалось недостаточно для изложения новых математических идей. Доказать сложные теоремы XIX века исключительно с помощью слов и фигур было так же сложно, как сегодня перевести на один из мертвых языков инструкцию для iPhone.

Постепенно математическая нотация становилась все более символической: была введена форма, пригодная не только для записи рядов, производных и интегралов, — благодаря работам английского математика Джорджа Буля (1815–1864) стало возможным записывать в виде уравнений логические высказывания. Геометрия изучает фигуры в пространстве, арифметика — числа, математический анализ — средства, необходимые для формализации физических законов, алгебра — уравнения. Можно ли найти язык, общий для всех этих дисциплин, который сделал бы очевидным их единство?

* * *

БУЛЕВА АЛГЕБРА

Джордж Буль был первым, кто провел аналогию между логическими связками «и» и «или» и операциями умножения и сложения в алгебре. Он также ввел обозначения 0 («ложь») и 1 («истина») для двух значений логических переменных. Перед тем как рассмотреть пример, напомним, что при умножении чисел результат равняется нулю только тогда, когда одно из этих чисел равно нулю.

Допустим, что мы хотим перевести на язык алгебры высказывание «Все люди смертны».

Буль предложил обозначить через р значение истинности высказывания «быть человеком», за q — значение высказывания «быть смертным». Этот хитроумный прием позволяет свести содержание фразы к уравнению р·(1 — q) = 0.

Так, если некто является человеком, то р принимает значение истинности 1 («истина»).

Уравнение гласит, что произведение чисел р и (1 — q) равно нулю. Так как р отлично от нуля, то 1 — q должно равняться нулю. Однако это означает, что q равно 1 («истина»), то есть что человек смертен.

Джордж Буль, один из прародителей вычислительной алгебры.

* * *

Размышляя о проблеме, которая изначально не имела ничего общего с этим скорее философским, нежели математическим вопросом, Георг Кантор в период с 1878 по 1884 год считал, что нашел ответ в теории множеств. На интуитивном уровне множество определяется как совокупность объектов: мы говорим о множестве животных, множестве парков Парижа или множестве читателей этой книги.

Эти совокупности можно определить, перечислив все входящие в них элементы либо указав нечто общее для этих элементов. Так, множество натуральных чисел (напомним, что натуральные числа — это числа, которые мы используем при счете) — это не что иное, как множество  = {0, 1, 2, 3 …}. Если бы мы хотели рассмотреть только четные числа, то записали бы 2 = {0, 2, 4, 6 …} или  n кратно 2}, где символ  обозначает «принадлежит», а вертикальная черта | — «такое, что». Мы указали не список элементов множества, а правило его определения, так как в этом случае мы рассматриваем подмножество натуральных чисел, обладающее свойством делимости на два.

Едва начав работу, Кантор осознал, что в его новой теории рассматривались одновременно два объекта совершенно разной природы: конечные и бесконечные множества. По сути задача о нахождении числа элементов множества (математики называют его кардинальным числом, или мощностью множества) имеет разные решения в зависимости от того, конечное или бесконечное множество мы рассматриваем. Представим очень простую ситуацию: допустим, мы хотим узнать, имеют ли два конечных множества одно и то же кардинальное число, например равно ли число букв в слове «нахальство» числу цветов радуги. Очевидный метод заключается в том, чтобы подсчитать элементы каждого множества и сравнить результаты: так как в слове Н-А-Х-А-Л-Ь-С-Т-В-О десять букв, а в радуге семь цветов (красный, оранжевый, желтый, зеленый, голубой, синий, фиолетовый), то эти два множества содержат разное число элементов. Но что произойдет, если мы применим этот же метод к двум бесконечным множествам? В этом случае необходимо либо считать, что все бесконечные множества обладают одинаковым кардинальным числом и поставить на этом точку, либо использовать какой-то другой метод.

Вернемся к конечным множествам и посмотрим, что произойдет, если мы будем не рассматривать две совокупности по отдельности, а станем по очереди извлекать из них по одному элементу: начнем с буквы Н и красного цвета и т. д., пока не дойдем до буквы С, которой соответствует фиолетовый цвет. В этот момент одно из двух множеств уже «закончилось», а в другом осталось еще три элемента — буквы Т, В и О, следовательно, кардинальное число этого множества больше. Операция, которую мы попытались проделать, в математике называется установлением биекции между двумя множествами и означает присвоение каждому элементу множества X элемента другого множества Y «один к одному» так, что выполняются следующие условия.

1. Не существует двух элементов X таких, которым соответствует один и тот же элемент Y.

2. Каждому элементу Y соответствует какой-либо элемент множества X.

Таким образом, используя введенную нами терминологию, можно сказать, что кардинальные числа двух множеств равны, если между ними можно установить биекцию. Нетрудно показать, что установить биекцию между двумя конечными множествами с разным числом элементов нельзя, так как либо несколько элементов X будут поставлены в соответствие одному и тому же элементу Y, либо какой-то элемент Y останется без пары.

Три примера отображения конечных множеств, лишь одно из которых (см. рис. 3) является биекцией, так как на рис. 1 двум элементам первого множества сопоставлен один элемент второго, а на рис. 2 один из элементов исходного множества остался без пары.

Преимущество этого подхода в том, что его можно применить к бесконечным множествам. Таким образом, будем говорить, что кардинальные числа двух множеств равны, если между множествами можно установить биекцию. Первое следствие этого, возможно, удивит читателя: существует столько же четных чисел, сколько четных и нечетных, вместе взятых. Как такое возможно? Для доказательства этого весьма неочевидного утверждения достаточно определить биекцию между натуральными и четными числами. Сопоставим 0 и 0, 1 и 2, 2 и 4, а произвольному п сопоставим число, в два раза большее него. При таком отображении различным числам всегда будут соответствовать разные числа, и любое четное число будет сопоставлено с числом, в два раза меньшим его. Так как оба свойства биекции выполняются, это означает, что существует столько же четных чисел, сколько и натуральных!

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

Существование подобных гостиниц, которые невозможно заполнить, — это не просто любопытный факт, связанный с четными числами, а основное свойство бесконечных множеств, как заметил Рихард Дедекинд в своей статье «Что такое числа и для чего они служат», опубликованной в 1888 году. Множество является бесконечным, если можно определить биекцию между ним и его частью. Очевидно, что с конечными множествами подобное невозможно, так как часть конечного множества не может быть поставлена в соответствие целому (как мы говорили выше, между двумя конечными множествами, число элементов которых равно m и n соответственно, можно установить биекцию только при m = n). Тем не менее натуральных чисел бесконечно много, так как часть этого множества, строго включенная в него, то есть множество четных чисел, имеет то же кардинальное число, что и все множество в целом. Следовательно, новое определение соответствует рассуждениям, основанным на аксиомах Пеано, с помощью которых мы в предыдущей главе доказали, что натуральных чисел бесконечно много. Однако множество натуральных чисел — это наименьшее бесконечное множество из всех, что можно представить.

Поэтому все множества, для которых можно установить биекцию со множеством натуральных чисел, называются счетными множествами, а их кардинальное число обозначается буквой алеф — первой буквой еврейского алфавита. Индекс указывает, что речь идет о наименьшем кардинальном числе: .

Счетность множества означает, что между множеством X и множеством натуральных чисел можно установить биекцию. Так, каждому натуральному n можно поставить в соответствие элемент этого множества, который мы обозначим через хn, так, что если n и m различны, то хn и хm также различны. С другой стороны, все элементы X можно записать в виде хn для некоторого n. Когда дети идут на экскурсию с классом, учитель иногда присваивает им номера, чтобы никто не потерялся.

Перед тем как сесть в автобус, каждый ученик громко выкрикивает свой номер: пе-е-ервый! второ-о-ой! тре-е-етий! Каждый ученик имеет свой номер, и ни один из номеров не повторяется. Элементы счетных множеств также имеют свои порядковые номера: «пе-е-ервый!» — это x1 «второ-о-ой!» — х2. Счетные множества — это множества, элементы которых можно выстроить в ряд. Мы показали, что множество четных чисел является счетным, так как их можно упорядочить: 0, 2, 4, 6, 8, 10… Это же справедливо и для положительных и отрицательных чисел, так как можно, начав с нуля, называть их поочередно: 0, 1, —1, 2, —2.

Элементы любого ли множества можно выстроить в ряд? Если это так, то все множества будут счетными, и мы придем к тому же, с чего начали, когда использовали примитивный метод подсчета элементов множества. Однако пусть читатель не беспокоится: одним из величайших достижений Георга Кантора стало открытие множеств, которые не являются счетными. Пусть дано множество, образованное бесконечными последовательностями нулей и единиц, то есть объектами вида 0100100010… или 1100101001… Покажем, что если мы будем считать это множество счетным, то придем к противоречию. В самом деле, если бы это множество было счетным, мы могли бы записать все его элементы в виде списка следующим образом:

Напомним, что аn, Ьn и сn принимают только значения 0 и 1. Составим элемент, который будет принадлежать к множеству бесконечных последовательностей нулей и единиц и при этом не будет упомянут в нашем списке. Для этого рассмотрим элементы, расположенные по диагонали и обведенные рамкой. Рассмотрим a0: если этот элемент равен 0, начнем нашу последовательность с 1, и наоборот. Так мы определим первый член нашей последовательности. Перейдем к b1 если этот элемент равен 0, то вторым членом нашей последовательности будет 1. Если же, напротив, этот элемент равен 1, то вторым членом последовательности будет 0. В общем случае для определения n-го члена нашей последовательности мы будем рассматривать соответствующий элемент на диагонали и записывать противоположное ему значение. Таким образом, мы получим последовательность, все члены которой будут иметь значение 0 или 1, следовательно, эта последовательность будет принадлежать к рассматриваемому множеству. Например, если наш список будет начинаться так:

то первыми членами составленной нами последовательности будут 1, 0, 0.

Так как этот метод составления последовательности нулей и единиц заключается в изменении значений элементов, расположенных по диагонали, он называется диагональным методом. Здесь мы хотим показать, что последовательность, полученная диагональным методом, является элементом рассматриваемого множества, однако не фигурирует в гипотетическом списке всех элементов этого множества. И действительно, наша последовательность не может быть первой последовательностью из списка, так как их первые члены отличаются. Она не может быть и второй последовательностью, так как мы изменили ее второй член, она не может быть ни третьей, ни четвертой: каждая последовательность из списка будет отличаться от составленной нами как минимум одним элементом — этот элемент будет располагаться на диагонали. Мы предположили, что множество последовательностей нулей и единиц счетное, то есть все его элементы можно представить в виде списка, и получили противоречие. Это доказывает, что наше множество не является счетным!

Мы посвятили несколько страниц объяснению основных понятий теории множеств не только для того, чтобы даже сформулировать парадокс Рассела. Доказательство того, что множество последовательностей нулей и единиц не является счетным, читатель может счесть не более чем виртуозным упражнением, однако оно позволит нам показать в главе 5, что существуют задачи, с которыми не могут справиться даже компьютеры, и установить пределы «сну разума», о котором говорится в названии этой книги. Мы также надеемся, что смогли продемонстрировать читателю, сколько тайн встречается тем, кто путешествует по миру бесконечных множеств.

* * *

ПРЕПОДАВАНИЕ ТЕОРИИ МНОЖЕСТВ В ШКОЛЕ

В 70-е годы группа последователей французской математической группы Бурбаки, которые, однако, в большинстве своем не были математиками, захотели ввести теорию множеств в курс начальных школ Европы. В этой учебной программе натуральные числа объяснялись как кардинальные числа конечных множеств. 0 определялся как кардинальное число пустого множества, а сложение 2 и 3 объяснялось как объединение множества из 2 элементов с другим множеством из 3 элементов, при этом не важно, что результат будет обозначаться 5, важно, что 2 + 3 = 3 + 2, так как не имеет значения, в каком порядке мы будем объединять элементы множеств. Как рассказывал Пьер Картье, в то время бывший секретарем группы Бурбаки, в результате этой политики в сфере образования дети возвращались из школы домой и плакали: «Мама, я не хочу быть множеством».

Диаграммы Венна — наиболее типичный способ представления множеств.

* * *

Парадокс Рассела

Бертран Рассел познакомился с теорией множеств в 1896 году. Ему было довольно трудно принять ее: автор книги, из которой Рассел узнал о существовании этой теории, входил в число тех, кто считал, что теория Кантора была недостаточно строгой, и уподоблял ее теологии, а Рассел в этот период стремился к максимальной научной строгости. Однако позднее он понял, что многие обвинения в адрес Кантора были необоснованными, и включил идеи этого немецкого математика в последнее издание «Начал математики», вышедшее в мае 1903 года. Знакомясь с новой литературой, чтобы дополнить последнее издание книги, Рассел открыл для себя труд Готлоба Фреге, который предвосхитил многие из его открытий, опередив Рассела на 20 лет.

Понять, что Фреге и Рассел вели речь об одном и том же, было не всегда просто: сложный символический язык Фреге, подобный нотной партитуре современной музыки, не имел ничего общего с простой и понятной нотацией, которую Рассел перенял у Пеано.

Подробно изучив «Исчисление понятий» (Begriffsschrift) — книгу, в которой Фреге впервые изложил результаты своих исследований, — Рассел начал задумываться о множестве всех множеств, которые не принадлежат сами себе. Множество всех котов определенно не является котом, однако множество всего, что только можно себе представить, также можно представить. О таких множествах мы говорим, что они принадлежат сами себе.

Гэтлоб Фреге — создатель математической логики.

Страница «Исчисления понятий» Гэтлоба Фреге.

Конечно, это определение несколько расплывчато, поэтому давайте одним махом разберемся со всеми множествами такого типа. Обозначим через R (по первой букве фамилии Рассела) множество всех множеств, которые не содержат сами себя в качестве своего элемента: к R будет принадлежать множество котов, столов и все совокупности предметов, не содержащие сами себя. И все будет в порядке, пока мы не пересекаем границу, отделяющую R от остальных множеств.

Различие между множеством всех котов, которое не является котом (рис. 1), и множеством всего, что только можно себе представить, которое также можно себе представить (рис. 2).

(Источник: Умберто Эко, Vertige de la liste, Париж, издательство Flammarion, 2009, стр. 396).

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

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

Чтобы объяснить свой парадокс простыми словами, Рассел описал город, где по закону брадобрей должен брить только тех, кто не бреет себя сам. Мы заменили свойство «принадлежать самому себе» на «бриться самому», и теперь в роли множества R будет выступать брадобрей. В этой версии парадокса возникает вопрос: кто бреет брадобрея? Если он бреет себя сам, то принадлежит к числу тех, кого по закону ему брить нельзя. Если же он не бреет себя сам, то по закону он должен брить себя сам. Что бы они ни делал, он окажется в тюрьме, где, возможно, некий логик попытается убедить его, что провести несколько лет в тюрьме всегда лучше, чем столкнуться с противоречием, которое ставит под сомнение правильность всей математики двух тысячелетий.

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

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

Столкнувшись с этим парадоксом, Рассел написал письмо Фреге, который в то время вносил правки в доказательства второго тома своего главного труда — «Основные законы арифметики». В него Фреге включил аксиому, благодаря которой стало возможным сформировать множество всех объектов, обладающих свойством Р, однако Рассел открыл, что если эту аксиому применить к самому свойству Р = «принадлежать самому себе», то это приведет к противоречию: множество R всех множеств, которые не принадлежат сами себе, нарушает закон исключенного третьего. Обескураженный этим открытием, Фреге, с присущей ему скрупулезностью, добавил к книге предисловие, в котором признался: «С автором не может произойти ничего более печального, чем, закончив свой труд, увидеть, как рушится одна из основ выстроенного им здания». Затем он предложил видоизменить эту аксиому, однако ее новый вариант не согласовывался с остальной системой аксиом, поэтому решения парадокса Рассела пришлось ждать несколько лет.

В период с 1906 по 1908 год Рассел нашел простое решение парадокса, на основе которого сформулировал теорию типов. До этого он занимался решением онтологической задачи, предметом которой были описания вида «наибольшее натуральное число» или «нынешний король Франции», которые, будучи грамматически корректными, не описывают никакой конкретный объект. В случае с «множеством всех множеств, которые не содержат себя в качестве своего элемента» дело обстоит еще хуже: это множество не просто не существует, но даже его описание не является корректным. Оно равносильно высказыванию «Франция в период правления нынешнего короля» или «наибольшее натуральное число».

* * *

РАССЕЛ О ФРЕГЕ

В письме к историку математической логики Жану ван Хейенорту от 23 ноября 1962 года Рассел так отзывался о Фреге:

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

* * *

В простейшем варианте теории Рассела каждому математическому объекту можно присвоить число в зависимости от его сложности: элементы имеют тип 0, множества элементов — тип 1, множества множеств элементов — тип 2 и т. д. Например, если рассмотреть натуральные числа, то число 8 будет иметь тип 0, множество Р всех четных чисел и множество I всех нечетных чисел — тип 1, а множество {Р, I} будет иметь уже тип 2, так как его элементы будут иметь тип 1. После того как всем объектам присвоены типы, устанавливается нерушимое правило: для объекта типа n можно задать отношение принадлежности только к объекту типа n + 1. Выражение «число 8 четное» является корректным, так как 8 имеет тип О, Р — тип 1. Тем не менее нет смысла задаваться вопросом, является ли само множество Р четных чисел четным числом или нет, так как в этом случае речь идет об отношении принадлежности, связывающем объекты одного типа. Именно о таком отношении шла речь в описании множества всех множеств, которые не принадлежат самим себе. На языке логики говорить «принадлежать самому себе» с концептуальной точки зрения некорректно, и здесь парадокс исчезает: для данного свойства Р можно рассмотреть множество объектов, которые обладают этим свойством, однако для этого Р как минимум должно быть корректно определено.

Эрнст Цермело, создатель первой аксиоматики теории множеств.

Одновременно с публикацией в журнале American Journal of Mathematics статьи Рассела «Математическая логика, основанная на теории типов» Эрнст Цермело (1871–1953) предложил новое решение этого парадокса, менее концептуальное, чем выдвинутое Расселом, но намного более практичное с точки зрения «рабочих от математики». Сегодня нам известно, что одна из величайших трудностей при создании любой теории — это определить предмет ее изучения. Повсюду говорят о теории информации, но что такое информация? Некоторые определяют биологию как науку о жизни, но что такое жизнь? Этими же вопросами задался Цермело при рассмотрении теории множеств. Согласно интуитивному определению Кантора, множества были не более чем совокупностями объектов, обладающих определенным свойством, однако такое определение допускало создание множества всех множеств, которые не принадлежат сами себе. Без четкого определения множества нельзя было двигаться дальше. Цермело заменил примитивное определение множества списком аксиом, в число которых включил аксиому, не позволявшую определить множество из парадокса Рассела. Начиная с этого момента множества стали определяться как объекты, удовлетворяющие списку аксиом.

Парадокс лжеца

Мы начали эту главу с анализа парадокса Рассела, однако пусть читатель не думает, что логические парадоксы являются исключительно творениями современности. Само слово «парадокс» — «неожиданный, странный» — имеет греческие корни.

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

Один из древнейших парадоксов — это парадокс об Ахиллесе и черепахе, с помощью которого философ-досократик Зенон Элейский, ученик Парменида, хотел доказать, что движения не существует, и нанести удар по защитникам атомистической концепции пространства и времени. Зенон объяснял: фора, которую Ахиллес дает черепахе, чтобы забег проходил в равных условиях, непреодолима — когда атлет добежит до того места, где черепаха находилась вначале, она проползет чуть дальше. Когда Ахиллес преодолеет расстояние, пройденное черепахой, он вновь не сможет поравняться с ней — она успеет проползти немного вперед. Ахиллеса всегда будет отделять от черепахи некоторое расстояние, сколь бы малым оно ни было.

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

Возможно, наиболее интересными среди классических парадоксов являются антиномии — утверждения, истинные и ложные одновременно. Среди них выделяется парадокс лжеца, обычно приписываемый Эпимениду Критскому, хотя возможно, что этот философ, о котором говорили, будто он проспал 57 лет в пещере, зачарованной Зевсом, не осознавал, что формулирует парадокс. В одном из стихов Эпименид говорит о «критянах, вечно лживых», которые не верили в бессмертие Зевса. Однако сам Эпименид также был критянином, поэтому его утверждение относилось к нему самому и было равносильно высказыванию «Я всегда лгу».

Допустим, что Эпименид лжет, тогда его высказывание не может быть верным, следовательно, он говорит правду. Если же, напротив, Эпименид говорит правду, то его высказывание должно быть истинным, следовательно, он лжет. По легенде, поэт Филит Косский умер от изнеможения, пытаясь разрешить этот парадокс.

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

* * *

ОСТРОВ РЫЦАРЕЙ И ОРУЖЕНОСЦЕВ

Некий логик попал на остров, все жители которого делились на две группы: рыцари всегда говорили правду, а оруженосцы всегда лгали. Повстречав троих жителей А, В и С, логик спросил А, к рыцарям или оруженосцам он принадлежит, но получил столь путаный ответ, что был вынужден обратиться к в и спросить его: «Что сказал А?». В ответил: «А сказал, что он оруженосец». Однако в этот самый момент в разговор вмешался С, который предупредил логика: «Не верь В, он лжет!»

На основе этих двух утверждений логик может определить, кем же являются B и С. В самом деле, согласно В, житель А сказал «Я оруженосец», что можно считать одной из версий парадокса лжеца: «Я всегда лгу». Следовательно, существует единственный непротиворечивый выход из этой ситуации: когда В говорил об А, он солгал, следовательно, В — оруженосец. Таким образом, когда С предупреждал логика, он говорил правду, из чего следует, что С — рыцарь. Чтобы узнать, кем на самом деле является А, нам потребуется задать дополнительные вопросы.

* * *

В разные эпохи парадокс лжеца трактовался по-разному. Сервантес, например, упоминает его в главе LI второй части «Дон Кихота» — «О том, как Санчо Панса губернаторствовал далее, а равно и о других поистине славных происшествиях» в качестве примера того, сколь трудные решения приходилось принимать Санчо Пансе на острове Баратария. До этого, в главе XVIII, дон Кихот объясняет, что к наукам, которые должен знать странствующий рыцарь, принадлежит математика, «ибо необходимость в математике может возникнуть в любую минуту». Именно это про

исходит с Санчо Пансой, когда ему сообщают о деле хозяина поместья, разделенного рекой, который обязывал всякого, кто хотел переправиться через нее, сначала сообщить, куда он направляется. Если путник говорил правду, ему разрешалось переправиться через реку, но если он лгал, его ждала казнь. После вступления закона в силу судьи беспрепятственно пропускали почти всех, пока в один прекрасный день перед ними не предстал человек, который заявил, что направляется на виселицу, чтобы быть повешенным. Посовещавшись, судьи вынесли вердикт: «Если позволить этому человеку беспрепятственно следовать дальше, то это будет значить, что он нарушил клятву и согласно закону повинен смерти; если же мы его повесим, то ведь он клялся, что пришел только затем, чтобы его вздернули на эту виселицу, следственно, клятва его, выходит, не ложна, и на основании того же самого закона надлежит пропустить его»[2].

В шедевре Мигеля Сервантеса Дон Кихот предлагает разрешить парадокс своему оруженосцу.

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

(1/2) + (1/4) + (1/8) + (1/16) + (1/32) и т. д.

чтобы догнать черепаху. При этом сначала ему нужно преодолеть его половину (1/2), затем — половину половины, то есть одну четверть (1/4), затем — половину половины половины, то есть одну восьмую (1/8) и т. д. Так как число слагаемых бесконечно велико, то расстояние, которое должен преодолеть Ахиллес, обязательно равняется бесконечности, таким образом Ахиллесу не хватит всей жизни, чтобы преодолеть его и догнать черепаху. Ошибка Зенона состояла в том, что сумма бесконечного числового ряда необязательно равна бесконечности, при условии что члены ряда убывают с достаточной быстротой. Николай Орезмский (1323–1382) привел красивое геометрическое решение этого парадокса, в котором показал, что сумма ряда Зенона равна не бесконечности, а в точности единице — именно такую фору Ахиллес дал черепахе. Следовательно, парадокс Зенона есть не более чем ошибочное представление о бесконечных рядах.

Схема, с помощью которой Николай Орезмский в XIV веке показал, что сумма ряда из парадокса об Ахиллесе и черепахе не равна бесконечности.

С парадоксом лжеца дело обстоит иначе. «Эта фраза ложна» — об этом высказывании нельзя сказать, истинно оно или ложно, так как любой ответ неизменно ведет к противоположному. Как заметил греческий логик Хрисипп из Сол, те, кто сформулировал парадокс лжеца, «совершенно отклонились от изначального значения слов — они произвели лишь звуки, ничего не выразив». Первой естественной реакцией будет объяснить противоречие тем, что высказывание ссылается на само себя, однако этого недостаточно — высказывания «эта фраза истинна» или «эта фраза относится к книге «Сон разума. Математическая логика и ее парадоксы» также ссылаются сами на себя, однако не вызывают никаких затруднений.

Другим, несколько хитроумным решением, будет поставить вопрос: не принадлежит ли понятие истинности, подобно понятию множества, к числу тех, которые просто использовать, но трудно определить. Этой точки зрения придерживался Альфред Тарский (1902–1983), который в 1933 году опубликовал статью объемом свыше двухсот страниц на польском языке, где впервые формально определил истину. Несмотря на значительный объем статьи, Тарский не предложил придать понятию «истинность» новое значение, а вместо этого всего лишь описал на языке математики аристотелево определение истины как соответствие между тем, что говорится о реальности, и самой реальностью. Подобно тому как высказывание «снег белый» истинно тогда и только тогда, когда снег в самом деле белый, высказывание Р является истинным в некоторой теории тогда и только тогда, когда при интерпретации Р в рамках структуры, которую описывает эта теория, Р является истинным. В какой структуре следует интерпретировать фразу вида «эта фраза ложна»?

Как вы увидите в главе 4, ответить на этот вопрос удалось лишь Курту Геделю.

В конечном итоге парадокс Рассела, парадокс Ахиллеса и черепахи и парадокс лжеца были решены, однако попутно родилось множество других вопросов.

В 1905 году преподаватель института Дижона Жюль Ришар открыл парадокс, связанный с диагональным методом Кантора. Годом позже юный библиотекарь Бодлианской библиотеки Оксфордского университета (необязательно тот, который проводил дни и ночи, составляя каталог всех каталогов, не содержащих ссылки на самих себя) упростил парадокс Ришара, представив, что произойдет, если для описания любого натурального числа можно использовать только пятнадцать слов. Так как число выражений, состоящих из пятнадцати слов, является конечным, то с их помощью мы можем описать лишь конечное множество чисел. Среди всех чисел, которые мы не сможем описать пятнадцатью словами, одно будет наименьшим. Обозначим его через n. Однако в этом случае n будет «наименьшим числом, которое нельзя описать менее чем пятнадцатью словами» — это описание содержит всего девять слов!

Как мы можем быть уверены, что парадоксы не будут и дальше распространяться, подобно вирусам? Источниками противоречий служили бесконечность, самоотносимость и не вполне точно определенные понятия. Однако не все высказывания, которые ссылаются сами на себя, порождают парадоксы, полностью исключить бесконечность из математики нельзя, и у нас нет инструмента, который безошибочно укажет на недостаточно четко определенные понятия. В следующей главе мы расскажем о стратегии, с помощью которой наиболее выдающийся математик своего поколения, Давид Гильберт, хотел полностью избавиться от парадоксов.

Глава 3 Программа Гильберта

Бог существует потому, что математика непротиворечива, а дьявол существует потому, что мы не можем доказать это.

Приписывается Андре Вейлю

«Кто из нас не обрадовался бы, если бы мог поднять завесу, за которой скрывается будущее, окинув взором перспективы нашей науки и ее секреты?»

Начинался новый век, и тысячи посетителей Всемирной выставки в Париже наводнили ее павильоны, озаряемые ярким августовским солнцем. В это же время в Париже проходил II Международный математический конгресс, и Давид Гильберт выступал в амфитеатре Сорбонны на заседании своих секций. Его целью было впервые рассказать не о том, что уже доказано, а о том, что еще предстоит открыть.

Никто не сомневался, что Гильберт был лучшим математиком своего поколения, однако его выступление было отодвинуто на второй план — наряду с исследованиями, посвященными древним японским геометрам, и предложениями ввести во всех странах единый научный язык. Разумеется, ученого пригласили выступить и на общем заседании конгресса в день открытия, но он слишком долго не мог определиться с темой выступления, и организаторам пришлось исключить его доклад из программы.

Наблюдая, как Гильберт в своих очках поднимался на кафедру, зрители спрашивали друг у друга, о чем же он все это время размышлял.

«История учит, что развитие науки протекает непрерывно. Мы знаем, что каждый век имеет свои проблемы, которые последующая эпоха или решает, или отодвигает в сторону как неразрешимые, чтобы заменить их новыми». Гильберт был убежден, что единственным двигателем прогресса в математике является решение задач. Поэтому, обращаясь к собравшимся в зале Сорбонны, лидер Гёттингенской математической школы подчеркивал, что решить задачу означает сформулировать рассуждения, с помощью которых, исходя из конечного числа гипотез, выраженных точными терминами, можно прийти к выводу за конечное число этапов посредством строгих логических правил вывода. Чтобы проиллюстрировать свои идеи, Гильберт выбрал двадцать три задачи, которые, по его мнению, должны были указать направления исследований математикам XX века, однако ему не хватило времени, чтобы прокомментировать все эти задачи. Благодаря свидетельствам его друзей — математиков Германа Минковского (1864–1909) и Адольфа Гурвица (1859–1919) — нам известно, каких трудов стоило Гильберту выбрать задачи, упомянутые в парижском докладе. И однако он ни на секунду не усомнился в своем выборе. Вторая задача из списка звучала, казалось, совершенно невинно: являются ли аксиомы арифметики непротиворечивыми?

* * *

ЗАДАЧА О КАРДИНАЛЬНЫХ ЧИСЛАХ МНОЖЕСТВА

В предыдущей главе вы увидели, что одним из величайших открытий Георга Кантора было доказательство того, что не все бесконечные множества имеют одинаковый размер. И действительно, его диагональный метод позволил показать, что натуральных чисел меньше, чем бесконечных последовательностей, состоящих из нулей и единиц. В первой задаче из списка Гильберта требовалось дать положительный или отрицательный ответ на вопрос о том, существует ли такое множество, кардинальное число которого будет больше, чем кардинальное число множества натуральных чисел, но меньше, чем кардинальное число множества последовательностей из нулей и единиц. Благодаря трудам Курта Гёделя (1940) и математика Пола Коэна из Стэнфордского университета (1963) сегодня нам известно, что если исходить из привычной системы аксиом теории множеств, на этот вопрос нельзя дать ни положительного, ни отрицательного ответа.

* * *

Доклад Гильберта прозвучал 8 августа 1900 года. К этому времени в теории множеств уже появились первые парадоксы, однако Рассел открыл противоречие, которое заставило всех забить тревогу, лишь годом позже. Очень быстро парадокс о множестве всех множеств, которые не принадлежат сами себе, встревожил европейские математические круги: в Англии Уайтхед предсказал конец «счастливым и спокойным будням», в Германии Фреге добавил к своим «Основам арифметики» пессимистичное предисловие, во Франции Анри Пуанкаре, враг математической логики, победно воскликнул: «Формальная логика не бесплодна: она порождает противоречия». Если от кого и ожидали ответа, то это был Давид Гильберт — его многие считали новым Евклидом благодаря опубликованной им в 1899 году системе аксиом геометрии, которая ознаменовала начало современного подхода к этой дисциплине. Тем не менее Гильберт не потрудился дать меткий ответ, который вошел бы в историю, подобно изречениям Уайтхеда, Фреге и Пуанкаре: он просто точно знал, как можно избавить математику от парадоксов.

Давид Гильберт больше всего подходил на роль того, кто покончил бы с математическими парадоксами.

Формализм Гильберта

Решение, предложенное Гильбертом, состояло из двух этапов. Сначала нужно было полностью формализовать арифметику, то есть представить все ее содержимое как формальную систему. Это следовало сделать с максимально возможной строгостью, и за этим первым этапом должен был последовать второй, на котором доказывалась бы корректность выполненной формализации. Математика, в отличие от жены Цезаря, не была выше подозрений: ее непротиворечивость следовало доказать. Для этого Гильберт предложил ряд приемов, объединенных названием «метаматематика».

Читатель справедливо заметит: какова разница между системами аксиом, которые мы рассматривали выше, и формальными системами, которые Гильберт хотел определить для арифметики? Действительно, эти понятия очень похожи, однако формальные системы обладают важным отличием: в них любое утверждение представляется в виде символов искусственного языка, лишенных конкретных значений.

Цель Гильберта понятна из его переписки, в которой он, например, объясняет, что геометрия не изменится, если вместо терминов «точка», «прямая» и «плоскость» мы напишем «любовь», «закон» и «трубочист». Как следствие, для формалиста выражения «глава третья» и «глава 3» — это два разных высказывания, единственная связь между которыми заключается в особенностях синтаксиса: оба выражения начинаются с одного и того же слова.

Основу гильбертовой формальной системы составляло множество базовых символов L, основанных на алфавите нашего языка. На их основе можно создать формулы, которые будут представлять собой не что иное, как конечные последовательности символов, составленные согласно ряду грамматических правил. Если, например, язык содержит открывающую и закрывающую скобки, то одно из его правил может звучать так: справа от каждой открывающей скобки обязательно должна быть записана закрывающая скобка.

Чтобы определить формальную систему, помимо алфавита, необходимы аксиомы и правила вывода. Аксиомы отличаются от всех остальных формул только тем, что занимают привилегированное положение. Как мы указывали в главе 1, выбор аксиом — одна из сложнейших задач при определении формальной системы: если мы выберем слишком много аксиом, то они могут смешаться с остальными формулами, а если мы выберем слишком мало аксиом, то некоторые формулы нельзя будет ни доказать, ни опровергнуть. Правила вывода, в свою очередь, это процедуры, позволяющие получить новые формулы на основе уже известных. Аксиомы и правила вывода объединяются в формальные доказательства — последовательности формул, каждая из которых является либо аксиомой, либо получена из предыдущих формул с помощью правил вывода. Традиционно последняя формула доказательства называется теоремой.

Следовательно, первое требование программы Гильберта заключалось в том, чтобы описать алфавит, определить аксиомы и формальные правила вывода для арифметики. Этой задаче Бертран Рассел и Альфред Норт Уайтхед посвятили три объемных тома «Начал математики», опубликованных в 1910–1913 годах. В действительности теория, предложенная Расселом и Уайтхедом и названная вскоре логицизмом, выходила далеко за рамки формалистской программы: оба ее автора не ограничивались формализацией арифметики и хотели свести ее к логике, то есть определить все понятия теории натуральных чисел исходя из чисто логических обозначений, а также вывести из этих понятий все теоремы арифметики. Одним из величайших успехов математики XIX века было построение любого класса чисел на основе натуральных, таким образом, если бы Рассел и Уайтхед достигли своей цели, математика и логика пошли бы рука об руку по дороге, свободной от противоречий (по крайней мере, основоположники логицизма на это надеялись).

* * *

НЕПРИБЫЛЬНАЯ МАТЕМАТИКА

Ключевой труд Рассела и Уайтхеда был опубликован издательством Cambridge University Press. Издательство смогло выделить на публикацию всего 300 фунтов, что составляло половину необходимой суммы. Недостающие 300 фунтов обязалось внести Лондонское королевское общество, членом которого был Рассел, однако в итоге было внесено лишь 200, а остаток Расселу и Уайтхеду пришлось заплатить из своего кармана. «Неплохой баланс, — шутил Рассел впоследствии, — за десять лет работы мы заработали минус пятьдесят фунтов на каждого».

* * *

В упрощенной версии формальная система арифметики, предложенная Расселом и Уайтхедом в «Началах математики», состояла из следующих основных символов: 0 (число ноль), s (функция следования), ¬ (отрицание), V (дизъюнкция «или»),  (существование), = (равенство) и открывающая и закрывающая скобки. Позднее к этим символам были добавлены переменные х, у, z типа 0, которые обозначали натуральные числа, а также переменные А, В, С типа 1, то есть множества натуральных чисел, и т. д. по мере того, как требовались элементы все новых и новых типов. Возможно, внимательный читатель заметил отсутствие других символов, которые должны быть частью языка: например, наряду с квантором существования, благодаря которому можно формализовать высказывания вида «существует натуральное число, обладающее свойством Р», можно было бы добавить еще один символ, который означал бы «для всех», как в высказывании «для всех натуральных чисел выполняется утверждение Р». По сути, этот универсальный квантор очень широко используется в математике: «для всех» обозначается символом . Мы действительно можем добавить к языку символ , однако этого на самом деле не требуется, так как выражение «для всех натуральных чисел выполняется высказывание Р» равносильно выражению «не существует такого натурального числа, для которого не выполнялось бы высказывание Р». Следовательно, символ  можно выразить с помощью символов отрицания и существования.

Это же справедливо и для конъюнкции «и»: для ее обозначения существует символ , однако он является избыточным, так как его можно заменить символами V и ¬. Чтобы доказать это, рассмотрим три операции теории множеств: дополнение, объединение и пересечение.

Для данного множества А, которое содержится в другом множестве В, дополнением множества А до В называют множество, состоящее из элементов, принадлежащих В, но не А. Например, дополнением множества гласных {а, е, i, о, и} английского алфавита является множество согласных. Рассмотрим операции объединения и пересечения. Для данных множеств X и Y их пересечение X  Y определяется как множество элементов, одновременно принадлежащих X и Y. Например, если X — множество четных чисел 0, 2, 4, 6, 8, 10…, а Y — множество чисел, кратных трем, 0, 3, 6, 9, 12, 15 …, то чтобы найти их пересечение, нужно определить их общие элементы: ими будут 0, 6, 12, 18…, то есть числа, кратные шести. Объединением множеств X U Y называется множество, которому принадлежат все элементы X и все элементы Y. В предыдущем примере первыми элементами объединения X и Y будут 0, 2, 3, 4, 6, 8, 9…

Похожесть символов, обозначающих пересечение двух множеств () и конъюнкцию двух высказываний (), а также символов, обозначающих объединение двух множеств (U) и дизъюнкцию двух высказываний (V), вовсе не случайна. Если сопоставить свойствам Р и Q множества чисел, обладающих этими свойствами, например X и Y, то числа, обладающие свойствами Р и Q одновременно, будут элементами пересечения множеств X  Y, а числа, обладающие свойством Р или Q, то есть как минимум одним из этих двух свойств, будут принадлежать объединению множеств X U Y. Дополнение множества, в свою очередь, соответствует отрицанию высказывания. Для представления дополнений, объединений и пересечений множеств очень удобно использовать диаграммы, созданные британским математиком и философом Джоном Венном в 1880 году. С их помощью можно доказать, что конъюнкция свойств Р и Q равносильна отрицанию дизъюнкции отрицаний Р и Q, иными словами, Р  Q = ¬(¬Р V ¬Q). Это свойство позволяет выразить  через V и ¬.

Рис. 1. Пересечение двух множеств, соответствующее конъюнкции P  Q.

Рис. 2. Объединение двух множеств, соответствующее дизъюнкции Р V Q.

Рис. 3. Дополнение множества, соответствующее отрицанию ¬Р.

Диаграммы Венна, на которых представлены операции пересечения (рис. 1), объединения (рис. 2) и дополнения (рис. 3) множеств.

Сделав замечание о том, как представляются выражение «для всех» и конъюнкция высказываний (логическое «и»), рассмотрим, как переводятся в формальную систему арифметики некоторые аксиомы Пеано. Первая аксиома Пеано звучит так: «Ноль есть натуральное число». Эта аксиома не требует перевода, так как мы включили символ 0 в созданный нами язык. Перейдем ко второй аксиоме: «Каждое натуральное число имеет число, следующее за ним». В этой аксиоме фигурируют две переменные: рассматриваемое натуральное число, которое мы будем обозначать через х, и следующее за ним, которое будем обозначать через у. Вспомним, что число, следующее за данным, записывается с помощью буквы s, которая ставится перед этим числом, и выражается формулой у = sx, то есть «у равно числу, следующему за х». Следующий шаг заключается в том, что высказывание «каждое натуральное число» равносильно высказыванию «для всех натуральных чисел», и в этом контексте слово «имеет» означает «существует». Таким образом, аксиома принимает вид: «Для всякого натурального числа х существует натуральное число у такое, что у = sx». Если бы мы могли использовать символ , то на этом можно было бы остановиться: аксиома записывалась бы как xy(y = sx) — скобки мы использовали, чтобы выделить свойство, которым обладают числа х и у. Так как этот символ применить нельзя, нужно выполнить еще одно действие: так как «для всякого натурального числа х существует натуральное число у такое, что у = sx» равносильно «не существует натурального числа х такого, что для него не существует натурального числа у такого, что у = sx», и вторая аксиома Пеано будет записываться так: ¬ху (у = sx). После столь подробных объяснений читатель может самостоятельно убедиться в том, что третья аксиома Пеано, «0 не следует ни за каким натуральным числом», соответствует выражению ¬х (sx = 0).

* * *

ЧЕТВЕРТАЯ АКСИОМА ПЕАНО

Переведем в формальную систему арифметики четвертую аксиому Пеано, которая гласит: «за двумя различными натуральными числами следуют различные натуральные числа». Сначала определим переменные, используемые в высказывании: это два натуральных числа, х и у. Аксиома гласит, что не могут одновременно выполняться два следующих условия: х и у различны, следующие за ними числа совпадают. Иными словами, не существует чисел х и у таких, что:

1) х отличается от у;

2) число, следующее за х, равно числу, следующему за у.

Если бы символ конъюнкции был частью определенного нами языка, то эта аксиома записывалась бы так:

Так как использовать символ конъюнкции нельзя, нужно переписать это выражение, применяя функции отрицания и дизъюнкции. С учетом того, что отрицание отрицания высказывания равносильно исходному высказыванию, четвертая аксиома Пеано примет вид:

* * *

От языка — к метаязыку

Благодаря описанному выше процессу арифметика была очищена от значений и сведена к формальному каркасу. Теперь ее аксиомы являются исключительно последовательностями абстрактных символов, а доказательства превратились в упражнения по комбинаторике. Однако мы по-прежнему можем сформулировать высказывания со смыслом: например, мы можем сказать «вторая аксиома Пеано длиннее третьей», «квантор существования упоминается во второй аксиоме Пеано два раза» или «формула ¬(0 = 1) является теоремой арифметики». Важно, что здесь речь идет уже не о формализованных высказываниях языка L, а о фразах на русском языке, которые относятся к формулам L. В этих фразах говорится уже не о числах, а о высказываниях о числах, таким образом, они выходят за пределы математики в область метаматематики. Этот переход подобен ситуации, когда один из героев романа начинает писать свой роман. Подобно тому, как литература порой превращается в металитературу, математика может превратиться в метаматематику.

Одним из важнейших открытий Гильберта было проведение четкого различия между уровнями языка, к которым принадлежат различные высказывания. Представьте себе урок английского языка, на котором учитель по-русски объясняет тонкости значения какого-то слова. В этот момент используются два языка: английский, который изучают ученики, и русский, который они используют в качестве инструмента. Это же происходит и с фразой вида «формула ¬х ¬y (y = sx) длиннее, чем формула ¬х (sx = 0)» — в ней сочетаются последовательности символов языка L и выражения «формула» и «длиннее», принадлежащие не к языку L, а к метаязыку, который мы используем, чтобы описать формальную систему, так сказать, извне. Термины «ноль», «следующее» и «равно» принадлежат к языку L, где они записываются как 0, s и = соответственно, однако слова «формула», «доказательство» и «истинный» принадлежат метаязыку и невыразимы на языке L.

Следовательно, при формализации арифметики все эти высказывания в рамках самой арифметики теряют смысл.

Но какое отношение все это имеет к парадоксам? Ведь целью программы Гильберта было избавить от них математику. Как мы отмечали в предыдущей главе, многие парадоксы связаны с самоотносимостью, которая вполне имеет право на существование в естественных языках, но нет никаких причин для того, чтобы она сохранялась в искусственных языках формальных систем. Когда мы озвучиваем парадокс Рассела на русском языке, нам кажется вполне логичным, что существует два класса множеств: одни принадлежат сами себе, другие — нет. Однако в формальной системе отношение принадлежности, примененное к двум переменным одного и того же типа, нарушает правила грамматики языка. Еще более интересным является парадокс лжеца: «эта фраза ложна». Чтобы эту фразу можно было рассматривать всерьез, формальная система должна не только допускать самоотносимость, но и содержать свойство «быть истинным», которое можно будет выразить средствами самого языка, а не только метаязыка. Гильберт ожидал, что эти две ситуации никогда не произойдут одновременно, если формализация арифметики будет проведена должным образом.

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

В этом метаматематическом доказательстве допускались не все методы: можно было использовать лишь два самых строгих, которые Гильберт назвал немецким словом finit, не слишком вдаваясь в объяснения, и которые позднее получили название финитных. Финитные методы должны были устранить все рассуждения, в которых можно было усомниться. Так, не допускались доказательства от противного, хотя этот метод использовал еще Евклид для доказательства того, что существует бесконечное множество простых чисел, а квадратный корень из двух нельзя представить в виде отношения двух натуральных чисел. Первый шаг доказательства от противного заключается в том, что мы отрицаем исходное высказывание, которое хотим доказать. Если, например, мы хотим доказать, что существует бесконечное множество простых чисел, то исходная гипотеза будет предполагать, что множество простых чисел является конечным. Затем на основе этой предпосылки нужно произвести корректные логические умозаключения, пока мы не получим абсурдное утверждение, которое будет гласить, например, что теорема арифметики, доказанная независимо от рассматриваемого утверждения, не выполняется. Все промежуточные рассуждения корректны, следовательно, единственным объяснением того, что мы пришли к абсурдному выводу, является ложность исходной гипотезы. Таким образом исходное утверждение оказывается доказанным. Часто, когда нам нужно доказать существование некоторого математического объекта, например решения некоторого уравнения, легче не найти его, а показать, что его отсутствие ведет к абсурдному заключению. Это же может произойти и в метаматематике: возможно, мы не сможем подтвердить истинность утверждения вида «формула Р доказуема», найдя явное доказательство этой формулы, однако можем предположить, что такого доказательства не существует, и в результате прийти к противоречию. Однако Гильберт не был достаточно уверен в этих методах, поэтому предпочел отказаться от них.

* * *

ПУАНКАРЕ ПРОТИВ ГИЛЬБЕРТА

Анри Пуанкаре (1854–1912), которого некоторые историки называют «последним универсальным математиком», испытывал неприязнь к тем, кто хотел свести математику к множеству формальных отношений между символами. Когда в 1899 году были опубликованы «Основания геометрии» Гильберта, Пуанкаре написал длинную рецензию, в которой критиковал автора за стремление «заставить математику функционировать подобно механическому пианино». Несколько лет спустя, когда Гильберт по-прежнему не вполне четко представлял себе различия между языком и метаязыком, он попытался доказать непротиворечивость арифметики, применив принцип индукции, то есть пятую аксиому Пеано. Пуанкаре обратил на это внимание, указав, что Гильберт попал в порочный круг: он пытался доказать непротиворечивость арифметики с помощью важнейшей аксиомы самой арифметики. И хотя Гильберт утверждал, что использовал не индукцию, а метаиндукцию, однако прав был все же Пуанкаре. И Гильберт в конце концов согласился с ним, вняв доводам своего ученика Германа Вейля (1885–1955).

Анри Пуанкаре.

* * *

Давид Гильберт был не единственным, кто отвергал неконструктивные методы. Одновременно с логицизмом и формализмом развивалась еще одна концепция, призванная разрешить парадоксы теории множеств, в которой предполагалось полно стью исключить использование бесконечности. Для интуиционистов все математические объекты были продуктами человеческого разума, следовательно, они могли существовать только в том случае, если их можно было построить. Последователи этого направления различали потенциальную бесконечность, соответствующую множествам, которые можно неограниченно расширять, и актуальную бесконечность, характерную для законченных сущностей. Интуиционисты признавали, что натуральных чисел потенциально бесконечно много, так как к любому конечному множеству вида {0, 1, 2, …, n} можно добавить новые числа, однако нельзя говорить обо всех натуральных числах одновременно. Они также не признавали закон исключенного третьего, согласно которому для любого высказывания истинным обязательно является либо оно само, либо его отрицание. Отвергнув этот закон, сторонники интуиционизма были вынуждены также отвергнуть все математические теоремы, в доказательстве которых он использовался. Сам основоположник интуиционизма, датский математик Лёйтзен Эгберт Ян Брауэр (1881–1966), был вынужден отвергнуть множество ранее полученных им самим результатов, в которых использовался закон исключенного третьего.

Интуиционисты также хотели избавиться от аксиомы выбора, предложенной Эрнстом Цермело для теории множеств. Согласно этой аксиоме, для данной совокупности множеств, конечной или бесконечной, можно выбрать по одному элементу из каждого множества и таким образом определить новое множество. Тем, кто не признавал существование актуальной бесконечности, вряд ли понравился бы подобный способ выбора элементов, который был сродни магии, не подчиняющийся никакому четкому правилу.

В ряде статей, опубликованных с 1904 по 1927 год, Давид Гильберт постепенно уточнял свою стратегию замены всех математических доказательств доказательствами, выполненными с помощью финитных методов. Кульминацией его программы должно было стать максимально строгое и четкое доказательство непротиворечивости арифметики. Однако глава Гёттингенской математической школы не мог и предположить, что некий австрийский юноша, который начал изучать в Венском университете физику, а затем и математику, попытается дополнить формалистскую программу и обнаружит, что мечте Гильберта не суждено сбыться. И более того, соберется доказать это финитными методами!

Глава 4 Теоремы Гёделя

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

Готфрид Вильгельм Лейбниц

Улицы Кёнигсберга видели многое. В этом городе семь мостов, и жители не раз задавались вопросом: можно ли пройти по всем мостам ровно один раз и при этом вернуться в исходную точку? Этого не мог сделать никто, но и доказать, что это невозможно, также не удавалось, пока в 1735 году швейцарский математик Леонард Эйлер не создал теорию графов и не дал отрицательный ответ на этот вопрос.

Сорок лет спустя Иммануил Кант гулял по тем же мостам, пытаясь определить пределы чистого разума. Давид Гильберт также родился возле Кёнигсберга, и у общества сторонников эмпирической философии было достаточно причин, чтобы совместно с Венским кружком именно в этом городе провести конференцию с 5 по 7 сентября 1930 года.

Схема решения задачи о кёнигсбергских мостах, принадлежащего Леонарду Эйлеру.

Целью конференции было определить, в какой степени в первые годы XX века удалось справиться с кризисом, вызванным парадоксом Рассела. Докладчиками на пленарном заседании стали те, кто внес наибольший вклад в развитие трех направлений, призванных разрешить кризис: логицизма, сторонники которого считали, что всю математику можно свести к логике; формализма, успехи которого заключались в проведении различий между языком и метаязыком; и интуицизма, в рамках которого предпринималась попытка исключить бесконечность из математики. Также в программу входили доклады участников, желавших представить свои последние открытия, и непринужденные беседы в городских кафе, которые, хотя и не могли сравниться с венскими, но тоже были весьма уютными.

Австрийский логик Курт Гёдель был приглашен выступить с тезисами своей докторской диссертации, открывавшей путь к математике, которой подвластно всё. Однако за то время, что прошло с момента защиты диссертации и до начала Кёнигсбергской конференции, Гёдель в своих исследованиях пришел к выводу, что мечте логиков его поколения не суждено сбыться. И хотя он не сказал об этом в своем выступлении, по окончании круглого стола, которым завершалась программа следующего дня конференции, он заявил, что располагает примерами истинных высказываний, которые нельзя доказать исходя из аксиом. Гёдель был подобен главному герою истории, который в финале произведения нашел разгадку с помощью ключа, упомянутого на первых страницах. Его слова застали собравшихся врасплох, поэтому практически не вызвали обсуждения и даже не были зафиксированы в протоколе.

Фотография Кёнигсбергского университета, известного в народе как Альбертина. Около 1900 года.

* * *

ДИАЛОГ ИЗ ФИЛЬМА «УБИЙСТВА В ОКСФОРДЕ»

(РЕЖИССЕР АЛЕКС ДЕ ЛА ИГЛЕСИА, АВТОР СЦЕНАРИЯ ХОРХЕ ГЕРРИКАЭЧЕВАРРИЯ, 2008)

Шелдон: О, я забыл, что говорю с защитником универсальной логики. Вы и полиция верите, что истину можно доказать. Исходя из неких аксиом с помощью корректных рассуждений можно прийти к верному выводу, не так ли?

Мартин: Это верно, как верно и то, что сегодня среда.

Шелдон: А что если я скажу «Все британцы лжецы»? Эта фраза будет истинной, ложной или ее нельзя будет доказать?

Мартин: Разумеется, существуют математические высказывания, которые нельзя доказать или опровергнуть исходя из аксиом. Это неразрешимые высказывания.

Шелдон: Именно. Теорема Гёделя о неполноте. Даже в мире чистой математики не все можно доказать.

Мартин: Да, я это знаю, но в нашем случае это не так.

Шелдон: Известно ли вам, что истинное и доказуемое разделяет пропасть, бездна? Мы никогда не узнаем, известны ли нам все данные о каком-либо явлении, при этом любая новая информация может изменить все.

* * *

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

Помимо открытий в области логики, Джон фон Нейман совершил важный вклад в квантовую механику.

Прибыв в Кёнигсберг в качестве приглашенной звезды, Джон фон Нейман вскоре понял, что его затмил актер второго плана, рассказавший о том, что именно могло присниться фон Нейману. Вернувшись домой, давний коллега Гильберта обнаружил, что если рассуждения австрийского математика верны, то непротиворечивость арифметики нельзя доказать в рамках самой арифметики. Фон Нейман сообщил об этом Гёделю 20 ноября 1930 года, всего через три дня после того, как Гёдель отправил в журнал Monatshefte fur Mathematik und Physik рукопись статьи «О формально неразрешимых предложениях Principia Mathematica и родственных систем I» с аналогичным выводом. Фон Нейман проникся уважением к своему коллеге, и когда весной 1931 года статья была опубликована, он прервал курс лекций в Берлине, чтобы объяснить важность открытия Гёделя, а 20 лет спустя вспоминал этот момент как «веху, видимую издалека, во времени и пространстве».

В дни проведения Кёнигсберской конференции в этом же городе находился и Давид Гильберт — он был приглашен на встречу общества немецких ученых, чтобы выступить с речью на тему «Логика и понимание природы». Эта речь прозвучала на следующий день после того, как Гёдель сделал свое заявление, и весьма вероятно, что он также находился среди ее слушателей. В своем выступлении Гильберт горячо провозгласил, что в математике не существует неразрешимых задач: «Не надо верить тем, кто сегодня с философической миной и тоном превосходства пророчит закат культуры, и впадать в ignorabimus[3]. Нет для нас, математиков, никакого ignorabimus, и, по моему убеждению, нет его и для естественных наук вообще.

Вместо дурацкого ignorabimus провозгласим наш контрлозунг: мы должны знать — мы будем знать!» Эхо выступления Гильберта еще не стихло, когда он узнал, что его программа находится под угрозой.

Теоремы о неполноте

До заявления Геделя программа Гильберта давала все основания рассчитывать на успех: ее первый этап, формализация математики, по всей видимости, был завершен Расселом и Уайтхедом в книге «Начала математики», а различные логики пытались доказать непротиворечивость классических формальных систем начиная с арифметики. Хотя еще во введении к своей докторской диссертации Гёдель предположил невозможность существования «истинных высказываний, которые нельзя вывести в рассматриваемой системе», он стремился не положить конец мечтам Гильберта, а доказать правильность его программы. Однако последние открытия того времени говорили об обратном: исследования Гаусса в области геометрии отрицали возможность создания идеально точной карты Земли; Эварист Галуа (1811–1832) доказал, что почти никакое алгебраическое уравнение нельзя решить простыми методами, а Вернер Гейзенберг (1901–1976) поставил новые задачи перед наукой, введя принцип неопределенности, согласно которому нельзя одновременно с точностью определить положение электронов и их скорость.

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

Для доказательства первой теоремы о неполноте Гедель видоизменил парадокс лжеца, превратив его в неразрешимое высказывание, которое тем не менее не содержало противоречий. Очарование этой теоремы отчасти заключается в том, что она находится всего в одном шаге от парадоксов, но никогда не делает этот шаг. Мы уже рассказывали в главе 2 об антиномии Эпименида, которая в одной из формулировок звучит как «эта фраза ложна». И действительно, если это высказывание истинно, то оно само утверждает свою ложность, а если считать его ложным, то оно должно быть истинным. Что произойдет, если вместо истинных утверждений мы будем рассматривать доказуемые? Обозначим буквой G (по первой букве фамилии Геделя) высказывание «это высказывание недоказуемо» и будем предполагать, что используемая нами система аксиом является непротиворечивой. Если G ложно, то, так как G гласит «я недоказуемо», то G является доказуемым, однако в непротиворечивой системе никакое ложное высказывание не может быть доказуемым, так как это немедленно приведет к противоречию. Если С не является ложным, оно истинное, следовательно, имеем истинное высказывание, гласящее «я недоказуемо». Таким образом, мы предположили, что исходная система непротиворечива, однако обнаружили истинное, но недоказуемое высказывание. Иными словами, непротиворечивость подразумевает неполноту.

Мы предположили, что исходная система непротиворечива… Но какая система?

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

Более подробное описание гёделевской нумерации будет приведено дальше, а пока мы укажем, что с ее помощью в арифметике можно найти утверждение, эквивалентное высказыванию «я недоказуемо». Если бы множество аксиом арифметики S было рекурсивно перечислимым и непротиворечивым, то существовала бы истинная, но недоказуемая формула Gs (мы использовали индекс S, чтобы указать, что эта формула зависит от выбранных нами аксиом и при смене системы аксиом эта формула также изменится). Гёдель поставил всех логиков перед необходимостью сделать выбор либо в пользу полноты, либо в пользу непротиворечивости. И, что было еще хуже, арифметика была не просто неполной — ее полнота была недостижимой. Когда в начале этой книги мы приводили пример с инспектором полиции, который недавно пришел на службу, читатель мог возразить, что его коллеги наверняка узнали бы, женат ли он, продлись разговор немного дольше.

* * *

«ВСЁ, ЧТО НЕ В ВАШЕМ СПИСКЕ»

Рэндел Манро (род. в 1984 году) работал в NASA, пока в 2005 году не обнаружил в себе удивительный талант смешить людей шутками на околонаучные темы. Он начал рисовать комиксы xkcd — «веб-комикс о романтике, сарказме, математике и языке». В его схематичных комиксах часто упоминаются различные понятия физики, математики и информатики. Курт Гёдель становился героем множества историй, однако лучшая из них рассказана в комиксе «Фетиши», приведенном ниже. В нем вы можете видеть трех персонажей, а рисунки поясняет текст:

«Недавно писатель Катарина Гейтс попыталась составить таблицу всех сексуальных фетишей. Она понятия не имела, что ту же задумку уже однажды провалили Рассел и Уайтхед».

Один из героев комикса говорит:

— Привет, Гёдель. Мы тут собираем полный список всех фетишей. Скажи, что тебя возбуждает?

— Всё, что не в вашем списке, — отвечает Гёдель.

* * *

Существуют неполные системы, которые перестают быть таковыми, если добавить к ним несколько аксиом. Однако в случае с арифметикой это не так: Гёдель не только привел недоказуемое утверждение Gs, но и доказал, что не имеет смысла включать его в качестве аксиомы, так как, применив аналогичный метод на множестве Т = S + Gs  — множестве аксиом, которое вновь будет непротиворечивым и рекурсивно перечислимым, — мы получим новое истинное, но недоказуемое высказывание GT. Если отрубить гидре с бесконечным числом голов одну, это не спасет нас от неполноты.

Мы обещали объяснить, как можно перевести на язык арифметики неразрешимое высказывание «я недоказуемо», однако вначале скажем несколько слов о второй теореме о неполноте. В главе 1 мы упомянули, что в противоречивой системе аксиом любое высказывание является теоремой. Следовательно, существование хотя бы одной формулы, которая не является теоремой, позволяет доказать, что рассматриваемая теория является непротиворечивой. Если можно найти всего одно недоказуемое высказывание, это автоматически доказывает непротиворечивость системы. Достаточно всего одного! Поэтому зачем рассматривать сложные высказывания, когда достаточно простейшего: 0 = 1? В начале книги мы указали, как теорема «единица отлична от нуля» выводится из аксиом Пеано. Нетрудно убедиться в том, что в любой разумной теории о числах, даже при выборе иных аксиом, ноль будет отличаться от единицы. Таким образом, заявление «арифметика является непротиворечивой» равносильно словам: формула 0 = 1 недоказуема.

И вновь мы столкнулись с высказыванием на метаязыке, однако благодаря «гёделизации» мы можем преобразовать ее в формулу о числах, которую обозначим СоnS (где S — система аксиом). В этой системе обозначений первая теорема о неполноте гласит, что из СоnS следует Gs так как если арифметика является непротиворечивой (иными словами, СоnS истинна), то Gs истинна. Здесь будет уместно напомнить, в чем заключается одно из важнейших правил дедукции, modus ponens, позволяющее выводить из логической формулы «если А, то В» и формулы А формулу В. Предположим на мгновение, что непротиворечивость арифметики можно доказать в рамках самой арифметики. Следовательно, формула СоnS является доказуемой, и, вкупе с доказательством первой теоремы о неполноте СоnS —> Gs согласно modus ponens следует доказательство Gs. Однако этот вывод абсурден, ведь Gs недоказуема! Единственный возможный вывод таков: чтобы доказать непротиворечивость арифметики, нужно выйти за ее пределы — именно об этом говорится во второй теореме о неполноте, которую сам Гедель считал «неожиданным следствием» своих исследований.

Согласно программе Гильберта, для доказательства непротиворечивости математики следовало начать с арифметики. Тем не менее вторая теорема Гёделя указывает, что если доказательство непротиворечивости арифметики существует, то в нем обязательно должны использоваться более сложные методы, чем предложенные формалистами финитные. Читатель наверняка заметил, что название статьи Геделя «О формально неразрешимых предложениях Principia Mathematica и родственных систем I» наводит на мысли о возможном продолжении. И действительно, в этой статье содержались лишь наброски второй теоремы о неполноте. Хотя все указанное в ней было верно, Гедель так и не написал вторую часть статьи, что согласуется с его образом «исследователя, который оставляет работу над деталями остальным», созданным его биографами. На самом деле Гедель объяснил все подробности доказательства Давиду Гильберту и его коллеге Паулю Бернайсу (1888–1977) во время трансатлантического путешествия — они и опубликовали первое полное доказательство второй теоремы о неполноте в 1939 году. О духе тогдашней науки свидетельствует тот факт, что сам Гильберт завершил доказательство теоремы, которая сводила на нет все его труды в течение предыдущих 23 лет.

Однако теоремы о неполноте были приняты совершенно не так, как они того заслуживали. Некоторые математики считали, что неразрешимое высказывание «я недоказуемо» — лишь любопытный частный случай, никак не влияющий на их исследования. Были и те, кто не понимал тонкую разницу между истинным и доказуемым и обвинял Гёделя в том, что он воспроизвел парадокс лжеца. К их числу относился и шестидесятилетний Эрнст Цермело, хотя он как никто другой знал, сколь тяжело бороться за идею: его аксиома выбора в свое время вызвала огромное множество критических отзывов. Словом, математическое сообщество в то время не было готово понять работу, содержавшую принципиально новые методы и касавшуюся области, которая традиционно была уделом меньшинства. Томас Кун совершенно прав, указывая в своей книге «Структура научных революций», что «открытие всегда сопровождается трудностями, встречает сопротивление, утверждается вопреки основным принципам, на которых основано ожидание». К счастью, перевод статьи Гёделя на английский язык и популярное изложение его теорем способствовали тому, что начиная с 70-х годов теоремы о неполноте постепенно обрели статус важнейших открытий в логике со времен Аристотеля.

Курт Гёдель в Институте перспективных исследований в Принстоне, Нью-Джерси.

* * *

ГЁДЕЛЬ И АМЕРИКАНСКОЕ ГРАЖДАНСТВО

Покинув нацистскую Германию, Курт Гёдель в 1940 году был принят на работу в Принстонский университет. Когда семь лет спустя он получил американское гражданство, с ним произошел анекдотичный случай. Как и остальные кандидаты, Гёдель должен был продемонстрировать на экзамене знание американской конституции. И хотя экзамен был лишь формальностью, Гёдель решил серьезно подготовиться к нему, однако во время подготовки обнаружил в Конституции США несколько логических противоречий:

— Ранее у вас было немецкое гражданство?

— Нет, австрийское! — поправил чиновника Гёдель.

— Какая разница, в любом случае — страна с проклятым диктатором. К счастью, в Америке это невозможно!

— Совершенно наоборот, — перебил Гёдель. — И я знаю, как это может случиться!

Однако чиновник, которого Альберт Эйнштейн предупредил, что Гёдель отличается от остальных кандидатов, взял нить разговора в свои руки и перешел к рутинным вопросам, сказав: «Не будем умствовать». Примерно в то же самое время некоторые логики начали формировать основы новой теории — деонтической логики, целью которой было избежать противоречий при дополнении существующих законов новыми положениями.

* * *

Гёделевская нумерация

21 июня 1851 года Адольф Андерсен, лучший шахматист того времени, встретился в одном из старейших ресторанов Лондона с Лионелем Кизерицким, преподавателем шахматного клуба в Париже, и сыгранная ими партия позже была названа бессмертной. Впечатленный стратегией Андерсена, который пожертвовал слоном, ферзем и двумя ладьями, Кизерицкий захотел отправить запись партии в свой шахматный клуб. «Белые: пятая пешка слева передвинута на две клетки вперед. Черные: пешка на той же вертикали ставится перед пятой пешкой белых. Белые: третья пешка справа передвигается на две клетки вперед. Черные: пешка, которой был сделан первый ход, бьет пешку, которой белые совершили последний ход»… Но нет! Запись выглядела вовсе не так. Ее первые символы: е2—е4 е7—е5 f2—f4 е5: f4 …». Вся запись заняла не больше трех строк!

Если бы шахматист использовал первый способ записи, стоимость телеграммы с описанием партии превысила бы стоимость счета в «Кафе де ля Режанс», где сыграть в шахматы можно было за пять франков в час.

Игроки разработали чрезвычайно краткий способ записи ходов. Для этого они, во-первых, применили старинный метод аналитической геометрии Декарта, благодаря которому каждая клетка шахматной доски стала обозначаться двумя координатами: латинской буквой от а до h обозначались вертикали, числами от 1 до 8 — горизонтали. Пешки не обозначались никак, а все остальные фигуры получили обозначения по первым буквам названий (в русской нотации: Кр — король, Ф — ферзь, А — ладья, К — конь, С — слон). Далее нотация пополнилась другими символами: взятие фигуры обозначалось буквой х (в русской нотации — двоеточием), шах — знаком умножения в русской нотации и решеткой (#) — в международной. В этой нотации последовательность символов «е2—е4 е7—е5 f2—f4 е5: f4» означает: «белые делают ход пешкой на клетку е4, черные отвечают ходом пешки на е5. Затем белые делают ход пешкой на f4, черные проводят взятие этой пешки пешкой, которая находилась на клетке е5».

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

И Гёдель вспомнил, что на семинарах по истории философии, которые он посещал во время учебы в Венском университете, профессор Теодор Гомперц рассказывал об издании Луи Кутюром отредактированных рукописей Лейбница в 1903 году.

Подобно своим гениальным предшественникам, Лейбниц потратил немало сил, чтобы положить конец вавилонскому смешению языков, которым Бог наказал людей за то, что они хотели построить башню высотой до самого неба. Для этого Лейбниц задумал универсальный язык, в котором все человеческие мысли вне зависимости от языка носителя сводились к каталогу первичных идей, каждой из которых ставилось в соответствие простое число. С помощью этой системы можно было найти числа, соответствующие производным идеям так, что всегда было возможным «извлечь базовые обозначения, их составляющие», подобно тому, как из простых чисел образуются составные. Если понятиям «вода» и «неподвижность» поставлены в соответствие, например, числа 3 и 5, то понятие «озеро» (неподвижная вода) можно выразить произведением 3·5. И напротив, если понятие озера обозначается числом 15, мы можем разложить 15 на простые множители, найти в энциклопедии основных идей те, что соответствуют числам 3 и 5, и сделать вывод, что озеро есть не более чем неподвижная вода. Так, чтобы узнать, является ли утверждение вида «А есть В» истинным, достаточно определить, делится ли число, обозначающее В, на число, обозначающее А, и «когда возникнет противоречие, необходимости в споре между двумя философами будет не более, чем между двумя математиками». Эта амбициозная программа Лейбница, открытая спустя двести лет после его смерти, никогда не была реализована, однако она подсказала Гёделю, как можно перевести метаязык на язык арифметики.

Напомним, что простые числа — это числа, которые делятся только на 1 и на самих себя: например, число 5 простое, так как не делится ни на 2, ни на 3, ни на 4, однако 6 не является простым, так как при делении на 2 дает 3. Первыми простыми числами являются 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. Путем доказательства от противного, которое так не любили интуиционисты, можно установить, что этот перечень простых чисел можно продолжать бесконечно. Большинство усилий физиков второй половины XX века было направлено на определение элементарных частиц, из которых состоит материя и которые нельзя разделить на другие, более мелкие частицы. Математикам же со времен Евклида известно, что элементарными частицами арифметики являются натуральные числа. Действительно, для любого натурального n возможны два варианта: либо n является простым, либо существует число, отличное от 1 и n, которое является делителем этого числа. Если, например, n равно 23, то мы имеем дело с первым случаем, но если n равно 30, то его можно разделить на 2.

Следовательно, исходное число не является простым. Его можно представить в виде произведения: n = а·b (в нашем случае 30 = 2·15). Мы получили два числа, для которых повторим вышеописанные действия: если оба этих числа являются простыми, процесс на этом завершается, но если одно из них не является простым, мы вновь запишем его в виде произведения сомножителей. В нашем примере 2 является простым, однако 15 можно представить в виде произведения 15 = 3·5, таким образом, 30 = 2·3·5. Так как 2, 3 и 5 — простые числа, процесс на этом завершается. В общем случае мы либо находим простой сомножитель, либо найденные нами множители постепенно уменьшаются — это гарантирует, что описанный нами процесс рано или поздно завершится. Таким образом, мы доказали основную теорему арифметики, которая гласит, что любое число можно представить в виде произведения простых множителей, которые могут повторяться. Пример: 77220 = 2·2·3 x 3·3·5·11·13. В этом случае используется сокращенная запись: 77 220 = 22· З3 х 5·11·13, где показатели степеней указывают, сколько раз повторяется каждый сомножитель.

Основная теорема арифметики утверждает, что разложение на простые множители не только существует для любого натурального числа, но и является единственно возможным (порядок множителей при этом не имеет значения). Иными словами, мы можем записать число 77 220 другим способом, например 77 220 = 3· 22·11 x З3·13, однако и в новом разложении будут использоваться те же простые множители, возведенные в те же степени.

В предыдущей главе мы показали, что «алфавит» арифметики состоит из восьми символов: 0 (число ноль), s (функция следования), ¬ (отрицание), V (дизъюнкция «или»),  (существование), = (равенство), открывающие и закрывающие скобки.

Мы также использовали переменные х, у, z для обозначения чисел. На первом этапе кодификации Гёдель предложил поставить в соответствие каждому из этих символов число от 1 до 8, переменным х, у, z — три первых числа, больших 8, как показано в таблице ниже.

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

Третья аксиома Пеано гласит, что «0 не следует ни за каким натуральным числом», и записывается в виде  Будем следовать инструкциям «гёделизации»: чтобы преобразовать эту формулу в число, сначала нужно подсчитать, сколько символов в ней используется. Их всего девять: ¬,, x, (, s, x, =, 0 и). Выберем первые девять простых чисел, а именно: 2, 3, 5, 7, 11, 13, 17, 19 и 23. Согласно таблице, ¬ отрицанию соответствует число 3, следовательно, нужно возвести простое число 2 в степень 3, то есть вычислить 23. Квантор существования  обозначается числом 5, поэтому нужно возвести простое число 3 в пятую степень: 35.

Повторив аналогичные действия, получим 511, 77, 112, 1311, 176, 191 и 238. После того как мы перемножим эти числа, формула примет вид:

23·35·511·77·112·1311·176·191·238

Описанный нами метод позволяет представить любую формулу в виде числа, которое мы будем называть числом Гёделя. Никто не мешает нам выполнить аналогичные действия и для доказательств. Напомним, что доказательство — это не более чем конечная последовательность, состоящая, например, из п формул. Следовательно, можно сначала представить в виде числа каждую из этих формул, затем выбрать n простых чисел, возвести каждое из них в степень, равную числу Геделя для каждой из формул, после чего вычислить их произведение. Таким образом, любое арифметическое доказательство сводится к одному числу.

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

Именно этот сценарий мы хотим восстановить в арифметике, так как числа никогда не смогли бы вести «двойную жизнь», как того хотел Гедель, если бы, играя одну роль, они навсегда забывали бы о другой. Благодаря основной теореме арифметики все «реакции» при «гёделизации» обратимы. Рассмотрим, почему это так.

Допустим, дано число

304 496 379 203 017 490 604 020 678 113 081 132 612 291 772 080 917 708 404 389 616 093 394 253 015 558 500 327 468 465 234 375 000,

которое мы записали специально для того, чтобы читатель представил себе наименьшие числа Гёделя. Основная теорема арифметики гарантирует, что это число можно разложить на простые множители. Если вы не хотите выполнять разложение вручную, что вполне объяснимо, то можете обратиться к веб-странице и записать в строке поиска слово «factor», а затем — это число.

Для разложения больших величин на простые множители компьютеру потребуется значительное время, однако важно другое: основная теорема арифметики гарантирует, что это разложение всегда существует и, более того, является единственным.

К счастью, наше число сравнительно невелико, поэтому его разложение на множители займет менее секунды:

23·35·511·73·115·1313·177·1913·236·292·3111·378.

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

Разумеется, не все натуральные числа являются числами Гёделя для какой-либо формулы, но даже если кто-то скажет нам, что какое-либо число не соответствует никакой формуле арифметики, мы мгновенно сможем это проверить. Например, 15 = 3·5 не является числом Геделя для какой-либо формулы, так как по условиям «гёделизации» разложение числа на простые множители должно обязательно содержать первые простые числа без пропусков, а в разложении 15 отсутствует число 2. Число 1536 = 29·3 также не соответствует никакой формуле арифметики: хотя в его разложении присутствуют первые простые числа без пропусков, число 9 не соответствует ни одному из символов алфавита.

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

1. Является ли N числом Гёделя для некоторой формулы.

2. Если число N соответствует некоторой формуле, то какой именно.

* * *

ГЁДЕЛЬ В ЛИТЕРАТУРЕ

В романе «Новые признания» (The new confessions) Уильяма Бойда главный герой снимает шедевр немого кино, однако его премьера остается незамеченной, так как в то же самое время появляются первые звуковые короткометражные фильмы. Лишь Курт Гёдель, который мимолетно появляется на страницах романа, признает талант режиссера.

В романе мексиканского писателя Хорхе Вольпи «В поисках Клингзора», опубликованном на десять лет позже, подруга главного героя, физика по имени Фрэнсис Бэкон, врывается на семинар Гёделя в Институте перспективных исследований и начинает кричать на него, обвиняя в неверности. Когда действие переносится в последние ряды аудитории, «профессор Гёдель объявляет, что не может продолжать занятия, и безудержно заливается слезами». Главным его конфликтом, объясняет автор устами фон Неймана, были не формально неразрешимые предложения, а «терзания от любви к проститутке — собственной жене». Эпизод «Новых признаний» выглядит правдоподобным, но сцена, описанная Вольпи, и жестока, и неправдоподобна.

Писатель Уильям Бойд сделал Курта Гёделя одним из героев своего романа «Новые признания».

* * *

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

Хотя мы уделили немало времени объяснениям гениального метода нумерации, на создание которого Гёделя вдохновили труды Лейбница, не следует забывать, что этот метод — лишь средство достижения цели: доказать, что в любой непротиворечивой и рекурсивно перечислимой системе аксиом существуют истинные, но недоказуемые высказывания. В начале этой главы мы указали, по какой схеме должно выполняться это доказательство: в парадоксе лжеца нужно заменить понятие истинности понятием доказуемости и получить самоотносимое утверждение, которое гласит: «я недоказуемо». Если противоречия не допускаются, то это утверждение должно быть истинным, следовательно, недоказуемым. Основная сложность, как мы уже указывали, заключается в том, чтобы найти арифметический эквивалент этого утверждения на метаязыке, в котором речь идет не о числах, а о математических теориях. Теперь в нашем распоряжении есть все необходимые методы, позволяющие это сделать. Далее мы попытаемся изложить важнейшие этапы доказательства Геделя максимально простым языком.

Нужно перевести на язык арифметики утверждение «я недоказуемо». Но что означает доказуемость утверждения в системе аксиом арифметики? Это означает, что существует доказательство, которое заканчивается нашим утверждением, то есть конечная последовательность формул, каждая из которых является либо аксиомой, либо получена из предыдущих формул с помощью правил вывода. Чтобы определить, является ли последовательность формул, которую мы обозначим Z, доказательством высказывания X, нужно показать, что Z строится по вышеуказанному правилу и что его последней формулой является именно X. Основная идея заключается в том, чтобы с помощью «гёделизации» сопоставить формулам X и Z числа Гёделя, которые мы будем обозначать строчными буквами х и z. Нам хотелось бы найти механизм D, который позволял бы для натуральных чисел х и z через определенное количество шагов дать ответ, является ли последовательность формул, соответствующая числу z, доказательством формулы с числом Гёделя х. Следовательно, высказывание D(х, z) будет истинным, если Z доказывает формулу X, и ложным — в противном случае.

Приведем простейший пример. Напомним, что число Гёделя для второй аксиомы Пеано равно

23·35·511·73·115·1313·177·1913·236·292·3111·378.

Так как определяющее свойство аксиом гласит, что они являются доказательством самих себя, то если мы подставим вышеприведенное число вместо х и z в D(х, z), результат будет истинным: последовательность формул для числа Гёделя z, состоящая в этом случае лишь из второй аксиомы Пеано, является доказательством формулы, которой соответствует число х — это вновь вторая аксиома Пеано! Однако если мы введем в качестве значения z число 23·35·511·77·112·1311·176·191·238, механизм D(х, z) выдаст результат «ложь», так как формула, соответствующая этому числу, не является доказательством второй аксиомы Пеано. Тот факт, что формула для числа Гёделя х доказуема, означает, что существует число z такое, что после довательность формул, соответствующая z, является доказательством формулы, связанной с х. Иными словами, существует z такое, что высказывание D(х, z) является истинным. Как следствие, формула z D(х, z), которую для краткости будем обозначать Dem (х), гласит, что формула, соответствующая числу Гёделя х, доказуема. Вкратце повторим вышеизложенное: если бы существовала формула D, то благодаря «гёделизации» все тонкости доказуемости высказываний можно было бы свести к простому отношению между натуральными числами х и z. Какая же теория рассматривает подобные отношения? Арифметика!

Читатель уже наверняка понял, что наиболее трудоемкая часть работы Гёделя состояла в том, чтобы доказать, что механизм, обладающий описанными выше свойствами, действительно существует. Для этого Гёделю потребовалось 46 этапов, которые мы опишем лишь вкратце. Допустим, что дано некоторое натуральное число z, кодирующее некую последовательность формул. По основной теореме арифметики мы можем разложить z на простые множители:

z = pk1·pk2·pk3·…·рkn.

Итак, мы разложили число z на простые множители, возведенные в различные степени. Так как z соответствует последовательности формул, то каждый показатель степени будет числом Гёделя для одной из этих формул. Таким образом, мы можем определить числа Гёделя для всех формул последовательности, которые обозначим

k1, k2, k3… kn.

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

— первый шаг: последовательность формул с числами Гёделя k1, k2, k3… kn является доказательством, то есть каждому из этих чисел соответствует либо аксиома, либо высказывание, которое получено из предыдущих с помощью правил вывода;

— второй шаг: последняя формула последовательности — это формула, которую мы хотим доказать.

Начнем с последнего шага, который является наиболее простым: нам дана формула, которой соответствует число Гёделя х, и мы хотим узнать, оканчивается ли последовательность высказываний этой формулой, — простейшее требование, которое должно выполняться, если речь действительно идет о доказательстве. Вышеприведенные расчеты позволяют определить числа Гёделя для каждой формулы последовательности. Последней формуле соответствует число kn, поэтому достаточно проверить, что числа х и kn равны. Никто не усомнится в том, что проверить равенство чисел очень просто.

Теперь перейдем к первому этапу нашей гонки с препятствиями и рассмотрим формулы, которым соответствуют числа Гёделя k1, k2,… kn . Именно здесь обязательно должно выполняться условие рекурсивной перечислимости системы аксиом арифметики — ранее это условие казалось не более чем причудой. Напомним, что множество аксиом S является рекурсивно перечислимым, когда за конечное число шагов можно показать, является некоторое высказывание аксиомой или нет. Следовательно, в нашем распоряжении находится формула А(х) (А — по первой букве слова «аксиома»), которая для любого числа х позволяет определить, является ли соответствующее ему высказывание аксиомой. Достаточно вычислить А(k1), А(k2)… А(kn), и мы узнаем, какие из высказываний предполагаемого доказательства являются аксиомами. Первая формула, которой соответствует число Гёделя обязательно должна быть аксиомой, так как ей не предшествуют формулы, из которых ее можно было бы вывести. Следовательно, если результат А(k1) случайно окажется ложным, дальнейшие действия не потребуются: z не является числом Гёделя, соответствующим доказательству. Предположим, что этого не произошло.

Некоторые из следующих формул, которым соответствуют числа k2, k3,… kn  будут аксиомами, другие — нет. Для тех, что не являются аксиомами, нужно показать, что они выводятся из предыдущих высказываний по допустимым правилам вывода. В своей скрупулезно выполненной работе Гёдель доказывает, что для каждого правила вывода существует формула I, которая для первых s чисел k1, k2,… ks возвращает результат «истина», если формула, обозначаемая числом Гёделя ks, выводится из формул, обозначаемых числами Гёделя k1, k2,… ks -1 (предшествующей формулы), по соответствующему правилу вывода. Например, I(k1, k2, k3, k4) будет истинной, если четвертая формула последовательности выводится из трех предыдущих по правилу вывода, обозначаемому формулой I. Таким образом, этот процесс можно выполнить для формул, которые не являются аксиомами, и если для каждой из них формула, обозначающая хотя бы одно из правил вывода, вернет значение «истина», то первый этап будет успешно завершен, и z будет числом Гёделя, обозначающим доказательство. Так как здесь нетрудно запутаться в технических деталях, выделим главное: нужно запомнить, что мы доказали существование процесса D(х, z), определяющего, является ли последовательность формул, обозначаемая числом z, доказательством высказывания, которому соответствует число Гёделя х.

Для этого достаточно выразить в виде отношений между числами правила, которым должно удовлетворять доказательство, что мы уже не раз повторили.

Отлично: в рамках арифметики мы сформулировали высказывание Dem (х), которое гласит: «формула, выражаемая числом Гёделя х, доказуема». Отрицанием этой формулы будет ¬ Dem (х), которая звучит так: «формула, выражаемая числом Гёделя х, недоказуема». Пока что все абсолютно понятно, но мы постепенно приближаемся к тому, чтобы совершить своеобразное сальто-мортале. Сначала следует напомнить, что высказывание «арифметика является непротиворечивой», которое фигурирует во второй теореме о неполноте, равносильно высказыванию «формула 0 = 1 недоказуема». Напомним также, что 1 является числом, следующим за нулем, то есть 1 = s0. Предлагаем читателю убедиться, что число Гёделя для формулы 0 = 1 равно 255150. Следовательно, высказывание ¬ Dem (255150), переведенное на язык арифметики, гласит, что «формула, обозначаемая числом Гёделя 255150, недоказуема», то есть «формула 0 = 1 недоказуема», что равносильно высказыванию «арифметика непротиворечива». Высказывание ¬ Dem (х) позволяет убить сразу двух зайцев.

Важность выражения ¬ Dem (х) заключается в том, что это уже не высказывание на повседневном языке, а арифметическая формула, в которой используются только символы 0, s, ¬, V, =, (, ) и некоторые переменные. Буквы «Dem» — это лишь сокращенный способ записи этого выражения, так как его полная запись очень сложна и занимает не одну страницу. Однако если мы захотим найти его полную запись, то сможем сделать это, используя исключительно символы алфавита арифметики. И ради этого мы потратили столько сил! У нас нет никаких сомнений, что теперь читатель знает, что нужно сделать всякий раз, когда ему встретится записанная в таком виде формула: ее нужно записать согласно гёделевской нумерации. Сопоставим выражению ¬ Dem (х) число Гёделя, которое обозначим d. Возможно, это число будет настолько большим, что во всем мире не хватит чернил, чтобы записать его, однако его размер совершенно не важен — главное, что это число будет конечным.

Вся структура высказывания «формула, обозначаемая числом Гёделя х, недоказуема», содержится в единственном числе d. Параметр х не фиксирован, он не равняется, например, 14 451937 500, а может принимать любые значения. Но если этот параметр может принимать любые значения, почему бы умышленно не принять х равным d? В этом случае мы получим высказывание ¬ Dem (d), которое гласит, что «формула, выражаемая числом Гёделя d, недоказуема», но так как d, в свою очередь, является числом Гёделя, обозначающим высказывание «формула, выражаемая числом Гёделя х, недоказуема», ¬ Dem (d) преобразуется в высказывание «формула „формула, выражаемая числом Геделя х, недоказуема" недоказуема». Нетрудно видеть, что это высказывание означает не что иное, как «я недоказуемо»[4].

* * *

НЕПОЛНОТА ЗАМОЩЕНИЙ

Замощение плоскости — это покрытие ее «облицовочной плиткой» определенной формы без промежутков и наложений. Исламское искусство содержит прекраснейшие образцы замощений, но они встречаются и в природе: так, пчелиные соты представляют собой оптимальное замощение плоскости шестиугольниками. Оно необязательно должно быть правильным: возможно, существуют другие, непериодические замощения, не обладающие какой-либо симметрией.

В 70-е годы логик Хао Ван (1921–1995) обнаружил, что если вопрос о замощении плоскости является неразрешимым в том же смысле, в каком нельзя ни доказать, ни опровергнуть высказывание «я недоказуемо», то подобные непериодические замощения плоскости существуют. Так как возможность существования подобных замощений показалась ему полностью абсурдной, он сделал вывод: этот вопрос обязательно должен быть разрешимым. Однако несколько лет спустя один из его студентов доказал, что, используя 20426 плиток разной формы, можно получить непериодическое замощение плоскости. Эта величина понемногу уменьшалась, и в итоге было найдено непериодическое замощение плоскости, состоящее всего из двух плиток разной формы.

Слева — правильное замощение плоскости, образованное одинаковыми правильными многоугольниками подобно пчелиным сотам. Справа — пример непериодического замощения.

* * *

О чем не говорится в теоремах

Заключительный этап рассуждений, в котором мы доказали, что никакое непротиворечивое и рекурсивно перечислимое множество аксиом арифметики не может быть полным, очень точно воспроизводит сцену, когда ученики возвращаются из школы домой и плачут: «Мама, я никогда не буду логиком!», а остальные — «горсточка счастливцев», о которых писал Шекспир, — улыбаются до ушей. Мы хотим, чтобы читатель этой книги оказался в числе этих немногих. Хотя, возможно, нам не удалось достичь этой цели, и те, кто хочет закричать: «Мама, я никогда не буду логиком!» или отбросить книгу в сторону, поймут, что теоремы, о которых мы только что рассказали, не имеют ничего общего с фразой вида: «После того как Гёдель доказал, что не существует доказательства непротиворечивости арифметики Пеано, которое формулируется в терминах самой арифметики, политологи, наконец, поняли, почему следовало мумифицировать Ленина и выставить его на обозрение в Мавзолее».

Следует признать, что автор этой цитаты, французский эссеист Режи Дебре, известен своим воображением, но отнюдь не невежеством: он родился в 1940 году и изучал философию у Луи Альтюссера в Высшей нормальной школе Парижа. Он находился в тюремном заключении в Боливии, но был освобожден после начала международной кампании в его поддержку, в которой участвовали Жан-Поль Сартр и папа римский Павел VI — трудно найти более непохожих друг на друга людей. В свободное от политики время Дебре начал работу над своим трудом, сегодня насчитывающим около пятидесяти книг, среди которых «Происхождение политики», из которой и взята цитата о Ленине.

Пример Режи Дебре не единственный: другие интеллектуалы, например философы Жиль Делёз и Юлия Кристева, психоаналитик Жак Лакан и архитектурный критик Поль Вирильо, использовали прием, который французский философ Жак Бувресс называл «головокружением аналогий». Они выводят из логического высказывания, носящего сугубо технический характер, некий общий вывод, не имеющий никакого отношения к математике, но псевдонаучный вид которого, несомненно, произведет впечатление на читателя.

Гораций писал, что однажды выпущенное слово улетает безвозвратно. Помимо цитат, приведенных в этой книге, читатель может самостоятельно ознакомиться с оригинальными произведениями Юлии Кристевой, Режи Дебре, Жака Лакана, Жиля Делёза и Поля Вирильо и решить, являются их слова доказательством того, что не следует рассуждать о неизвестном, или, напротив, они как нельзя лучше подтверждают огромную притягательность некоторых теорем, которые — повторим вслед за Джоном фон Нейманом — являются вехой, видимой издалека, во времени и пространстве. Далее мы расскажем только о тех, кто прекрасно понимал, о чем говорит, и на сцену выходит один из величайших гениев в истории — Алан Мэтисон Тьюринг.

Глава 5 Машины Тьюринга

На что я могу надеяться?

Иммануил Кант

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

Она боялась забыть малейшие подробности истории, которую собиралась рассказать всему миру, когда закончится война. Р-у-с-с-к-о-й. Последнее слово появилось с небольшим опозданием, но Бетти могла праздновать очередную победу союзных войск: ей удалось перехватить сообщение «Европа никогда не будет русской». Было 15 апреля 1945 года, и с этой фразой Адольф Гитлер обратился к высокопоставленным членам нацистской партии.

Они не единственными получили умоисступленное сообщение диктатора за две недели до его самоубийства: Гиммлер и не подозревал, что его переписку с Гитлером читало одновременно десять тысяч человек в маленьком поселке в восьмидесяти километрах от Лондона, надежно спрятанном, чтобы избежать бомбардировок. Именно там в 1939 году была создана правительственная школа кодов и шифров, которая занималась расшифровкой сообщений, кодируемых нацистами на машине «Энигма» — самой совершенной шифровальной машине того времени. «Энигму» в 1918 году начал производить инженер Артур Шербиус. Вначале он продавал машину частным лицам, однако потом ее потенциал оценили немецкая армия и флот, и «Энигма» начала широко использоваться военными, службой безопасности и разведкой. Когда войска вермахта вторглись в Польшу в начале сентября 1939 года, методы шифрования «Энигмы» достигли такой сложности, что возможность их взлома даже не рассматривалась.

И лишь совместная работа группы, состоявшей из математиков, физиков, переводчиков и уже упомянутых нами женщин — победительниц конкурса кроссвордов, помогла разгадать загадку дьявольской машины, которая посредством электрических импульсов и системы роторов преобразовывала одну и ту же букву, записанную два раза подряд, в разные символы. Одетые в костюмы пиратов, словно скучающая знать, ищущая развлечений в годы войны, первые дешифровщики в 1939 году разместились в бараках рядом с викторианским поместьем. Ни одна душа в соседнем поселке не должна была заподозрить, какую важную задачу решали обитатели Station X — так назывался центр в сообщениях союзников, отправляемых на передовую. Даже Уинстон Черчилль называл Блетчли-парк «курицей, несущей золотые яйца, которая никогда не кудахчет».

Справа — немецкие военные кодируют сообщения на машине «Энигма», один из экземпляров которой изображен на рисунке слева.

Вверху — зал Блетчли-парка, в котором происходила расшифровка кодов «Энигмы». Внизу — современная фотография поместья.

Поляки заметили одну особенность «Энигмы», делавшую ее уязвимой: каждая буква вне зависимости от положения всегда кодировалась одной и той же буквой. И все равно потребовалось ответить еще на много вопросов, прежде чем за пять дней до высадки союзников в Нормандии обитатели Блетчли-парка смогли отпраздновать расшифровку секретного сообщения Гитлера. В сообщении утверждалось, что американский десант высадится в Кале, почти в трехстах километрах к северо-востоку от пляжа Арроманш. Возможно, высадка союзников вообще не состоялась бы, если бы не была получена информация о местонахождении нацистских подлодок, которую удалось расшифровать в Station X. Это было особенно удивительно, если учесть, что в 1939 году у дешифровщиков не было ни одной машины «Энигма», на которой можно было бы проверять свои гипотезы.

Работая день и ночь сменами по восемь часов, дешифровщики из Блетчли-парка сконструировали прототип машины, идентичной той, что находилась в руках у на цистов, однако успех предприятия был бы невозможен без юного английского математика, которого многие студенты Кембриджа сравнивали с греческим «богом из машины»: он появился словно из ниоткуда, чтобы помочь выиграть войну. Без Алана Тьюринга (1912–1954) было бы нелегко понять, что во всех сообщениях обязательно упоминались дата и время, к которым они относились, и именно с этого следовало начинать их расшифровку.

Статуя Алана Тьюринга из угольного сланца работы британского скульптора Стивена Кеттла рядом с портретом Тьюринга, который хранится в Национальном музее компьютеров в Блетчли-парке

(источник: Джон Каллас).

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

* * *

ДИАЛОГ ИЗ ФИЛЬМА «ВЗЛОМАТЬ КОД»

(РЕЖИССЕР ХЕРБЕРТ УАЙЗ, АВТОР СЦЕНАРИЯ ХЬЮ УАЙТМОР, 1996)

Дилли Нокс: Я ознакомился с некоторыми подробностями вашей работы, господин Тьюринг, и должен признаться, что многие из них мне непонятны.

Тьюринг: Меня это не слишком удивляет.

Дилли Нокс: Когда я был молод, я был неплохим математиком, но некоторые фразы совершенно сбивают меня с толку. Например, вот эта: «О вычислимых числах в приложении к проблеме разрешения». Можете сказать что-либо по этой теме?

Тьюринг: Что именно?

Дилли Нокс: Не знаю, что-нибудь, несколько слов, объясните в общих чертах.

Тьюринг: Несколько слов?

Дилли Нокс: Да.

Тьюринг: В общих чертах?

Дилли Нокс: Да, если это возможно…

Тьюринг: Хорошо. В общих чертах — речь идет об истинном и ложном. Это техническая статья по математической логике, в которой также рассматривается, как трудно отличить истинное и ложное. Люди, то есть многие люди, думают, что в математике всегда известно, что истинно, а что нет, но это не так! И это никогда не будет так! Это проблема, над которой математики работают уже сорок или пятьдесят лет. Как вам это объяснить? Нужно понять, как отличить истинное отложного, понимаете? […]

Дилли Нокс: На самом деле не совсем, но теперь мне кое-что понятно. Ваши идеи кажутся мне весьма оригинальными, и я убежден, что вы станете ценным членом нашей команды или группы — называйте ее как угодно.

* * *

Думать как машина

Постройка «Бомбы», или «Колосса», первого программируемого компьютера, также изготовленного в Блетчли-парке, вписывалась в череду открытий, восходящую как минимум ко второму десятилетию XVII века, когда немецкий астроном Вильгельм Шиккард (1592–1635) создал первые «часы для счета» — хитроумный механизм, способный выполнять сложение, вычитание, умножение и деление.

За Шиккардом следовал Блез Паскаль (1623–1662), в девятнадцать лет начавший работу над своей вычислительной машиной, чтобы облегчить труд отца — сборщика налогов в Руане. Его «Паскалина» произвела фурор в аристократических салонах, вызвав удивление ученых и членов знатных семейств. Там же ее увидел и Готфрид Лейбниц (1646–1716). Он был убежден, что «терять время на вычисления, подобно рабам, недостойно выдающихся людей», поэтому неудивительно, что «Паскалина» вызвала у Лейбница большой энтузиазм и желание немедленно ее усовершенствовать. Ученый мечтал создать машину, способную распознавать все истинные высказывания.

«Паскалина», придуманная французским ученым Блезом Паскалем, стала первой вычислительной машиной в истории.

В начале XIX века вычислительные машины Паскаля и Лейбница вдохновили английского математика Чарльза Бэббиджа (1791–1871) и его ученицу Аду Байрон (1815–1852) на исследования по теории вычислений. Для создания аналитической машины (Analytical Engine) Бэббидж и Байрон выделили обязательные элементы всех процессов в информатике. Во-первых, должна существовать программа, указывающая операции, которые нужно выполнить. Она представляет собой ряд инструкций, которые на основе множества входных данных позволяют вычислить результат, возвращаемый пользователю на выходе программы. Например, на вход программы «умножить» подаются пары чисел вида (2, 3), выводом является их произведение — в этом случае 2·3 = 6. Чтобы программа (далее мы будем называть ее алгоритмом) могла быть исполнена, необходимы процессор, выполняющий инструкции, и память, в которой хранятся входные данные, инструкции и все промежуточные расчеты. В аналитической машине Бэббиджа входные данные вводились с помощью перфорированных карт, которые использовались в ткацком станке Жаккара, предназначенном для автоматического создания узоров.

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

Используя тот же подход, что и Ада Байрон, Алан Тьюринг смог заложить основы теории алгоритмов в статье «О вычислимых числах в приложении к проблеме разрешения», опубликованной в 1937 году в журнале Proceedings of the London Mathematical Society. В то время как Бэббидж на смертном одре был убежден, что, проживи он еще несколько лет, и его аналитическая машина стала бы известной всему миру, Байрон и Тьюринг поняли, что прежде чем можно будет сконструировать первый компьютер, необходимо значительно продвинуться в теории алгоритмов. Наибольших размышлений требовал вопрос, какие задачи можно решить с помощью машины Бэббиджа, а какие — нет. Нечто подобное происходит сегодня с квантовыми вычислениями, теория которых заметно отстает от практических результатов, полученных в попытках сконструировать первый квантовый компьютер.

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

Вверху — памятная марка, выпущенная в честь столетия со дня рождения Чарльза Бэббиджа. Внизу — табличка у садов Барселоны, посвященных Аде Байрон

(фото: Анна Наварро Дюран).

* * *

ЧИСЛА БЕРНУЛЛИ

В одной из известнейших историй о Карле Фридрихе Гауссе рассказывается, что как-то раз его учитель в начальной школе захотел немного передохнуть и дал ученикам задание сложить все числа от 1 до 100. Учитель не рассчитывал, что юный Гаусс мгновенно найдет ответ, применив метод, который он затем использовал для вычисления суммы чисел от 1 до 1000. Пусть нужно найти сумму всех натуральных чисел, предшествующих числу n. Идея Гаусса заключалась в том, чтобы записать сумму 1 + 2 + … + n в обратном порядке и воспользоваться симметрией ее членов так, как показано ниже:

Читатель легко может убедиться, что если сгруппировать каждое слагаемое с тем, что записано под ним, их сумма всегда будет равна n + 1. Так как этот процесс повторяется n раз, результатом сложения будет n(n + 1). Однако в этой сумме каждое число учитывается дважды: один раз — в первом ряду, один раз — во втором. Следовательно, полученную сумму нужно разделить на два:

Читатель спросит, сможем ли мы, заменив первые n чисел на первые n квадратов, получить похожую формулу. Применив несколько более сложный метод, можно доказать, что

и что сумма первых n кубов рассчитывается по формуле

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

* * *

Вычислимые функции

Первым успехом Тьюринга стало определение вычислимой функции. Далее всякий раз, когда мы будем говорить о функции, мы будем иметь в виду функцию, определенную на множестве натуральных чисел и принимающую натуральные значения. Напомним, что функция — это не более чем способ сопоставить каждому числу другое число, которое мы будем называть отображением первого. Чтобы лучше понять изложенное ниже, читатель может представить функцию как машину, которая придает форму закладываемому в нее материалу. Так, наша функция превращает число 3 в другое число, которое мы будем обозначать f(3), где f — первая буква латинского слова «функция». Процесс получения f(n) по известному n может описываться последовательностью алгебраических операций или более сложной словесной формулировкой. Например, если эта функция сопоставляет каждому числу следующее за ним (как вы уже знаете из предыдущих глав, эта функция используется в аксиомах Пеано), то мы можем записать f(n) = n + 1, и результатом будет f(3) = 3 + 1 = 4. Если же, напротив, функция определяет n-е простое число, то f(3) будет равно 3, а f(4) будет равно 7, так как первыми простыми числами являются 2, 3, 3, 7, 11. В этом случае функция задается словесным описанием, а не простой формулой, определяющей значение функции в каждой точке.

Образ машины может быть обманчивым, и читатель, возможно, поверит, что идеальная машина Тьюринга, о которой мы говорим, в состоянии вычислить значение любой функции, которую только можно себе представить. В действительности дело обстоит с точностью до наоборот: действия, скрытые между входным значением n и выходным значением f(n), могут быть настолько сложными, что даже машина Тьюринга будет неспособна их выполнить. Чтобы читатель лучше понимал эту ситуацию, необходимо подробно объяснить, как работают машины, которые придумал Алан Тьюринг, когда ему было немногим больше двадцати лет.

Первым элементом машины Тьюринга является лента, не имеющая начала и конца (напомним, что речь идет об идеальной машине), разделенная на ячейки. В каждую ячейку помещается только один символ — 0 или 1. Эти символы соответствуют, как известно, двум возможным значениям истинности. Вторым элементом машины Тьюринга является устройство чтения-записи, способное определять, какой символ записан в определенной ячейке, и производить запись поверх него.

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

Принцип действия машины Тьюринга

 (источник: «Complexity» Мелани Митчелл).

Как мы уже упоминали, инструкции нумеруются начиная с 1, используются символы 0 и 1, а допустимыми операциями являются запись 0 (0), запись 1(1), переход на ячейку вправо (R), переход на ячейку влево (L) или останов (N). Таким образом, любую инструкцию можно описать всего четырьмя параметрами. Если первая инструкция звучит так: «Если считан символ 1, сместиться влево и перейти к третьей инструкции», достаточно записать (#1, 1, L, #3). Читатель уже наверняка понял, что для каждой ячейки требуются две инструкции: одна указывает, что нужно делать, если считан символ 0, другая указывает, что нужно делать, если считан символ 1. Если в предыдущем примере третья инструкция указывает только действие, выполняемое в случае, если считан 0, но в действительности считан символ 1, то машина не сможет продолжить работу. Возможное решение этой проблемы может выглядеть так: в случае когда машина Тьюринга не имеет четких инструкций (а сама по себе она не способна «придумать», что делать дальше), она останавливается.

Чтобы сделать объяснение более понятным, укажем явно инструкции для всех возможных случаев. Рассмотрим очень простой пример с машиной Тьюринга Т, для которой заданы следующие три команды.

Инструкция № 1: Если считан 0, записать 1 и перейти к инструкции № 3.

Инструкция № 1: Если считан 1, сместиться вправо и перейти к инструкции № 2.

Инструкция № 2: Если считан 0, записать 1 и перейти к инструкции № 3.

Инструкция № 2: Если считан 1, остановить выполнение.

Инструкция № 3: Если считан 0, записать 1 и перейти к инструкции № 1.

Инструкция № 3: Если считан 1, остановить выполнение.

При кодировании машины Тьюринга согласно описанной системе возникает вопрос: что делать, когда машина останавливается? Ведь в этом случае не указано, какая инструкция должна быть следующей. Простейшим решением будет приписать символ 0: это гарантирует отсутствие ошибок, так как машина Тьюринга попытается найти инструкцию 0, но ни одна из инструкций не обозначена этим числом. Применив этот прием, запишем следующую последовательность инструкций, полностью описывающих работу Т:

Теперь посмотрим, как будет действовать машина, если на ее вход подать ленту, на которой записаны только нули. Стрелка указывает положение считывающей головки машины Тьюринга в каждый момент времени.

Программа начинает выполнение первой инструкции. Так как считан 0, а инструкция гласит «Если считан 0, записать 1 и перейти к инструкции № 3», достаточно заменить 0 на 1 и посмотреть, как звучит третья инструкция.

Инструкция № 3 состоит из двух частей: первая указывает, что если считан 0, то нужно записать 1 и вернуться к инструкции № 1, однако согласно второй части этой инструкции, если считан символ 1, машина Тьюринга должна остановить работу. Так как в этом случае считан именно символ 1, программа прекращает выполнение. Следовательно, если подать на вход машины Тьюринга ленту, заполненную нулями, Т остановится после того, как запишет 1 в исходной точке.

Рассмотрим, что произойдет, если мы снова подадим на вход программы ленту, которую только что получили. Входные значения будут выглядеть так.

Начнем с первой инструкции: так как считан символ 1, нужно сместиться вправо и перейти к инструкции № 2. Никакой загадки нет.

Теперь, согласно инструкции № 2, если считан 0, машина Тьюринга должна заменить его на 1 и перейти к инструкции № 3. Последуем этой инструкции.

И вновь, согласно инструкции № 3, машина Т должна остановиться, если считан 1, следовательно, программа прекратит выполнение, а результатом ее работы будет лента, на которой записаны две единицы посреди бесконечного множества нулей, при этом устройство чтения-записи будет располагаться рядом с единицей, записанной справа. Если мы вновь запустим эту машину Тьюринга, в результате получим ленту, на которой будет записано три единицы, таким образом Т вычисляет не что иное, как значение функции f(n) = n + 1. В общем случае функция является вычислимой, если существует машина Тьюринга, вычисляющая каждое из ее значений.

Допустим, что натуральное число n закодировано, как мы показали в предыдущем примере, путем ввода бумажной ленты, на которой записано n единиц посреди бесконечного множества нулей справа и слева, при этом устройство чтения-записи расположено на ячейке с последней единицей. Функция f будет вычислимой, если существует такая машина Тьюринга, что при вводе произвольного значения n описанным способом ее выходным значением будет f(n). Мы доказали, что функция «прибавить единицу» является вычислимой на машине Тьюринга. Так как для вычисления функции f(n) = n + 2 достаточно выполнить это же множество инструкций два раза, а для вычисления f(n) = n + 3 — трижды, операция сложения является вычислимой. Вычислимой является и операция умножения, поскольку умножить 3 на 3 означает сложить число 3 с самим собой три раза или сложить число 3 с самим собой пять раз. Мы указали, что функция является вычислимой, если существует машина Тьюринга, вычисляющая каждое из ее значений, но это не означает, что мы всегда можем найти такую машину. Рассмотрим, например, функцию, которая принимает в качестве входных и выходных значений только нули и единицы. Следовательно, достаточно определить значение f(0), которое может равняться 0 или 1, и f(1), которое также будет иметь одно из этих значений.

Читателю несложно убедиться, что существует всего четыре функции с подобными свойствами: та, которая всегда возвращает значение 0; та, значение которой всегда равно 1; та, которая при входном значении 0 принимает значение 0, при входном значении 1–1, и та, которая сопоставляет числу 0–1 и наоборот, числу 1–0.

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

Пусть на множестве чисел от 1 до 9 определена некая функция, которая ставит в соответствие n значение 1, если десятичная запись числа π содержит n последовательных цифр n (например, число 4444 для n = 4), и 0 в противном случае. Согласно этому определению f(1) равно 1, так как десятичная запись π, которая начинается с 3,141592 …, содержит 1 (это первый знак после запятой).

Аналогично f(2) также равно 1, однако чтобы найти первую последовательность цифр 22, нужно просмотреть 135 первых знаков π: …44609550582231725359408.

Следующая таблица была составлена с помощью программы для подобных экспериментов, которая находится на сайте .

Из таблицы видно, что наша функция принимает значение 1 для первых восьми натуральных чисел, так как запись числа π содержит последовательности цифр 333, 4444, 55555, 666666, 7777777 и 88888888. Чтобы вычислить значение f(9), можно написать программу, которая будет обходить все знаки π, пока не будет найдена искомая последовательность из девяти девяток подряд. Если такая последовательность в записи π действительно существует, то программа обязательно обнаружит ее, и функция примет значение 1. Время выполнения программы в данном случае не имеет значения, поскольку, как мы неоднократно указывали, речь идет об идеальной машине, не имеющей физических ограничений, свойственных компьютерам. Однако если последовательность из девяти девяток подряд в записи π отсутствует, программа никогда не остановится, и мы не сможем определить значение f(9). Следовательно, мы никогда не сможем узнать, является ли функция f вычислимой, если только не докажем, что в записи числа π присутствует последовательность из девяти девяток подряд. Однако в этом случае программа будет бесполезной, так как из нашего доказательства будет следовать, что f(9) равно 1. Эта функция является вычислимой, хотя на первый взгляд может показаться, что это не так.

* * *

А ЧТО, ЕСЛИ ВСЕ ЕСТЬ ЧИСЛО?

В своем рассказе «Вавилонская библиотека» аргентинский писатель Хорхе Луис Борхес предполагает, что вся информация во вселенной может содержаться в единственной книге, которая «содержит бесконечное число бесконечно тонких страниц». Но зачем хранить информацию в этом громадном томе, если, возможно, она поместится в одно число? Одна из самых таинственных гипотез современной математики заключается в том, что в десятичной записи числа π, равного отношению длины окружности к ее диаметру, рано или поздно встречается любая числовая последовательность. Если это в самом деле так, то в записи этого числа содержится не только последовательность 999999999, но и числовая последовательность, кодирующая любое сообщение прошлого, настоящего и будущего.

* * *

Чтобы доказать это, нужно рассуждать точно так же, как мы рассуждали выше: так как число функций, определенных для чисел от 1 до 9 и принимающих значения 0 и 1, является конечным (в нашем случае таких функций 512 — управиться с ними будет несколько труднее, чем с функциями, определенными только для 0 и 1 и принимающими значения 0 и 1), существует машина Тьюринга, вычисляющая значение каждой из них. Это пример вычислимой функции, машину Тьюринга для которой мы не можем описать в явном виде.

Другим классом вычислимых функций являются рекурсивные функции, то есть такие функции, в которых значение f(n) можно вычислить на основе значений, которые принимает эта функция для других чисел, меньших n. Большинство функций, постоянно используемых в математике, являются рекурсивными, но все ли они вычислимы? Алан Тьюринг моментально дал отрицательный ответ на этот вопрос: существует множество функций, значение которых не сможет вычислить ни одна машина Тьюринга, более того, если выбрать функцию произвольным образом, то она почти наверняка не будет вычислимой. В то же время по другую сторону Атлантики логик Алонзо Чёрч (1903–1995) из Принстонского университета пришел к тем же выводам, разработав формальную систему, которую он назвал лямбда-исчислением. Обе эти идеи были столь новаторскими, что единственным, кого смогли найти редакторы журнала Proceedings of the London Mathematical Society для рецензирования статьи Тьюринга, оказался именно Чёрч. Так началось их плодотворное сотрудничество, прервавшееся на время войны, результатом которого стал принцип, сегодня известный под названием «тезис Чёрча — Тьюринга». Возможны и другие определения вычислимой функции, но если принять этот тезис, то все они будут эквивалентны существованию машины Тьюринга, вычисляющей значения функции.

Алонзо Чёрч, коллега Тьюринга и создатель лямбда-исчисления.

Чтобы доказать, что почти никакие функции не являются вычислимыми, Алан Тьюринг использовал хитроумный вариант диагонального метода Кантора, рассмотренный в главе 2. В ней мы рассказали, что не существует способа упорядочить список последовательностей, состоящих из нулей и единиц. Когда мы предполагали, что можем расположить одну последовательность после другой, изменяя значения элементов по диагонали, нам удалось сформировать последовательность из нулей и единиц, которая не совпадала ни с одной последовательностью в списке. Аналогичным образом можно показать, что множество функций не является счетным.

Мы указали, что функция — это отображение, сопоставляющее 0 и f(0), 1 и f(1), 2 и f(2) и т. д. до бесконечности. Следовательно, вся информация f содержится в последовательности чисел f(0), f(1), f(2), f(3)… Для простоты будем рассматривать только функции, которые принимают значения 0 и 1, например функцию f, значение которой равно 0 для четных чисел и 1 — для нечетных. В этом случае вся информация f содержится в последовательности 0101010101…, так как если мы хотим найти отображение n, достаточно перейти к n-му члену этой последовательности. Надеемся, мы убедили читателя, что функции, которые принимают только значения 0 и 1, эквивалентны бесконечным последовательностям нулей и единиц. Следовательно, множество функций не является счетным!

Каждая машина Тьюринга вычисляет значение единственной функции, поэтому утверждать, что все функции являются вычислимыми, можно, лишь доказав, что существует по меньшей мере столько же машин, сколько и функций, значения которых мы хотим вычислить. Однако Тьюринг установил, что бесконечное множество его машин намного меньше. Чтобы показать, что множество функций не является счетным, сначала следовало записать их в виде последовательностей из нулей и единиц. Мы можем записать в виде символов любую машину Тьюринга, поскольку она представляет собой конечную последовательность инструкций, и каждую из них можно записать несколькими символами. Как вы уже увидели, (#1,1, L, #3) означает то же, что и «Инструкция номер 1: если считан символ 1, сместиться влево и перейти к третьей инструкции». Представив машину Тьюринга как последовательность инструкций, читатель сможет найти способ, позволяющий записать все возможные машины Тьюринга в виде списка.

Больший интерес для нас будет иметь процесс «гёделизации», рассмотренный в главе 4. Он заключается в присвоении огромных натуральных чисел каждой формуле логики первого порядка так, что по известному числу можно восстановить исходную формулу. Этот метод, примененный к машинам Тьюринга, позволяет свести всю информацию, содержащуюся в программе, к одному числу. Как и в случае с «гёделизацией», машины Тьюринга соответствуют не всем числам, а только тем, которые обладают определенными свойствами. Хотя существует бесконечное множество машин Тьюринга, его размеры не могут превышать размеры множества натуральных чисел, так как всякая машина Тьюринга кодируется с помощью натуральных чисел.

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

Проблема остановки

Лейбниц, а в начале XX века и Давид Гильберт — мечтали создать машину, способную отличать истинные высказывания от ложных. Как мы отметили в главе 3, программа Гильберта по «очистке» математики от парадоксов заключалась не только в формировании ее устойчивого фундамента — с этим справились древние начиная с Евклида, и пока что основы математики стояли прочно. Для абсолютной уверенности в том, что в будущем никакой Рассел не вытащит из рукава новый парадокс, помимо укрепления логической структуры математики, требовалось рассчитать метаматематические структуры, чтобы доказать, что они способны выдержать вес всего здания науки. Первые два вопроса, которыми задался Гильберт, звучали так: является ли математика полной и непротиворечивой, иными словами, совпадает ли истинное и доказуемое, и нет ли риска столкнуться с противоречиями в математике. За три года до того, как Гёдель доказал, что для арифметики эти требования несовместимы, Давид Гильберт и его ученик Вильгельм Аккерман (1896–1962) добавили к этим вопросам еще один, который был изложен на первом пленарном заседании Международного математического конгресса в 1928 году.

Проблема разрешения (Entscheidungsproblem) заключалась в том, чтобы доказать существование алгоритма, на вход которого подается математическое высказывание, а возвращается — «истина» это или «ложь». Хотя множество аксиом должно быть рекурсивно перечислимым, для множества теорем, как вы увидите далее, это требование невыполнимо. Однако сначала воссоздадим сцену, связанную с новой проблемой Гильберта, свидетелем которой был автор этой книги. Этот случай произошел на Международном математическом конгрессе в Мадриде в августе 2006 года.

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

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

Да, всем нам хотелось бы иметь такую машину, однако Алан Тьюринг в ходе исследований, посвященных вычислимым функциям, доказал, что создать ее невозможно. Для этого он рассмотрел универсальную машину, входными значениями для которой могли выступать не только числа, но и инструкции произвольной машины Тьюринга. Если инструкции описывали то, что мы сегодня называем программой, то универсальная машина сама по себе была подобна компьютеру и была способна имитировать, по крайней мере теоретически, работу произвольной машины Тьюринга. Описав этот абстрактный компьютер, ученый на несколько лет предвосхитил архитектуру современных компьютеров, поэтому редакция журнала Time совершенно справедливо включила его в число людей тысячелетия с комментарием: «Каждый раз, когда мы нажимаем на клавишу компьютера, мы работаем с реинкарнацией машины Тьюринга». Использовав этот компьютер (которых, строго говоря, тогда еще не существовало), Тьюринг показал, что существование подобной «машины истинности» приводит к абсурдному результату.

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

Следовательно, речь идет о функции двух переменных, которая для данной пары чисел (m, n) определяет, остановится ли машина Тьюринга, описываемая числом n, когда ей на вход будет подана лента, на которой будет записано число m. Вернемся к примеру с числом π и обозначим за f число машины Тьюринга, которая просматривает десятичные знаки π в поиске требуемой последовательности. При вводе параметров (9, f) наша функция вернет значение 1, если среди знаков π обнаружится последовательность из девяти девяток подряд (так как в этом случае машина остановится), в противном случае — 0 (в этом случае машина будет продолжать работу бесконечно).

Если мы предположим, что существует машина Тьюринга Р, решающая эту проблему, мы получим противоречие. Чтобы убедиться в этом, повторим еще раз принцип действия Р: это машина Тьюринга, на вход которой подаются пары чисел (m, n) и выходным значением которой может быть одно из двух значений: 1, если машина Тьюринга Т(n) при заданном исходном значении m в определенный момент остановится, и 0 — в противном случае. Иными словами, либо не существует машины Тьюринга, обозначаемой числом n (так как не все натуральные числа обозначают какую-либо машину Тьюринга), или же она существует, но программа выполняется бесконечно долго при введенном параметре m. Такая программа, представляющая собой настоящий кошмар для специалистов по информатике, называется бесконечным циклом. Здесь важно, что если бы в нашем распоряжении находилась такая машина Т, мы с легкостью смогли бы создать другую машину Тьюринга (обозначим ее через С), входным значением которой было бы одно число m и которая действовала бы следующим образом:

— если машина Тьюринга Т(n) останавливается, когда ее входное значение равно n (иными словами, если Р(n, n) равно 1), то С не остановится никогда;

— если машина Тьюринга Т(n) бесконечно долго продолжает работу, если ее входное значение равно n (иными словами, если Р(n, n) равно 0), то С остановится, едва начав работу.

В главе 2 вы увидели, как возникает парадокс лжеца, лишивший покоя мудреца Эпименида: это происходит, когда критянин говорит, что все критяне — лжецы, или когда высказывание описывает само себя так: «это высказывание ложно». Далее мы показали, как Гёдель использовал самоотносимость для формулировки истинного, но недоказуемого высказывания, гласящего: «это высказывание недоказуемо». Теперь читатель наверняка догадается, как следует закончить рассуждения: мы определили машину Тьюринга С, которая останавливается или безостановочно продолжает работу в зависимости от того, как работает другая машина, Т(n). Но что произойдет, если на вход С подать саму машину С, то есть соответствующее ей число с?

Если машина Т(с) остановится, то С не остановится. Если, напротив, Т(с) войдет в бесконечный цикл, то С остановится. Но С и Т(с) — это одна и та же машина! Она не может одновременно вести себя по-разному! Предположив, что проблема остановки имеет решение для любых шип, мы пришли к противоречию: демон самоотносимости нашептывает нам «выбери с», но одна и та же машина будет одновременно вести себя по-разному.

Мечта Гильберта и Лейбница оказалась несбыточной. Самоотносимость сначала побудила Бертрана Рассела сформировать новые, более прочные основы математики, затем позволила Геделю доказать, что оптимизм ученых того времени был неоправданным, а теперь Тьюринг вновь использовал ее, чтобы справиться с проблемой разрешения — на этот раз самоотносимость стала свойством теоретических машин, которые позднее дали начало первым компьютерам.

Мы сказали, что логика описывает не рассуждения повседневной жизни, а способ, которым нужно рассуждать, чтобы гарантированно прийти к истинному результату. В самом деле, пока что мы рассматривали только формулы, в которых значения истинности 0 и 1 были лишены какого-либо значения. Мы всегда выбирали между белым и черным. В следующей главе мы попытаемся описать мир оттенками серого — более естественно, но менее четко.

Глава 6 Хорошо кончается то, что не кончается

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

Маргерит Дюрас

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

Нечеткая логика

Несмотря на внешние различия, все множества, которые мы рассмотрели до этого, обладали одним общим свойством: для любого элемента и любого множества на вопрос «Принадлежит ли этот элемент множеству?» можно было дать только один ответ: да или нет. Описание множества могло быть каким угодно сложным, но ответом на этот вопрос обязательно было бы «да» или «нет». Именно это произошло в примере с числами, десятичная запись которых содержит все возможные последовательности и о которых мы рассказали в предыдущей главе. Неизвестно, принадлежит π этому множеству или нет, но в любом случае на этот вопрос можно дать только один ответ. Предложения логики также подчиняются этой схеме: они либо истинны, либо ложны, и любая другая возможность исключается. Более того, два основных парадокса, которые мы рассмотрели (парадокс Рассела и парадокс лжеца), возникают именно тогда, когда даже с теоретической точки зрения невозможно ответить на вопрос «да» или «нет», невозможно определить, принадлежит некий элемент множеству или нет. Дело не в том, что закон исключенного третьего допускает исключения, а в том, что множество всех множеств, которые не являются элементами самого себя, и выражение «эта фраза ложна» формально некорректны, потому что отношение принадлежности справедливо только для объектов разных типов, а также потому, что понятие истинности принадлежит не языку, а метаязыку.

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

Несколько лет назад во многих странах произвела настоящий фурор настольная игра Scattergories. В этой игре нужно выбрать любую букву алфавита, а затем записать слова из разных областей, которые начинаются с этой буквы. Например, если нам дан список «Спорт. Названия песен. Части тела. Национальная кухня. Оскорбления» и после броска игральной кости, которая имеет форму икосаэдра, выпала буква «К», ответ может звучать так: «Кёрлинг. «Катюша». Колено. Кулебяка. Кретин!». В рекламе игры Scattergories расстроенный мальчик уходит из дома, унося игру с собой, потому что его друзья сказали, что «корабль» не относится к категории «морские животные». В конце концов они решают уступить ему, так как хотят продолжить игру, но в следующем туре мальчик вновь принимается за старое: когда выпадает буква «О», он спрашивает друзей: «А осьминога можно назвать домашним животным?»

В то время как некоторых живых существ затруднительно причислить к животным, множество домашних животных определено еще хуже: к нему, конечно же, принадлежат кошки и собаки, и так же совершенно однозначно в него не входят волки и слоны. Однако хотя некоторые причислят тарантулов к множеству «животных, к которым я не хочу подходить ближе, чем на километр», другие развлекаются тем, что бросают тарантулам сверчков между прутьями клетки. Так же нечетко, как и множество домашних животных, определены и другие множества, с которыми мы имеем дело каждый день, например множество красивых людей, хороших ресторанов и смешных шуток. Первым предложил теорию, описывающую подобные ситуации, польский логик Ян Лукасевич (1878–1956). В 1917 году он представил трехзначную логику, в которой высказывания могли быть не только истинными или ложными, но и «возможными». Например, человек ростом 1,50 м низкий, человек ростом 2 м — высокий, а тот, чей рост составляет 1,75 м, является «возможно, высоким» или «возможно, низким» — все зависит от того, с кем мы его сравниваем: с пигмеями или игроками НБА.

* * *

МЕСТЬ ЛЖЕЦА

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

* * *

Включение в перечень возможных значений истинности значения «возможно» стало настоящим прорывом за пределы черно-белого мира классической логики.

Однако этого прорыва оказалось недостаточно: значение «возможно» само по себе никак не помогает нам принимать решения. Допустим, что журналист решил подать в отставку после смены редакционной политики издания. Обозначим через Р высказывание «я не согласен с новой политикой редакции». Следовательно, классическое решение будет выглядеть так: «Если Р истинно, я ухожу» и «Если Р ложно, я остаюсь». Так как любое решение всегда сопровождается множеством тонкостей, журналист с радостью согласился бы иметь возможность выбора из трех вариантов.

Но как в этом случае следует понимать значение «возможно»? Если Р возможно, то нужно уходить в отставку или оставаться? Что отделяет одно решение от другого? Если мы хотим, чтобы наша логика позволяла принимать подобные решения, необходим более высокий уровень точности.

И здесь на сцену выходит профессор Калифорнийского университета в Беркли Лотфи Заде, который в 1965 году предположил, что значение принадлежности элемента множеству или значение истинности высказывания может описываться любым числом, лежащим на интервале от 0 до 1. Таким образом, игроки в Scattergories могут установить, что правильными ответами будут, например, только те, что принадлежат рассматриваемому семантическому полю более чем на 0,6, а журналист может решить уйти в отставку, если степень его несогласия с новой редакционной политикой будет превышать, допустим, 0,45. Заде обозначил новые множества английским словом fuzzy, которое можно перевести как «нечеткое, не имеющее четко обозначенных пределов». Следовательно, на вопрос о принадлежности элемента нечеткому множеству существует бесконечно много ответов.

Создатель нечеткой логики Лотфи Заде

(источник: Вольфганг Хюнше).

Читатель, возможно, поддастся искушению интерпретировать нечеткие множества в терминах теории вероятностей. Возможно, в этом случае объяснение станет более понятным, но говорить, что степень принадлежности элемента к множеству является вероятностью того, что он принадлежит к этому множеству, некорректно — это идет вразрез с духом нечеткой логики, предложенной Заде. Посмотрим, что происходит, когда мы бросаем в воздух монету. Мыс детства знаем, что вероятность выпадания решки равна 50 %, и это означает, что если мы подбросим монету много раз, например 10 тысяч, то примерно в половине случаев выпадет орел, в половине — решка. Но результат каждого броска будет единственным: орел или решка. Вероятность, по меньшей мере в упрощенной трактовке, отражает ограниченность наших знаний о ситуации: если бы нам с абсолютной точностью была известна сила, с которой мы подбросили монету, если бы мы могли уподобиться богу Эолу и повелевать ветрами, то смогли бы с точностью предсказать результат броска монеты. Это означает, что глубинный принцип, лежащий в основе теории вероятностей в ее простейшем понимании, совпадает с принципом классической логики, в то время как в мире нечетких множеств при броске монеты может выпасть решка, скорее решка, чем орел, скорее орел, чем решка, орел или любое из промежуточных значений, выраженных с бесконечной точностью.

В отличие от классических множеств, граница которых подобна отвесному утесу, множества, изучаемые в нечеткой логике, определяются функцией принадлежности, которая воспроизводит форму пологого склона. Рассмотрим в качестве примера множество высоких людей. Если считать, что люди ниже 1,60 м низкие, выше 1,90 м — высокие, то функция принадлежности этого множества примет следующий вид:

Функция принадлежности нечеткого множества высоких людей. График функции имеет форму склона.

Выполнив некоторые вычисления, можно доказать, что степень принадлежности тех, чей рост менее 1,60 м, к множеству высоких людей равна 0. Если рост человека больше или равен 1,90 м, он будет абсолютно точно считаться высоким, а если его рост находится на интервале между этими двумя значениями, то для определения степени принадлежности к множеству нужно умножить его рост в метрах на 10, вычесть 16, а затем разделить полученное число на 3. Если известно, что степень высоты человека равна 0,3, как, например, для автора этой книги, то этого достаточно, чтобы определить его рост.

В других случаях график функции принадлежности может иметь форму треугольника или трапеции. Если считать, например, что «слишком холодно» — это любая температура ниже +10 °C, «слишком жарко» — температура выше +30 °C, а идеальная температура находится на интервале между +18 и +22 *С, то график функции принадлежности ко множеству благоприятных температур будет напоминать изображенный на рисунке ниже. Если мы сравним этот график с климатограммами для разных городов, то сможем выбрать тот, где будет комфортнее всего жить, или, по крайней мере, исключим совсем уж неподходящие варианты.

Функция принадлежности нечеткого множества благоприятных температур. График функции имеет форму трапеции.

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

При обобщении любого математического понятия (это и попытался совершить Заде, введя нечеткую логику) нужно обязательно убедиться в том, что новая теория корректна для всех исходных объектов. Классические множества являются частными случаями нечетких множеств: для них функция принадлежности из всего бесконечного множества значений принимает только два значения: 0 и 1. Тем не менее отношение включения множества в другое, а также операции объединения и пересечения, которые, как вы увидели в главе 3, являются основными в теории множеств, обобщить не так просто. На эти и другие вопросы Заде дал ответ в своей статье, опубликованной в 1965 году.

Обозначим как А и В два нечетких множества, соответствующие функции принадлежности к которым мы будем обозначать fA и fB. Это означает, что для данного элемента х число fA (х), указывающее степень принадлежности х к множеству А, заключено в интервале от 0 до 1, и это же верно для fB(х). Использовав эту нотацию, Заде установил, что А включено в В тогда, когда для любого элемента х число fA (х) меньше или равно fB(х).

Рассмотрим пример. Вместо того чтобы считать людей ниже 1,60 м низкими, выше 1,90 м — высокими, мы понизим границу множества и будем считать низкими людей ниже 1,50 м, далее степень принадлежности ко множеству будет постепенно возрастать, как и ранее, до значения 1,90 м. Таким образом мы получим еще одно нечеткое множество высоких людей. Степень принадлежности автора к этому множеству будет равна уже не 0,5, а 0,625. Согласно Заде, первое множество содержится во втором, и это соответствует интуитивному представлению о том, что высокие люди остаются таковыми, даже если снизить нижнюю границу множества.

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

* * *

СТИРАЛЬНЫЕ МАШИНЫ С НЕЧЕТКОЙ ЛОГИКОЙ

Чтобы оптимизировать длительность и качество стирки, полезно точно указать, является одежда очень грязной, слегка грязной или практически чистой. Простейшие стиральные машины с нечеткой логикой присваивают каждой загрузке белья значение загрязнения от 0 до 1. Затем к фиксированному интервалу стирки продолжительностью в десять минут добавляется определенное время в зависимости от степени загрязнения одежды. Машина может, например, определить, что для чистого белья (0) достаточно базового времени стирки, а для очень грязного (1) — на две минуты больше. Следовательно, если мы положим в стиральную машину слегка грязную рубашку, продолжительность стирки увеличится на одну минуту. В других, более сложных моделях, с целью экономии электроэнергии учитывается степень жирности (жирные пятна отстирываются тяжелее других) и вес загруженного белья.

* * *

Сложность

«Любовь» и «справедливость» — слишком расплывчатые понятия, чтобы их можно было описать двоичной логикой. Множество оттенков серого, простирающееся между «он меня любит» и «он меня не любит», между виной и невиновностью, описывается нечеткой логикой. С ростом сложности возникает потребность в новом мышлении. Следовательно, полезно ввести оценку сложности понятий, однако само понятие «сложность» не поддается попыткам дать ему определение. Даже в царстве математики, где правит абсолютная точность, нельзя однозначно отделить сложные проблемы от простых. Именно это происходит и с машинами Тьюринга: если в прошлой главе работа с идеальными компьютерами позволила нам получить теоретические результаты, касающиеся проблем, которые не может решить машина, то теперь нас интересует, какие расчеты она может провести с учетом ограничений в объеме памяти и времени выполнения программ. Именно так, за неимением лучшего определения, мы будем отличать простые задачи от сложных.

В первом приближении мы можем определить сложность как число операций, необходимых для решения задачи. Представим коммивояжера, которому нужно посетить несколько городов, после чего вернуться в исходный. Следовательно, его целью будет максимально сократить пройденный путь. Если этими городами будут, например, Париж (П), Лондон (Л), Берлин (Б) и Рим (Р) и коммивояжер начинает поездку в Париже, то его секретарь может составить расписание шестью разными способами: ПЛБРП, ПЛРБП, ПБЛРП, ПБРЛП, ПРБЛП и ПРЛБП. Учитывая примерные расстояния Париж — Лондон (455 км), Париж — Берлин (1050 км), Париж — Рим (1435 км), Лондон — Берлин (1095 км), Лондон — Рим (1855 км) и Берлин — Рим (1515 км), можно рассчитать общую длину каждого маршрута и выбрать кратчайший из них:

Учитывая данные, представленные в таблице, оптимальным будет маршрут Париж — Лондон — Берлин — Рим — Париж или он же, но в обратном направлении: Париж — Рим — Берлин — Лондон — Париж. Но что произойдет, если коммивояжеру нужно будет посетить не три города, а четыре, пять или любое другое количество городов? Для решения этой задачи всего для двадцати городов компьютеру средней производительности потребуется 80 тысяч лет, и в свете этого возможная потеря времени от неправильного выбора маршрута уже несущественна.

Если мы попытаемся решить задачу «грубой силой», то потребуется рассмотреть уже не шесть случаев — их число будет равно произведению 1·2·3· … и т. д. до 20. Запись этого числа содержит девятнадцать цифр. В математике это число называется 20 факториал и обозначается восклицательным знаком после числа. Так, 3! = 1·2·3 = 6; 4! = 1·2·3·4 = 24; в общем случае n! равен произведению первых n натуральных чисел.

Факториал — это пример функции, вычислить значение которой теоретически очень просто, однако на практике компьютеры пасуют перед этой задачей. Как мы уже отмечали в предыдущей главе, все рекурсивные функции являются вычислимыми. Напомним, что функция является рекурсивной, если значение f(n) можно вычислить на основе значений, которые принимает эта функция для чисел, меньших n. Факториал — это классический пример рекурсивной функции, так как если мы хотим вычислить 4! = 1·2·3·4, мы можем сначала найти произведение 1·2·3, а затем умножить его на 4. Но что представляет собой произведение 1·2·3? Оно равно 3! таким образом, если известно значение 3! то чтобы найти 4! достаточно одной операции. В общем случае n! = (n — 1)!·n — это доказывает, что факториал является рекурсивной, а следовательно, и вычислимой функцией. Для машины Тьюринга, способной работать бесконечное время, вычисление n! не представляет трудностей. Но на практике значения факториала возрастают столь быстро, что с ними вскоре становится невозможно работать.

График, показывающий рост значений факториала.

Предыдущий пример был бы не более чем любопытным фактом, если бы факториал не описывал число перестановок элементов конечных множеств, то есть число способов, которыми можно упорядочить их элементы. Так, фразы «3! = 6» и «множество {1, 2, 3} можно записать шестью разными способами (123, 132, 213, 231, 312 и 321)» содержат одинаковую информацию. Так как примитивный метод решения многих задач, схожих с задачей коммивояжера, требует последовательного перебора всех элементов множества, которое может быть достаточно большим, то скорость, с которой возрастают значения факториала, имеет фатальные последствия.

* * *

ИЗОБРЕТАТЕЛЬ ШАХМАТ

По легенде, персидский царь хотел наградить изобретателя шахмат и подарить ему все, что он пожелает. Тогда мудрец удивил царя просьбой, которая показалась скромной: он хотел получить одно зерно за первую клетку доски, два — за вторую, четыре — за третью и т. д. — на каждой клетке доски должно было находиться в два раза больше зерен, чем на предыдущей. Эта просьба показалась царю насмешкой, и он, рассерженный, повелел слугам немедленно исполнить просьбу мудреца и выслать ему столько зерна, сколько тот просил. Каково же было его удивление, когда один из советников на следующий день сообщил ему, что для этого не хватит зерна в амбарах всего мира. Функция, принимавшая значения 1, 2, 4, 8… возрастала столь быстро, что общее число зерен составило 18446744073 709551615.

* * *

В одном из простых определений сложными называются задачи, решение которых требует выполнения сопоставимого числа операций, а простыми считаются те, которые разрешимы не только с теоретической, но и с практической точки зрения, то есть в разумное время. Эти задачи часто обозначаются буквой Р (по первой букве английского слова «полином»), так как число операций для их решения примерно равно некоторому многочлену от времени выполнения.

Ученые заметили, что существуют задачи, найти решение которых очень сложно, а подтвердить его правильность относительно просто. Вернемся к примеру с отелем из главы 2, который на этот раз содержит конечное число комнат. Предположим, что группа из четырехсот человек хочет остановиться в отеле в те дни, когда там будет свободно всего сто номеров. Выбрать сто человек из четырехсот, не следуя какому-либо критерию, очень просто, однако заявка от группы сопровождалась одной странной просьбой: некоторые путешественники настолько не ладили друг с другом, что их нельзя было размещать в соседних номерах. Не стоит и думать, что эту задачу можно решить перебором всех возможных выборок ста человек из четырехсот, но при этом для любого предложенного решения достаточно будет подтвердить, что никакие два путешественника, которые не ладят друг с другом, не будут поселены в соседние номера. С этой задачей сможет справиться администратор отеля даже без помощи компьютера всего за несколько часов. Такие задачи, которые сложно решить, но легко проверить, математики относят к классу NP.

Пока что мы говорили о сложности задач как о неотъемлемой части их формулировки. Эта точка зрения априори ошибочна, так как сложной или простой является не задача сама по себе, а наш способ ее решения. Возможно, найденное нами решение требует выполнения множества операций, но при этом существует другое, более простое. В этом случае наше решение относится к классу NP, в то время как сама задача — к классу Р. Решение задачи о коммивояжере заключалось в переборе всех возможных маршрутов. Однако в таблице показано, что при смене порядка обхода городов на противоположный длина маршрута не меняется. Следовательно, выбор маршрута Париж — Лондон — Берлин — Рим — Париж ничем не отличается от маршрута Париж — Рим — Берлин — Лондон — Париж, поэтому достаточно рассмотреть половину исходных случаев. На практике подобное упрощение не слишком полезно, так как половина огромного числа по-прежнему остается огромным числом. Этот аспект имеет скорее философский характер: если в первом решении мы упустили из вида столь тривиальную деталь, то сколько подобных моментов мы еще не учли? Мы сказали, что наша исходная точка зрения априори ошибочна, поскольку неизвестно, существуют ли задачи, для которых сложность является неотъемлемым свойством их формулировки, а не решений. К числу таких задач, возможно, относится задача о коммивояжере, пока что никому не удалось доказать, что все ее решения являются сложными.

* * *

Р И NP

Как вы увидели в главе 3, датой символического начала математики XX века считается август 1900 года, когда Гильберт обнародовал свой список из двадцати трех задач на конференции в Париже. Вновь в Париже, но уже сто лет спустя, экспертная комиссия из Института Клэя выбрала семь открытых задач, которые, по ее мнению, обозначили направление математических исследований нового столетия. Четвертая проблема в этом списке, известная как проблема равенства классов Р и NP, заключается как раз в том, чтобы подтвердить, существуют ли задачи класса NP сами по себе или же, напротив, любую задачу, решение которой можно проверить за полиномиальное время, также можно быстро решить, найдя некий хитроумный алгоритм. Того, кто найдет решение этой проблемы, ждет премия в один миллион долларов. Как видите, математика иногда может приносить доход.

* * *

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

Однако никто, будучи в здравом уме, не скажет, что запомнить пароли 111111111111 и 6u0yfz3eq85s одинаково просто. Первый пароль можно сжать до слов «12 единиц», а второй пароль можно описать только одним способом — посимвольно. В середине 70-х годов советский математик Андрей Колмогоров на основе этого примера ввел новое определение сложности, предложив заменить число операций на число инструкций. Сложность последовательности символов стала определяться как минимальная длина алгоритма, необходимого для ее генерации.

Представим себе машину Тьюринга, задача которой — записать определенную последовательность нулей и единиц, которую мы назовем s. Как вы увидели из предыдущей главы, машине нужно дать последовательность инструкций вида «Если считано 1, сместиться вправо и перейти к инструкции № 2». В этом упрощенном варианте мы говорим, что сложностью s является натуральное число n, если существует машина Тьюринга, описанная посредством n инструкций, выходным значением которой является s, и если никакая машина не может сгенерировать заданную последовательность за меньшее число инструкций. Таким образом определяется функция К (по первой букве фамилии Колмогорова), которая сопоставляет каждой последовательности нулей и единиц ее сложность. Рассмотрим последовательность 1111… Если подать на вход машины Тьюринга ленту, на которой записаны только нули и единственная инструкция которой гласит «Инструкция № 1: Если считан 0, записать 1 и перейти к инструкции № 1. Если считан 1, сместиться вправо и перейти к инструкции № 1», то в результате мы получим последовательность 1111… Это означает, что заданная последовательность имеет минимально возможную сложность К(s) = 1, так как для ее описания достаточно единственной инструкции.

Живительное следствие этого определения сложности состоит в том, что компьютеры не могут генерировать бесконечные случайные последовательности нулей и единиц. Интуитивно понятно, что последовательность является случайной, когда невозможно предсказать, каким будет ее следующий элемент. Это означает, что описание случайной последовательности не может быть короче, чем сама последовательность.

Иными словами, ее сложность бесконечно велика. Однако все компьютерные программы содержат конечное число инструкций (вспомните определение машины Тьюринга из предыдущей главы). Следовательно, генерируемые ими последовательности нулей и единиц, сколь случайными бы они ни казались, всегда будут иметь конечную сложность. Компьютеры могут воспроизводить только псевдослучайные последовательности, поэтому для генерирования истинно случайных последовательностей многие физики пытаются использовать недетерминированность атомов.

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

Логично задаться вопросом, не приведет ли введенное нами определение сложности к противоречиям. Ответ удивляет: если бы функция К была вычислимой, то есть если бы существовала машина Тьюринга, способная вычислить для данной последовательности нулей и единиц s сложность К(s), то рассуждения, аналогичные тем, что мы использовали при решении проблемы остановки, позволили бы воспроизвести парадокс библиотекаря на формальном языке арифметики. Следовательно, единственно возможный ответ таков: сложность не является вычислимой, и этого достаточно для разрешения парадокса библиотекаря, который оставался открытым: выражение «описать пятнадцатью словами» некорректно, так как принадлежит не к языку, а к метаязыку.

Гёдель, Тьюринг и искусственный интеллект

На предыдущих страницах мы ограничились обсуждением приятия сложности исключительно с точки зрения математики, и читатель убедился, что определение этого понятия сопряжено с многочисленными трудностями. Наша изначальная цель была еще более амбициозной: мы хотели узнать, как измеряется сложность понятий «любовь» и «справедливость». Постепенно все новые и новые математические открытия вдохновили исследователей на создание новой теории сложности, которую можно обобщить фразой «целое больше, чем сумма его частей». Слова «сияние», «рана», «солнце» и «ближайший» имеют четкие значения — мы можем узнать их в словаре. Но когда французский поэт Рене Шар пишет «Сияние — рана, ближайшая к солнцу», из четырех прекрасно знакомых нам слов рождается нечто новое.

Стих представляет собой нечто большее, чем сумму слов, поэтому понять поэзию непросто.

Эта эмерджентность присуща не только языку — она характерна для так называемых общественных насекомых, с ее помощью объясняется успех интернета, и она является одним из ключей к изучению нервных систем живых существ. Представим себе, например, крохотного муравья, который в поисках пищи следует алгоритмам, заложенным в его генах. Мы никогда не смогли бы понять сложную организацию муравейника, способного приспосабливаться к экстремальным ситуациям, если бы рассматривали его исключительно как совокупность отдельных муравьев. Иммунная система также представляет собой нечто большее, чем совокупность клеток, экономика есть нечто большее, чем множество покупателей акций, а интернет — это нечто большее, чем сумма отдельных действий пользователей из разных уголков планеты. Понять, каким образом из относительной простоты отдельных компонентов этих систем возникает сложное единое целое — одна из величайших задач науки начала нынешнего столетия.

Хотя определение сложной системы как системы, в которой целое больше суммы его частей, довольно приблизительно, нет сомнений, что оно весьма точно описывает наш мозг. В этом случае отдельными компонентами системы являются нейроны — клетки, получающие импульсы, обрабатывающие их и передающие их другим нейронам посредством множества отростков. Среди исследователей мозга распространено мнение, согласно которому сеть связей, благодаря которым мозг становится чем-то большим, чем просто совокупностью отдельных нейронов, лежит в основе таких явлений, как восприятие, разум и чувства. А если бы мы могли воссоздать подобную структуру в информатике? Первые попытки математического моделирования нейронов упоминаются в статье, опубликованной в 1943 году, в которой невролог Уоррен Маккалок и логик Уолтер Питтс определили нейрон как функцию, которая на основе ряда входных значений выдает единственное выходное значение.

До этого момента все функции, рассмотренные в этой книге, имели единственное входное значение и преобразовывали его в другое значение посредством ряда операций. Однако в реальной жизни очень и очень немногие явления определяются всего одним параметром. Современная теория искусственных нейронных сетей, созданная на основе идей Питтса и Маккалока, позволяет имитировать работу мозга с помощью функций от нескольких параметров. Предположим, что мы хотим вычислить значение функции f, которое зависит от чисел х1, x2, … хn. Основная идея здесь заключается в том, что программа, в которую передаются эти числа, обрабатывает их подобно тому, как ядро нейрона обрабатывает электрические импульсы, поступающие по отросткам. Так как величина этих импульсов может отличаться, для каждого числа х нужно указать еще одно число, ил, которое называется весом и обозначает важность каждого электрического импульса по отношению к остальным. Например, если w1 и wn намного больше, чем w2, w3 … wn-1 это означает, что на результирующее значение оказывают наибольшее влияние первый и последний импульс. На основе весов импульсов в искусственной нейронной сети рассчитывается взвешенная сумма s = w1x1 + w2x2 + … + wnxn и находится значение функции, как показано на рисунке.

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

Благодаря нечеткой логике и нейронным сетям компьютеры, способные во многом имитировать деятельность человеческого мозга, перестали быть только частью научной фантастики. Решение новых задач стало главной целью новой, быстро развивающейся научной дисциплины — искусственного интеллекта. В течение многих лет считалось, что машина никогда не сможет играть в шахматы на уровне гроссмейстера. Вне зависимости от того, на сколько ходов вперед она способна просчитать игру, ей неизвестны слабые стороны противника, она не способна учесть иные психологические факторы. Машина не смогла бы обыграть человека и в азартные игры: как обучить компьютер игре в покер, если блеф противоречит очевидной выигрышной стратегии? Голоса критиков умолкли, когда в феврале 1996 года суперкомпьютер Deep Blue, ставший результатом работы компании IBM, начатой еще в 1950-е годы, обыграл Гарри Каспарова в первой партии шахматного матча. Затем, несмотря на то что Deep Blue мог оценивать сто миллионов позиций в секунду, из пяти следующих партий, которые игрались медленнее обычного, в четырех победу одержал российский шахматист. Однако годом позже машина была усовершенствована, и Deep Blue удалось одержать победу в трех партиях и еще одну — свести вничью, совершая ходы с той же скоростью, что и профессиональные шахматисты. Чемпион мира был повержен, однако это не помешало Каспарову по-прежнему отстаивать превосходство человека над машиной. Любопытно, что он приводил точно те же доводы, что и его противники, создавшие Deep Blue: «Это синтез, способность сочетать творчество и расчет, искусство и науку в единое целое, большее, чем сумма его частей».

Гарри Каспаров обдумывает очередной ход в партии против суперкомпьютера Deep Blue 10 мая 1997 года.

* * *

ДИАЛОГ ИЗ ФИЛЬМА «Я, РОБОТ»

(РЕЖИССЕР АЛЕКС ПРОЙАС, АВТОР СЦЕНАРИЯ ДЖЕФФ ВИНТАР, ПО ЦИКЛУ ПРОИЗВЕДЕНИЙ АЙЗЕКА АЗИМОВА, 2004)

Главный герой фильма, полицейский по фамилии Спунер, расследует убийство, в совершении которого он подозревает робота Санни.

Спунер: Теперь роботы могут и убивать. Прими поздравления. Отвечай!

Санни: Что это означает? (Мигает одним глазом.) Когда вы вошли и посмотрели на другого человека… Что это значит? (Вновь мигает одним глазом.)

Спунер: Это знак доверия. Это человеческое. Тебе не понять.

Санни: Отец учил меня человеческим эмоциям. Они… сложные.

Спунер: Ты хотел сказать, твой конструктор?

Санни: Да.

Спунер: Так зачем ты его убил?

Санни: Я не убивал доктора Лэннинга.

Спунер: А почему прятался на месте преступления?

Санни: Я боялся.

Спунер: Роботы не испытывают страха. Они вообще лишены чувств. Они не знают голода, им не нужен сон.

Санни: А мне нужен. Мне даже снятся сны.

Спунер: Только люди видят сны. Даже собаки их видят, а ты нет. Ты — просто машина. Имитация жизни. Может ли робот написать симфонию? Или создать шедевр живописи?

Санни: А вы можете?

* * *

Эти успехи привели к тому, что возобновились ожесточенные споры ученых и философов, начатые 50 годами ранее Куртом Геделем и Аланом Тьюрингом. Используя разные методы, Гедель и Тьюринг сформулировали одинаковые определения формальной системы и одинаково трактовали неразрешимые задачи. Однако Гёдель различал формализм и логику, механизм и разум, а Тьюринг считал эти понятия полностью синонимичными. Доведя это сравнение до предела, в 1947 году Тьюринг сформулировал следующий постулат: наилучшей моделью человеческого мозга является универсальная машина, способная имитировать поведение любой программы. Эту универсальную машину сам Тьюринг ввел, чтобы справиться с проблемой разрешения Гильберта. Тьюринг считал, что на вопрос о том, могут ли компьютеры мыслить, можно дать ответ только по итогам эксперимента. В написанной в 1950 году статье «Вычислительные машины и разум», название которой вошло в историю, Тьюринг предложил «игру в имитацию», чтобы ученые посредством ряда вопросов, передаваемых в письменном виде, могли определить, с кем они взаимодействуют — с человеком или компьютером. Суть теста заключалась в том, что если машина во всем ведет себя подобно разумному существу, то простейшее объяснение этому состоит в том, что она действительно является разумной.

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

В декабре 1969 года, спустя пятнадцать лет после смерти Тьюринга, Гёдель счел, что обнаружил в его работе ошибку, которая могла иметь серьезные последствия. Тьюринг не учел, что разум непрерывно развивается. Во время демонстрации формальные системы не претерпевают изменений, равно как и машины во время расчетов, однако ничто не может гарантировать, что живой разум не изменяется во время рассуждений. Следовательно, компьютер никогда не сможет заменить человеческий разум. В любой книге по искусственному интеллекту рано или поздно встречается раздел, посвященный аргументам Гёделя, однако они относятся не к описанной нами ситуации, а к идее оксфордского философа Джона Лукаса, согласно которой теоремы о неполноте в некотором роде имеют отношение к возможности изобретения разумных машин. Любопытно, что Гёдель никогда всерьез не думал о том, что его открытия имеют отношение к структуре человеческого разума.

Наиболее известный аргумент противников искусственного интеллекта, как мы уже сказали, принадлежит философу Джону Лукасу, который до того, как посвятить себя философии и древней истории, изучал математику. В статье «Разум, машины и Гедель», представленной в 1959 году Оксфордскому философскому обществу, Лукас удивительно простым языком объяснил, почему человеческий разум нельзя свести к компьютеру: так как мы способны обучить машину аксиомам и правилам вывода арифметики, мы можем составить все формулы языка и попросить машину определить, какие из них являются истинными. Рано или поздно компьютер дойдет до высказывания «эта фраза недоказуема» и проведет остаток вечности в попытках доказать или опровергнуть ее, в то время как мы, люди, немедленно поймем, что эта фраза является неразрешимой. «Следовательно, машина попрежнему не будет адекватной моделью разума <…> который будет всегда находиться на шаг впереди любой закостенелой, омертвевшей формальной системы», — заключал Лукас.

Прошло полвека, и уже почти никто не согласен ни с Джоном Лукасом, ни с его последователем, Роджером Пенроузом, который в 1989 году расширил и дополнил его точку зрения. Означает ли это, что мы, люди, видим истинность высказывания Гёделя? Первая теорема о неполноте гласит, что если арифметика является непротиворечивой, то высказывание «эта фраза недоказуема» является истинным, следовательно, чтобы определить его истинность, сначала необходимо определить непротиворечивость арифметики. Если мы примем непротиворечивость арифметики на веру, так как сочтем, что мир свободен от противоречий, то мы также сможем запрограммировать робота, в коде которого будет отражено ожидание того, что арифметика является непротиворечивой. Это не более чем одна из трактовок второй теоремы о неполноте, которая гласит, что непротиворечивость арифметики нельзя доказать в рамках ее формальной системы. Тем не менее, возражает Лукас, математики способны доказать непротиворечивость арифметики, обратившись к более сложным методам и языкам высших порядков. Да, мы способны выйти за рамки системы, в то время как у компьютера подобный шаг вызовет затруднения. Но что, если нам удастся обучить его этому? Что, если в очень сложной искусственной нейронной сети возникнут новые трактовки непротиворечивости? Ответ на этот вопрос не так прост, как может показаться.

Что подумал бы Евклид об отходе от аксиоматического метода? Дополнение аксиоматического метода нечеткой логикой XXI века стало бы прекрасным финалом этого романа, который начался с открытия неевклидовой геометрии, продолжился теорией множеств и ее парадоксами, а в последующих его главах на первый план вышли три героя: Давид Гильберт, Курт Гёдель и Алан Тьюринг. Это было бы прекрасным завершением нашей книги, но исследования математиков и логиков на этом не заканчиваются. За те несколько месяцев, которые пройдут, прежде чем эта книга попадет к первым читателям, математики, физики и инженеры еще больше усовершенствуют нейронные сети. Нечеткая логика, возможно, возьмет новый курс, и, быть может, кому-то удастся найти решение проблемы равенства классов Р и NP. Поэтому будет лучше, если сейчас мы поставим точку. Хорошо кончается то, что не кончается, — эта фраза станет неплохим финалом книги, главными героями которой являются парадоксы.

Библиография

BERTO F. Tutti pazzi per Godel! Roma, Laterza, 2007.

EUCLIDES Elementos, Madrid, Gredos, 2000.

FRESAN J. Codel. La logica de los escepticos, Madrid, Nivola, 2007.

HEIJENOORT J.V. From Frege to Godel: A Source Book in Mathematical Logic, Cambridge (Massachussets), Harvard University Press, 1967.

HOFSTADTER D.R. Godel Escher, Bach. Un eterno у grac'd bucle, Barcelona, Tusquets, 1987.

MARTINEZ G. у PINEIRO G. Godel V(para todos)t Barcelona, Destino, 2010.

MITCHELL M. Complexity, Oxford, Oxford University Press, 2009.

MOSTERIN J. Los logicos, Madrid, Espasa, 2000.

NAGEL E. у Newman J.R. El teorema de Godel Madrid, Tecnos, 1970.

SANGALLI A. The Importance of Being Fuzzy and Other Insights from the Border between Math and Computers, Princeton, Princeton University Press, 1998.

SMITH P. An Introduction to Godel's Theorems, Cambridge, Cambridge University Press, 2007

SOKAL A. у BRICMONT J. Imposturas intelectuales, Barcelona, Paidos, 1999.

* * *

Научно-популярное издание

Выходит в свет отдельными томами с 2014 года

Мир математики

Том 22

Хавьер Фресаи

Сон разума. Математическая логика и ее парадоксы

РОССИЯ

Издатель, учредитель, редакция: ООО «Де Агостини», Россия

Юридический адрес: Россия, 105066, г. Москва, ул. Александра Лукьянова, д. 3, стр. 1

Письма читателей по данному адресу не принимаются.

Генеральный директор: Николаос Скилакис

Главный редактор: Анастасия Жаркова

Выпускающий редактор: Людмила Виноградова

Финансовый директор: Наталия Василенко

Коммерческий директор: Александр Якутов

Менеджер по маркетингу: Михаил Ткачук

Менеджер по продукту: Яна Чухиль

Для заказа пропущенных книг и по всем вопросам, касающимся информации о коллекции, заходите на сайт , по остальным вопросам обращайтесь по телефону бесплатной горячей линии в России:

8-800-200-02-01

Телефон горячей линии для читателей Москвы:

т 8-495-660-02-02

Адрес для писем читателей: Россия, 600001, г. Владимир, а/я 30, «Де Агостини», «Мир математики»

Пожалуйста, указывайте в письмах свои контактные данные для обратной связи (телефон или e-mail).

Распространение: ООО «Бурда Дистрибьюшен Сервисиз»

УКРАИНА

Издатель и учредитель:

ООО «Де Агостини Паблишинг» Украина

Юридический адрес: 01032, Украина, г. Киев, ул. Саксаганского, 119

Генеральный директор: Екатерина Клименко

Для заказа пропущенных книг и по всем вопросам, касающимся информации о коллекции, заходите на сайт , по остальным вопросам обращайтесь по телефону бесплатной горячей линии в Украине:

0-800-500-8-40

Адрес для писем читателей:

Украина, 01033, г. Киев, a/я «Де Агостини», «Мир математики»

Украïна, 01033, м. Кiев, а/с «Де Агостiнi»

БЕЛАРУСЬ

Импортер и дистрибьютор в РБ:

ООО «Росчерк», 220037, г. Минск, ул. Авангардная, 48а, литер 8/к, тел./факс: (+375 17) 331-94-41

Телефон «горячей линии» в РБ:

+ 375 17 279-87-87 (пн-пт, 9.00–21.00)

Адрес для писем читателей:

Республика Беларусь, 220040, г. Минск, а/я 224, ООО «Росчерк», «Де Агостини», «Мир математики»

КАЗАХСТАН

Распространение:

ТОО «КГП «Бурда-Алатау Пресс»

Издатель оставляет за собой право увеличить рекомендуемую розничную цену книг. Издатель оставляет за собой право изменять последовательность заявленных тем томов издания и их содержание.

Отпечатано в соответствии с предоставленными материалами в типографии:

СгаВса Veneta S.p.A Via Malcanton 2

35010 Trebaseleghe (PD) Italy

Подписано в печать: 30.04.2014

Дата поступления в продажу на территории России: 17.06.2014

Формат 70 х 100 / 16. Гарнитура «Academy».

Печать офсетная. Бумага офсетная. Печ. л. 4,5.

Уcл. печ. л. 5,832.

Тираж: 50 000 экз.

© Javier Fresan, 2010 (текст)

© RBA Collecionables S.A., 2011

© ООО «Де Агостини», 2014

ISBN 978-5-9774-0682-6

ISBN 978-5-9774-0717-5 (т. 22) 

Примечания

1

Из письма Готлоба Фреге (1848–1925) Давиду Гильберту (1862–1943).

(обратно)

2

Перевод Н. Любимова, Б. Кржевского. — Примеч. ред.

(обратно)

3

Сокращение латинского изречения ignoramus et ignorabimus, то есть «не знаем и не узнаем». Это изречение было взято из доклада немецкого физиолога Эмиля Дюбуа-Реймона «О пределах познания природы» (1872), в котором он выразил пессимизм по поводу ограниченности научного знания.

(обратно)

4

В этой книге мы не можем абсолютно точно привести формулы, описывающие свободные переменные, замены и обобщения, которые Гедель использовал в своей статье. Однако мы полагаем, что упомянули все основные элементы его доказательства.

(обратно)

Оглавление

Предисловие

Глава 1 Аксиоматический метод

Глава 2 Парадоксы

Глава 3 Программа Гильберта

Глава 4 Теоремы Гёделя

Глава 5 Машины Тьюринга

Глава 6 Хорошо кончается то, что не кончается

Библиография Fueled by Johannes Gensfleisch zur Laden zum Gutenberg