Хотя вскоре выяснится, что ее полнота не более чем химера, ТТЧ полна, по крайней мере, в отношении примитивно-рекурсивных предикатов. Иными словами, любое высказывание теории чисел, чья истинность или ложность могут быть разрешены компьютером за некое предсказуемое время, разрешимо также в ТТЧ. Иными словами,
Если на Блупе можно написать тест для некого свойства натуральных чисел, то это свойство представлено в ТТЧ.
Есть ли функции, не являющиеся примитивно-рекурсивными?
Свойства чисел, которые можно обнаружить с помощью тестов Блупа, широко варьируются: это простота чисел, их совершенность, наличие у них свойства Гольдбаха, то, является ли число степенью двух и т. д. Логично было бы спросить, всякое ли свойство чисел может быть обнаружено соответствующей программой Блупа. Нас не должно смущать, что мы пока не можем проверить число на его интересность. Это может означать лишь то, что у нас не хватает знаний; возможно, если как следует поискать, нам удалось бы найти верхнюю границу соответствующего цикла. Тогда мы могли бы тут же написать тест Блупа. То же самое можно сказать и о свойстве Черепахи.
Следовательно, вопрос в том, можно ли найти потолок для любого цикла — или же теории натуральных чисел присуща некая беспорядочность, мешающая нам предсказать заранее длину некоторых вычислений? Удивительно то, что верно второе, и сейчас мы увидим, почему. Наверное, именно такой тип рассуждений свел с ума Пифагора, впервые доказавшего иррациональность корня из двух. В нашем доказательстве мы будем использовать знаменитый диагональный метод, изобретенный основателем теории множеств Георгом Кантором.
Клуб Б, номера-индексы и Белые Программы
Для начала представим себе забавное понятие: некий клуб, членами которого являются все возможные программы Блупа. Нет нужды говорить, что число членов этого клуба (назовем его клубом Б) бесконечно. Рассмотрим часть этого клуба, так сказать, подклуб, полученный после трех последовательных фильтрующих операций. Первый фильтр оставит нам только программы без вызова. Из этого подклуба мы уберем все тесты, оставив только функции. (Кстати, последняя процедура программ без вызова определяет, является ли программа тестом или функцией.) Третий фильтр удержит только функции с единственным входным параметром. Что у нас остается?
Полный набор всех безвызовных программ Блупа, вычисляющих функции с единственным входным параметром.
Назовем такие специальные функции Белыми Программами.
Следующим шагом будет установление для каждой Белой Программы определенного номера-индекса. Как это можно сделать? Легче всего составить список Белых Программ согласно их длине: самая короткая возможная программа будет #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]. Перед нами — бесконечный заговор, родственный идее Черепахи о «бесконечных совпадениях», а также ω-неполноте. Здесь, однако, мы не будем подробно останавливаться на этих отношениях.
Первоначальный диагональный аргумент Кантора
Почему этот прием называется диагональным аргументом? Этот термин восходит к первоначальному диагональному аргументу Кантора, на котором впоследствии были основаны многие другие доводы (в том числе наш). Объяснение первоначального аргумента Кантора немного отвлечет нас от нашей темы, но все же это стоит сделать. Кантор тоже хотел показать, что некий предмет не состоит в определенном списке. Конкретнее, он хотел доказать, что если бы был создан список действительных чисел, то некоторые действительные числа неизбежно очутились бы вне этого списка; таким образом, понятие полного списка действительных чисел уже само по себе противоречиво.
Необходимо иметь в виду, что это верно не только для конечных, но и для бесконечных списков. Это гораздо более важный результат, чем утверждение типа: «Количество действительных чисел бесконечно, следовательно, оно не может содержаться ни в каком конечном списке.» Основная мысль Канторова результата заключается в том, что существуют два типа бесконечности: одна из них описывает, сколько отдельных записей может быть в бесконечном списке, в то время как другая — сколько существует действительных чисел (или сколько есть точек на линии или ее отрезке). Вторая бесконечность «больше», в том смысле, что действительные числа невозможно уместить в таблице, длина которой описана с помощью первой бесконечности. Посмотрим теперь, как аргумент Кантора использует диагональ в буквальном смысле.
