Даглас Хофштадтер - ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда

• Название: ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда
• Автор: Даглас Хофштадтер
• Издательство: Издательский Дом «Бахрах-М», 2001.
• Жанр: Математика
• Год: 2001
• ISBN: ISBN 5-94648-001-4

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

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

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

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

Переведенная на 17 языков, книга потрясла мировое интеллектуальное сообщество и сразу стала бестселлером. Теперь и русский читатель получил доступ к одной из культовых книг XX века.

---

Возьмем действительные числа между 0 и 1. Предположим, что возможно составить такой бесконечный список, в котором каждое положительное число N сопоставлено с действительным числом r(N) между 0 и 1, и где встречается каждое число между нулем и единицей. Поскольку действительные числа представлены бесконечными дробями, мы можем предположить, что начало списка выглядит так:

r(1): ,1  4  1  5  9  2  6  5  3  .  .  .  .  .  .  .

r(2): ,3  3  3  3  3  3  3  3  3  .  .  .  .  .  .  .

r(3): ,7  1  8  2  8  1  8  2  8  .  .  .  .  .  .  .

r(4): ,4  1  4  2  1  3  5  6  2  .  .  .  .  .  .  .

r(5): ,5  0  0  0  0  0  0  0  0  .  .  .  .  .  .  .

Цифры, идущие вниз по диагонали, выделены жирным шрифтом. Они будут использованы для получения того действительного числа d, которое находится между 0 и 1, но которое, как мы увидим, не состоит в списке. Чтобы получить d, вы берете диагональные цифры по порядку и меняете каждую из них на какую-либо иную цифру. После этого вы добавляете слева запятую, указывающую на десятичную дробь, и ваше число d готово! Разумеется, есть множество способов поменять одну цифру на другую и, соответственно, множество различных d. Предположим, например, что мы решили отнять от каждой диагональной цифры 1 (будем считать, что 0-1=9). Тогда нашим числом d будет:

,0 2 7 1 9 …

Мы построили его таким образом, что

первая цифра d отличается от первой цифры r (1);

вторая цифра d отличается от второй цифры  r (2);

третья цифра d отличается от третьей цифры r (3);

… и так далее.

Следовательно,

d отличается от r (1);

d отличается от r (2);

d отличается от r (3);

… и так далее.

Иными словами, d не находится в списке!

Что доказывает диагональный метод?

Основное различие между методом Кантора и нашим методом заключается в том, какое предположение мы решили изменить. В Канторовском методе этим предположением была сомнительная идея, что подобный список вообще возможен. Построение d доказало, что полную таблицу действительных чисел составить невозможно; иными словами, множество целых чисел не достаточно велико, чтобы пронумеровать множество всех действительных чисел. С другой стороны, в нашем доказательстве мы знаем, что список Белых Программ можно составить: множество целых чисел достаточно велико, чтобы пронумеровать множество всех Белых Программ. Поэтому нам приходится искать другую сомнительную идею. Ею оказывается предположение, что Beldiag [N] может быть закодировано как Белая Программа Блупа. Именно в этом — тонкое различие в приложении диагонального метода.

Это может стать понятнее, если мы применим тот же метод к «Списку Всех Великих Математиков» в Диалоге. Диагональ этого списка читается «Dboups». Заменив каждую букву на предыдущую букву латинского алфавита, мы получим «Cantor». Из этого возможны два заключения. Если вы твердо убеждены в том, что список полон, то вам приходится заключить, что Кантор — не Великий Математик, поскольку его имени нет в списке. С другой стороны, если вы убеждены в том, что Кантор — Великий Математик, то должны заключить, что Список Всех Великих Математиков неполон, поскольку этого имени там нет! (Горе тем несчастным, кто твердо убежден и в том, и в другом!) Первый случай соответствует нашему доказательству того, что Beldiag [N] — не примитивно-рекурсивная функция; второй — канторовскому доказательству того, что список действительных чисел неполон.

