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

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

Возьмем действительные числа между 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: КОНЕЦ

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