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

133

В конце находится скромный интервал, пустое место! Всего 88 символов. Для удобства, мы можем поместить все Белые Программы длины 1 в том 1, программы их двух символов — в том 2 и т. д. Ясно, что первые несколько томов будут совершенно пустыми, в то время как все последующие тома будут заполнены (каждый том будет содержать конечное количество записей). Самой короткой Белой Программой будет следующая:

ОПРЕДЕЛИТЬ ПРОЦЕДУРУ «А» [В]:

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

БЛОК 0: КОНЕЦ.

Эта глупенькая мясорубка выдает 0, что бы в нее ни засунули. Эта программа находится в томе 59, поскольку в ней 59 символов (считаются все необходимые интервалы, включая те, что разделяют строчки).

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

Давайте определим функцию, вызываемую k-нон Белой Программой следующим образом:

Belprogram {#k}[N]

Здесь k — индекс программы, и N — единственный параметр входа. Например, Белая Программа #12 может выдать результат, вдвое больший ее входа:

Belprogram {#12}[N] = 2 * N

Смысл вышеприведенного уравнения в том, что программа, приведенная слева, выдает такую же величину, которую получил бы человек, пользуясь обыкновенным алгебраическим выражением справа. Еще один пример: Белая Программа # 5000 может сосчитать куб числа на основании входного параметра:

Belprogram {#5000}[N] = N3

Диагональный метод

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

Уравнение (1) … Beldiag [N]: = 1 + Belprogram {#N}[N]

Стратегия здесь следующая: в каждую «мясорубку» закладывается ее собственный индекс, и к результату прибавляется 1. Для примера, давайте найдем Beldiag [12]. Мы знаем, что Belprogram [N] — это функция 2N; следовательно, Beldiag [12] должна иметь значение 1 + 2 * 12, то есть 25. Так же, Beldiag [5000] имела бы значение 125 000 000 001, поскольку она на единицу больше куба 5000. Подобным образом можно найти Beldiag любого аргумента.

Интересно то, что сама Beldiag [N] не представлена в каталоге Белых Программ. Она просто не может там быть — и вот почему: чтобы быть одной из Белых Программ, каждая программа должна иметь индекс. Возьмем, к примеру, Белую Программу #X. Этот факт выражается следующим уравнением:

Уравнение (2) … Beldiag [N]: = Belprogram {#X}[N]

Однако между уравнениями (1) и (2) есть противоречие, которое становится явным, когда мы пытаемся вычислить величину Beldiag [X]. Для этого мы должны заменить N на X в обоих уравнениях. В случае уравнения (1) мы получим:

Beldiag [X] = 1 + Belprogram {#X}[X]

С другой стороны, произведя замену в уравнении (2), мы получаем:

Beldiag [X] = Belprogram {#X}[X]

Но Beldiag [N] не может быть равен одновременно и числу, и его последователю, как утверждают эти два уравнения. Нам придется вернутся назад и избавиться от допущения, на котором основано это противоречие. Единственным кандидатом оказывается уравнение (2), утверждающее, что Beldiag [N] может быть закодировано как Белая Программа Блупа. И это доказывает, что Beldiag не является примитивно-рекурсивной функцией. Таким образом, нам удалось достигнуть своей цели и разрушить милое, но наивное убеждение Ахилла о том, что любая теоретико-числовая функция может быть вычислена за предсказуемое количество шагов.

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

Первоначальный диагональный аргумент Кантора

Почему этот прием называется диагональным аргументом? Этот термин восходит к первоначальному диагональному аргументу Кантора, на котором впоследствии были основаны многие другие доводы (в том числе наш). Объяснение первоначального аргумента Кантора немного отвлечет нас от нашей темы, но все же это стоит сделать. Кантор тоже хотел показать, что некий предмет не состоит в определенном списке. Конкретнее, он хотел доказать, что если бы был создан список действительных чисел, то некоторые действительные числа неизбежно очутились бы вне этого списка; таким образом, понятие полного списка действительных чисел уже само по себе противоречиво.

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

Возьмем действительные числа между 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  .  .  .  .  .  .  .

Цифры, идущие вниз по диагонали, выделены жирным шрифтом. Они будут использованы для получения того действительного числа 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);