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

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

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

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

Назовем такие специальные функции Белыми Программами .

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

А Б В Г Д Е Ж З И Й К Л М Н О П

Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Э Ь Ю Я

A B C D E F G H I J K L M N

O P Q R S T U V W X Y Z + Х

1 0 2 3 4 5 6 7 8 9 <= = < >

( ) [ ] { } - ' ? : ; , .

В конце находится скромный интервал, пустое место! Всего 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] = N 3

Давайте теперь применим обещанный трюк — Канторов диагональный метод. Возьмем каталог всех Белых Программ и используем его для определения новой функции с одной переменной — 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]. Перед нами — бесконечный заговор, родственный идее Черепахи о «бесконечных совпадениях», а также ω-неполноте. Здесь, однако, мы не будем подробно останавливаться на этих отношениях.

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