Текст книги "ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда"
Автор книги: Даглас Хофштадтер
Жанры:
Философия
,сообщить о нарушении
Текущая страница: 37 (всего у книги 64 страниц)
ХОРОШО СФОРМИРОВАННАЯ MIU? [N] = ДА, если N, в качестве строчки MIU, хорошо сформировано; в противном случае, НЕТ.
(например, ХОРОШО СФОРМИРОВАННАЯ MIU? [310] = ДА,
ХОРОШО СФОРМИРОВАННАЯ MIU? [415] = НЕТ)
ПАРА ДОКАЗАТЕЛЬСТВА MIU? [М, N] = ДА. если М, рассматриваемое как последовательность строчек MIU, является деривацией N, рассматриваемого как строчка системы MIU; в противном случае, НЕТ.
(например, ПАРА ДОКАЗАТЕЛЬСТВА MIU? [3131131111301, 301] = ДА,
ПАРА ДОКАЗАТЕЛЬСТВА MIU? [311130, 30] = НЕТ)
ТЕОРЕМА MIU? [N]= ДА, если N, в качестве строчки MIU, является теоремой; в противном случае, НЕТ.
(например, ТЕОРЕМА MIU? [311] = ДА,
ТЕОРЕМА MIU? [30]= НЕТ,
ТЕОРЕМА MIU? [701]= НЕТ)
ТЕОРЕМА ТТЧ? [N]= ДА, если N, в качестве строчки ТТЧ, является теоремой; в противном случае, НЕТ.
(например, ТЕОРЕМА ТТЧ? [666111666] = ДА,
ТЕОРЕМА ТТЧ?[123666111666] = НЕТ,
ТЕОРЕМА ТТЧ? [7014] = НЕТ)
ЛОЖНО? [N)= ДА, если N, в качестве строчки ТТЧ, представляет собой ложное утверждение теории чисел; в противном случае, НЕТ.
(например, ЛОЖНО? [666111666]= НЕТ,
ЛОЖНО? [223666111666]= ДА,
ЛОЖНО? [7014]= НЕТ)
Последние семь примеров особенно важны для наших будущих метаматематических исследований, поэтому они заслуживают самого пристального внимания.
Выразимость и представимость
Прежде, чем рассмотреть еще несколько интересных вопросов, касающихся Блупа, и перейти к его родственнику, Флупу, давайте вернемся к тому, зачем нам вообще понадобился Блуп, и к его связи с ТТЧ. Ранее я сказал, что критическая масса, необходимая формальной системе для приложения метода Гёделя, достигается тогда, когда в этой системе представимы все примитивно-рекурсивные понятия. Что это означает? Прежде всего, мы должны различать между понятиями представимости и выразимости. Выразить предикат означает просто перевести его с русского языка на язык формальной системы. Это не имеет ничего общего с теоремностью. С другой стороны, если предикат представлен, это означает, что
(1) Все истинные примеры этого предиката – теоремы;
(2) Все ложные примеры этого предиката – не теоремы.
Под «примером» я имею в виду строчку, которая получается при замене всех свободных переменных на числовые величины. Например, предикат m + n = k представлен в системе рr, поскольку каждый истинный пример этого предиката – теорема, и каждый ложный – не теорема. Таким образом, каждый частный случай сложения, истинный или ложный, переводится в разрешимую строчку системы рr. Однако система pr не способна выразить – и меньше того, представить – никакие другие свойства натуральных чисел. Она была бы слабеньким кандидатом в соревновании систем, способных символизировать теорию чисел.
ТТЧ, со своей стороны, способна выразить практически любой теоретико-численный предикат; например, легко написать строчку ТТЧ, выражающую предикат «b имеет свойство Черепахи». Таким образом, в смысле выразительной мощи ТТЧ – это именно то, что нам требуется.
Однако вопрос «Какие свойства представлены в ТТЧ?» эквивалентен вопросу «Насколько мощной аксиоматической системой является ТТЧ?» Можно ли сказать, что в ней представлены все возможные предикаты? Если это так, то ТТЧ может ответить на любой вопрос теории чисел – то есть она полна.
Примитивно-рекурсивные предикаты представлены в ТТЧ
Хотя вскоре выяснится, что ее полнота не более чем химера, ТТЧ полна, по крайней мере, в отношении примитивно-рекурсивных предикатов. Иными словами, любое высказывание теории чисел, чья истинность или ложность могут быть разрешены компьютером за некое предсказуемое время, разрешимо также в ТТЧ. Иными словами,
Если на Блупе можно написать тест для некого свойства натуральных чисел, то это свойство представлено в ТТЧ.
Есть ли функции, не являющиеся примитивно-рекурсивными?
Свойства чисел, которые можно обнаружить с помощью тестов Блупа, широко варьируются: это простота чисел, их совершенность, наличие у них свойства Гольдбаха, то, является ли число степенью двух и т. д. Логично было бы спросить, всякое ли свойство чисел может быть обнаружено соответствующей программой Блупа. Нас не должно смущать, что мы пока не можем проверить число на его интересность. Это может означать лишь то, что у нас не хватает знаний; возможно, если как следует поискать, нам удалось бы найти верхнюю границу соответствующего цикла. Тогда мы могли бы тут же написать тест Блупа. То же самое можно сказать и о свойстве Черепахи.
Следовательно, вопрос в том, можно ли найти потолок для любого цикла – или же теории натуральных чисел присуща некая беспорядочность, мешающая нам предсказать заранее длину некоторых вычислений? Удивительно то, что верно второе, и сейчас мы увидим, почему. Наверное, именно такой тип рассуждений свел с ума Пифагора, впервые доказавшего иррациональность корня из двух. В нашем доказательстве мы будем использовать знаменитый диагональный метод, изобретенный основателем теории множеств Георгом Кантором.
Клуб Б, номера-индексы и Белые Программы
Для начала представим себе забавное понятие: некий клуб, членами которого являются все возможные программы Блупа. Нет нужды говорить, что число членов этого клуба (назовем его клубом Б) бесконечно. Рассмотрим часть этого клуба, так сказать, подклуб, полученный после трех последовательных фильтрующих операций. Первый фильтр оставит нам только программы без вызова. Из этого подклуба мы уберем все тесты, оставив только функции. (Кстати, последняя процедура программ без вызова определяет, является ли программа тестом или функцией.) Третий фильтр удержит только функции с единственным входным параметром. Что у нас остается?
Полный набор всех безвызовных программ Блупа, вычисляющих функции с единственным входным параметром.
Назовем такие специальные функции Белыми Программами.
Следующим шагом будет установление для каждой Белой Программы определенного номера-индекса. Как это можно сделать? Легче всего составить список Белых Программ согласно их длине: самая короткая возможная программа будет #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] = 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);
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-цикла. Разумеется, множество программ Флупа будут заканчиваться для всех возможных величин вводного параметра. Например, как я уже говорил, большинство людей, изучавших свойство интересности, считают, что программы Флупа, подобные описанной выше, всегда будут заканчиваться – и, более того, всегда ответом ДА.
Оканчивающиеся и неоканчивающиеся программы Флупа
Было бы очень хорошо, если бы нам удалось разделить все процедуры Флупа на два класса: оканчивающиеся (терминаторы) и неоканчивающиеся (не-терминаторы). Первые всегда будут рано или поздно останавливаться, независимо от входных параметров и от наличия в нем MU-циклов. Вторые будут работать до бесконечности по крайней мере при одном из возможных выборов входного параметра. Если бы всегда можно было, внимательно рассмотрев данную программу Флупа, определить к какому типу она принадлежит, это привело бы к важным последствиям (как мы скоро увидим). Нет нужды говорить, что сама операция определения классов должна была 6ы принадлежать к оканчивающемуся типу, иначе бы от нее было мало пользы.
Трюки Тьюринга
Может быть, нам удастся заставить какую-нибудь из процедур самого Флупа заняться этой проверкой? Загвоздка здесь в том, что процедуры Флупа принимают в качестве вводных параметров только числа, а не программы. Однако это препятствие можно обойти … закодировав программы с помощью чисел! Этот ловкий трюк – не что иное, как Гёделева нумерация в одной из многих своих манифестаций. Каждый из 88 символов алфавита Флупа получит свой «кодон»: 901, 902, …988. Таким образом, каждая программа Флупа приобретает некий длинный Гёделев номер. Например, самая короткая функция Блупа (которая в то же время является оканчивающейся программой Флупа)
ОПРЕДЕЛИТЬ ПРОЦЕДУРУ «А» [В]:
БЛОК 0:НАЧАЛО
БЛОК 0: КОНЕЦ.
получит Гёделев номер, частично показанный ниже:
915,916,917,906,905,906,912,909,919,929,....... 911, 915,914,906,923,987
О П Р Е Д Е Л И Т Ь К О Н Е Ц .
Теперь нам нужен тест Блупа под названием ТЕРМИНАТОР?, который отвечал бы ДА, если входной параметр являлся бы кодом оканчивающейся программы Флупа, и НЕТ – в противном случае. Таким образом, если нам повезет, мы сможем заставить машину отличать терминаторы от не-терминаторов. Однако хитроумный аргумент, придуманный Аланом Тьюрингом, доказал, что никакая программа Блупа не сможет безошибочно находить это различие. Его идея весьма напоминает Гёделев метод и, таким образом, находится в близком родстве с диагональным методом Кантора. Не буду приводить ее здесь; достаточно сказать, что идея Тьюринга заключалась в том, чтобы ввести в программу ее собственный Гёделев номер. Это, однако, весьма непросто, все равно что ухитриться процитировать какое-то предложение внутри него самого. Для этого пришлось бы процитировать также и саму цитату… и так далее, и тому подобное. Очевидно, что это приводит к бесконечному регрессу. Однако Тьюринг придумал ловкий трюк, позволяющий скормить программе ее собственный Гёделев номер. В следующей главе я приведу решение этой проблемы в ином контексте. Однако сейчас мы пойдем к той же цели другой дорогой – а именно, постараемся доказать, что такой тест невозможен. Читатели, которые хотят ознакомиться с элегантной и простой версией метода Тьюринга, могут обратиться к статье Хоара и Аллисона (Hoar and Allison), упоминающейся в библиографии.
Программа-тест терминаторов была бы волшебной
Прежде, чем окончательно распроститься с этим понятием, давайте посмотрим, почему иметь такую программу было бы так замечательно. Такой тест был бы чем-то вроде волшебной палочки, которая могла бы одним взмахом разрешить все проблемы теории чисел. Предположим, мы захотели бы узнать, является ли Вариация Гольдбаха истинным предположением – иными словами, все ли числа обладают свойством Черепахи. Для начала мы написали бы тест на Флупе под названием ЧЕРЕПАХА?, который проверял бы, есть ли у вводного параметра данное свойство. Дефект этой программы – то, что она не кончается, если ввод не обладает свойством Черепахи – здесь превращается в достоинство, поскольку теперь мы можем проверить процедуру ЧЕРЕПАХА? на ее кончаемость. Если наш тест отвечает ДА, это значит, что ЧЕРЕПАХА? кончается для всех вводных параметров – иными словами, все числа обладают свойством Черепахи. Ответ НЕТ означал бы, что имеется некое число, обладающее свойством Ахилла. Ирония заключается в том, что мы никогда не используем саму программу ЧЕРЕПАХА? – мы только ее проверяем.
Идея решения любой проблемы теории чисел путем кодирования ее в программу и затем проверки этой программы на кончаемость сродни идее о проверке подлинности буддистского коана путем кодирования его в сложенную цепочку и затем проверяя на наличие буддистской природы уже эту цепочку. Может быть, Ахилл был прав, предполагая, что нужная информация может лежать ближе к поверхности в одном отображении, чем в другом.
Клуб Ф, числа-индексы и Зеленые Программы
Довольно мечтать – пора заняться делом! Как можно доказать, что тест на кончаемость в принципе невозможен? Для этого мы попытаемся применить диагональный аргумент к Флупу, так же, как мы это делали с Блупом. Мы увидим, что между этими двумя случаями есть небольшая, но решающая разница.
Так же, как в случае Блупа, вообразим клуб, членами которого являются все программы Флупа. Мы будем называть его «Клубом Ф». Теперь проведем с ним те же три фильтрующих операции, после чего мы получим:
Полный клуб всех безвызовных программ Флупа, которые вычисляют функции с одним вводным параметром.
Давайте назовем эти специальные программы Флупа Зелеными Программами (поскольку они могут идти, никогда не останавливаясь, словно машины на зеленый свет).
Теперь, точно так же как мы это сделали с Белыми Программами, дадим каждой Зеленой Программе индекс и организуем их в каталог, каждый том которого состоит из программ определенной длины, расположенных в алфавитном порядке.
До сих пор мы просто повторяли с Флупом то, что ранее проделали с Блупом. Посмотрим теперь, удастся ли нам скопировать последнюю часть – диагональный метод. Попробуем определить диагональную функцию:
Zeldiag [N] = 1 + Zelprogram {#N}[N]
Тут получается заминка: функция Zeldiag [N] может не иметь определенного значения выхода для всех значений входного параметра N. Это происходит потому, что при «фильтровании» мы не очистили Клуб Ф от всех неоканчивающихся программ – таким образом, у нас нет гарантии, что мы сможем вычислить Zeldiag [N] для всех значений N. Иногда мы можем ввести вычисления, которые никогда не окончатся. Диагональный аргумент в этом случае не годится, так как для его успешного приложения диагональная функция должна иметь значение для всех возможных входных параметров.
Проверка на кончаемость и Красные Программы
Чтобы поправить положение, мы могли бы использовать тест на кончаемость – если бы таковой существовал. Давайте предположим на минуту, что такой тест имеется, и используем его в качестве нашего четвертого фильтра. Идя по списку Зеленых Программ, мы начинаем отбрасывать одну за другой все не-терминаторы, так что в конце у нас остается:
Полный клуб всех безвызовных программ Флупа, которые вычисляют функции с одним входным параметром и которые оканчиваются для всех его значений.
Давайте назовем эти специальные программы Флупа Красными Программами (поскольку они всегда должны останавливаться, как машины на красный свет). Теперь мы можем применить диагональный аргумент. Определим:
Krasdiag [N] = 1 + Krasprogram {#N}[N]
Точно так же, как в случае с функцией Белдиаг, мы должны заключить, что Krasdiag [N] – хорошо определенная, вычисляемая функция одной переменной, которая не находится в списке Красных Программ и, следовательно, ее невозможно вычислить даже с помощью мощного языка Флуп. Не пора ли нам перейти к Глупу?
Глуп – …
Что же такое Глуп? если Флуп – это освобожденный от цепей Блуп, то Глуп должен, в свою очередь, быть освобожденным от цепей Флупом. Но как же можно снять цепи дважды? Как можно создать язык, более мощный, чем Флуп? Krasdiag [N] оказалась функцией, значение которой умеем вычислять только мы, люди, поскольку мы подробно описали всю процедуру на русском языке – однако эту функцию, по-видимому, невозможно запрограммировать на языке Флуп. Это – весьма серьезная проблема, поскольку никто пока не нашел компьютерного языка, более мощного, чем Флуп.
Мощность компьютерных языков в последнее время была объектом тщательных исследований. Нам самим не придется этим заниматься; упомянем только, что существует целый класс компьютерных программ с точно такой же выразительной мощностью, как Флуп, в том смысле, что любое вычисление, программируемое на одном языке, может быть запрограммировано на всех остальных языках. Интересно то, что почти любая попытка создать достойный внимания компьютерный язык приводит к созданию языка этого класса, то есть языка с выразительной мощностью Флупа. Приходится попотеть, чтобы создать достаточно интересный компьютерный язык слабее этих языков. Блуп, разумеется, пример более слабого языка, но это – скорее исключение, чем правило. Дело в том, что существует некий естественный путь создания алгоритмических языков, так что разные люди, работая независимо друг от друга, обычно создают эквивалентные языки, отличающиеся скорее стилем, чем степенью мощности.
