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ы принадлежать к оканчивающемуся типу, иначе бы от нее было мало пользы.