Канторовское доказательство использует диагональ в буквальном смысле слова. Другие «диагональные» доказательства основаны на более общем понятии, абстрагированном от геометрического смысла слова. В сердце диагонального метода лежит использование одного и того же целого числа двумя разными способами — можно сказать, что одно и то же число используется на двух разных уровнях — благодаря чему удается построить некий объект, не состоящий в определенном списке. Первый раз это число служит как вертикальный индекс, второй раз — как горизонтальный индекс. В Канторовском построении это хорошо видно. Что касается функции Beldiag [N], то там мы используем одно и то же число на двух различных уровнях: сначала как индекс Белой Программы и потом как входной параметр.

Рис. 73. Георг Кантор.

Коварная повторяемость диагонального метода

С первого взгляда, аргумент Кантора может показаться не очень-то убедительным. Нельзя ли его как-нибудь обойти? Может быть, если добавить к списку наше число d, то список окажется полным? Однако если подумать, то становится ясно, что это ничем не поможет, поскольку, как только это число займет свое место в списке, к последнему снова можно будет применить диагональный метод, результатом чего будет недостающее в новом списке число d'. Сколько бы раз вы не конструировали новые числа d и не добавляли их к списку в надежде его дополнить, вы все еще находитесь на крючке Канторовского метода. Вы даже можете попытаться построить такую таблицу действительных чисел, которая перехитрила бы диагональный метод, каким-то образом учитывая все его трюки вместе с самой повторяемостью. Это довольно интересное упражнение; однако, занявшись этим, вы очень скоро поймете, что, как бы вы не исхитрялись, вам не удастся сорваться с крючка Канторовского метода. Можно сказать, что любая так называемая «таблица всех действительных чисел» обязательно запутается в своих же сетях.

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

От Блупа к Флупу

Мы определили примитивно-рекурсивные функции и примитивно-рекурсивные свойства натуральных чисел с помощью программ, написанных на языке Блуп. Мы также показали, что Блуп не описывает всех функций натуральных чисел, которые можно выразить словами. Мы даже построили, пользуясь Канторовским методом, «не-Блупабельную» функцию Beldiag [N]. Что же именно в Блупе делает невозможным представить в нем функцию Beldiag [N]? Можно ли улучшить Блуп таким образом, что Beldiag [N] станет в нем представимой?

Определяющей чертой Блупа была ограниченность его циклов. Что, если мы опустим это требование и создадим второй язык, под названием Флуп? Флуп будет идентичен Блупу во всем, кроме одного: в нем можно будет иметь циклы как с потолком, так и без потолка (на самом деле, потолок здесь будет включаться в циклы исключительно для элегантности). Эти новые циклы будут называться MU-циклы, следуя обозначению, принятому в математической логике, где «свободный (неограниченный) поиск» обычно обозначается символом «μ — оператор». Таким образом, цикл в Флупе может выглядеть так:

MU-ЦИКЛ:

БЛОК n: НАЧАЛО

.

.

. 

БЛОК n: КОНЕЦ

Эта характеристика позволит нам написать на Флупе тесты для свойства Черепахи и свойства интересности — тесты, которые мы не могли создать на Блупе из-за того, что поиск там мог оказаться потенциально бесконечным. Интересующиеся читатели могут попробовать написать на Флупе следующий тест на интересности:

(1) Если вводной параметр N оказывается интересным числом, программа останавливается и выдает ответ ДА.

(2) Если N — неинтересное число, порождающее любой закрытый цикл, отличный от 1-4-2-1-4-2-1-…, программа останавливается и выдает ответ НЕТ.

(3) Если N — неинтересное число, порождающее «бесконечно возрастающую прогрессию», программа никогда не останавливается. Это «не-отвечание» и есть ответ Флупа. He-ответ Флупа странным образом напоминает не-ответ Джошу — «МУ».

Ирония (3) заключается в том, что ВЫХОД всегда принимает значение НЕТ, но при этом он недоступен, поскольку программа все еще работает. Неприятная третья альтернатива — это та цена, которую нам приходится платить за право писать свободные циклы. Незаконченность всегда будет теоретической альтернативой для всех программ Флупа, включающих вариант MU-цикла. Разумеется, множество программ Флупа будут заканчиваться для всех возможных величин вводного параметра. Например, как я уже говорил, большинство людей, изучавших свойство интересности, считают, что программы Флупа, подобные описанной выше, всегда будут заканчиваться — и, более того, всегда ответом ДА.