Сон разума. Математическая логика и ее парадоксы
Шрифт:
Важность выражения ¬ Dem (х) заключается в том, что это уже не высказывание на повседневном языке, а арифметическая формула, в которой используются только символы 0, s, ¬, V, =, (, ) и некоторые переменные. Буквы «Dem» — это лишь сокращенный способ записи этого выражения, так как его полная запись очень сложна и занимает не одну страницу. Однако если мы захотим найти его полную запись, то сможем сделать это, используя исключительно символы алфавита арифметики. И ради этого мы потратили столько сил! У нас нет никаких сомнений, что теперь читатель знает, что нужно сделать всякий раз, когда ему встретится записанная в таком виде формула: ее нужно записать согласно гёделевской нумерации. Сопоставим выражению ¬ Dem (х) число Гёделя, которое обозначим d. Возможно,
Вся структура высказывания «формула, обозначаемая числом Гёделя х, недоказуема», содержится в единственном числе d. Параметр х не фиксирован, он не равняется, например, 14 451937 500, а может принимать любые значения. Но если этот параметр может принимать любые значения, почему бы умышленно не принять х равным d? В этом случае мы получим высказывание ¬ Dem (d), которое гласит, что «формула, выражаемая числом Гёделя d, недоказуема», но так как d, в свою очередь, является числом Гёделя, обозначающим высказывание «формула, выражаемая числом Гёделя х, недоказуема», ¬ Dem (d) преобразуется в высказывание «формула „формула, выражаемая числом Геделя х, недоказуема" недоказуема». Нетрудно видеть, что это высказывание означает не что иное, как «я недоказуемо» [4] .
4
В этой книге мы не можем абсолютно точно привести формулы, описывающие свободные переменные, замены и обобщения, которые Гедель использовал в своей статье. Однако мы полагаем, что упомянули все основные элементы его доказательства.
* * *
НЕПОЛНОТА ЗАМОЩЕНИЙ
Замощение плоскости — это покрытие ее «облицовочной плиткой» определенной формы без промежутков и наложений. Исламское искусство содержит прекраснейшие образцы замощений, но они встречаются и в природе: так, пчелиные соты представляют собой оптимальное замощение плоскости шестиугольниками. Оно необязательно должно быть правильным: возможно, существуют другие, непериодические замощения, не обладающие какой-либо симметрией.
В 70-е годы логик Хао Ван (1921–1995) обнаружил, что если вопрос о замощении плоскости является неразрешимым в том же смысле, в каком нельзя ни доказать, ни опровергнуть высказывание «я недоказуемо», то подобные непериодические замощения плоскости существуют. Так как возможность существования подобных замощений показалась ему полностью абсурдной, он сделал вывод: этот вопрос обязательно должен быть разрешимым. Однако несколько лет спустя один из его студентов доказал, что, используя 20426 плиток разной формы, можно получить непериодическое замощение плоскости. Эта величина понемногу уменьшалась, и в итоге было найдено непериодическое замощение плоскости, состоящее всего из двух плиток разной формы.
Слева — правильное замощение плоскости, образованное одинаковыми правильными многоугольниками подобно пчелиным сотам. Справа — пример непериодического замощения.
* * *
Заключительный этап рассуждений, в котором мы доказали, что никакое непротиворечивое и рекурсивно перечислимое множество аксиом арифметики не может быть полным, очень точно воспроизводит сцену, когда ученики возвращаются из школы домой и плачут: «Мама, я никогда не буду логиком!», а остальные — «горсточка счастливцев», о которых писал Шекспир, — улыбаются до ушей. Мы хотим, чтобы читатель этой книги оказался в числе этих немногих. Хотя, возможно, нам не удалось достичь этой цели, и те, кто хочет закричать: «Мама, я никогда не буду логиком!» или отбросить книгу в сторону, поймут, что теоремы, о которых мы только что рассказали, не имеют ничего общего с фразой вида: «После того как Гёдель доказал, что не существует доказательства непротиворечивости арифметики Пеано, которое формулируется в терминах самой арифметики, политологи, наконец, поняли, почему следовало мумифицировать Ленина и выставить его на обозрение в Мавзолее».
Следует признать, что автор этой цитаты, французский эссеист Режи Дебре, известен своим воображением, но отнюдь не невежеством: он родился в 1940 году и изучал философию у Луи Альтюссера в Высшей нормальной школе Парижа. Он находился в тюремном заключении в Боливии, но был освобожден после начала международной кампании в его поддержку, в которой участвовали Жан-Поль Сартр
Пример Режи Дебре не единственный: другие интеллектуалы, например философы Жиль Делёз и Юлия Кристева, психоаналитик Жак Лакан и архитектурный критик Поль Вирильо, использовали прием, который французский философ Жак Бувресс называл «головокружением аналогий». Они выводят из логического высказывания, носящего сугубо технический характер, некий общий вывод, не имеющий никакого отношения к математике, но псевдонаучный вид которого, несомненно, произведет впечатление на читателя.
Гораций писал, что однажды выпущенное слово улетает безвозвратно. Помимо цитат, приведенных в этой книге, читатель может самостоятельно ознакомиться с оригинальными произведениями Юлии Кристевой, Режи Дебре, Жака Лакана, Жиля Делёза и Поля Вирильо и решить, являются их слова доказательством того, что не следует рассуждать о неизвестном, или, напротив, они как нельзя лучше подтверждают огромную притягательность некоторых теорем, которые — повторим вслед за Джоном фон Нейманом — являются вехой, видимой издалека, во времени и пространстве. Далее мы расскажем только о тех, кто прекрасно понимал, о чем говорит, и на сцену выходит один из величайших гениев в истории — Алан Мэтисон Тьюринг.
Глава 5
Машины Тьюринга
На что я могу надеяться?
Иммануил Кант
«Евр…» Бетти нетерпеливо ожидала, когда телеграфный механизм остановится, чтобы прочитать сообщение целиком. «Европа». Прошло больше пяти лет с того дня, как журнал, который она любила читать в часы, свободные от работы прислугой в одной из богатейших лондонских семей, устроил конкурс кроссвордов. «Европа ник…» Каждый день она вспоминала, как удивило ее известие о победе в конкурсе и как она не решалась попросить недельный отпуск. «Европа никогда». Затем она попыталась восстановить в памяти путешествие с другими любителями логических задач, пока очертания Блетчли-парка не стали в ее памяти столь же ясными, как в тот осенний день, когда она впервые увидела его. «Европа никогда не будет».
Она боялась забыть малейшие подробности истории, которую собиралась рассказать всему миру, когда закончится война. Р-у-с-с-к-о-й. Последнее слово появилось с небольшим опозданием, но Бетти могла праздновать очередную победу союзных войск: ей удалось перехватить сообщение «Европа никогда не будет русской». Было 15 апреля 1945 года, и с этой фразой Адольф Гитлер обратился к высокопоставленным членам нацистской партии.
Они не единственными получили умоисступленное сообщение диктатора за две недели до его самоубийства: Гиммлер и не подозревал, что его переписку с Гитлером читало одновременно десять тысяч человек в маленьком поселке в восьмидесяти километрах от Лондона, надежно спрятанном, чтобы избежать бомбардировок. Именно там в 1939 году была создана правительственная школа кодов и шифров, которая занималась расшифровкой сообщений, кодируемых нацистами на машине «Энигма» — самой совершенной шифровальной машине того времени. «Энигму» в 1918 году начал производить инженер Артур Шербиус. Вначале он продавал машину частным лицам, однако потом ее потенциал оценили немецкая армия и флот, и «Энигма» начала широко использоваться военными, службой безопасности и разведкой. Когда войска вермахта вторглись в Польшу в начале сентября 1939 года, методы шифрования «Энигмы» достигли такой сложности, что возможность их взлома даже не рассматривалась.
И лишь совместная работа группы, состоявшей из математиков, физиков, переводчиков и уже упомянутых нами женщин — победительниц конкурса кроссвордов, помогла разгадать загадку дьявольской машины, которая посредством электрических импульсов и системы роторов преобразовывала одну и ту же букву, записанную два раза подряд, в разные символы. Одетые в костюмы пиратов, словно скучающая знать, ищущая развлечений в годы войны, первые дешифровщики в 1939 году разместились в бараках рядом с викторианским поместьем. Ни одна душа в соседнем поселке не должна была заподозрить, какую важную задачу решали обитатели Station X — так назывался центр в сообщениях союзников, отправляемых на передовую. Даже Уинстон Черчилль называл Блетчли-парк «курицей, несущей золотые яйца, которая никогда не кудахчет».
Справа — немецкие военные кодируют сообщения на машине «Энигма», один из экземпляров которой изображен на рисунке слева.
Вверху — зал Блетчли-парка, в котором происходила расшифровка кодов «Энигмы». Внизу — современная фотография поместья.