На самом деле оказывается, что метод Гёделя приложим даже к намного более слабым системам: критерий мощности, по которому все примитивно рекурсивные истины должны быть теоремами системы, оказывается слишком строгим. Это похоже на вора, который грабит только «достаточно богатых» людей — его жертва должна иметь в кармане по меньшей мере миллион долларов. К счастью, в случае ТТЧ, мы сможем стать такими грабителями, так как миллион у нее есть — иными словами, ТТЧ действительно содержит все примитивно рекурсивные истины в виде теорем.
Прежде чем углубиться в подробное обсуждение примитивно рекурсивных функций и предикатов, я постараюсь связать эту тему с темами предыдущих глав, чтобы дать читателю определенную перспективу.
Как обнаружить порядок с помощью правильного фильтра
Мы уже с самого начала столкнулись с тем, что формальные системы могут вести себя как неукротимые и опасные бестии, когда в них есть удлиняющие и укорачивающие правила, поскольку это может привести к бесконечному поиску среди строчек. Открытие Гёделевой нумерации показало, что у любого поиска строчки с определенным типографским свойством есть арифметический кузен: изоморфный поиск целого числа с соответствующим арифметическим свойством. Следовательно, чтобы найти разрешающий алгоритм для формальных систем, необходимо решить проблему непредсказуемо длинного поиска — хаоса — среди строчек. Возможно, что в «Арии с различными вариациями» я преувеличил хаос в задачах о целых числах. В действительности, математикам удалось укротить гораздо худшие случаи кажущегося хаоса, чем проблема «интересности»; в конце концов, все они оказались довольно милыми зверями. Нерушимая вера Ахилла в регулярность и предсказуемость чисел достойна немалого уважения по крайней мере потому, что она отражает взгляды, которых придерживались почти все математики до 1930-х годов. Чтобы показать, почему противопоставление порядка и хаоса такая деликатная и важная тема, и связать ее с вопросом о местоположении и извлечении значения, я хотел бы процитировать здесь замечательный и памятный отрывок из диалога «Реальны ли числа?» написанного в Галилеевом стиле покойным Ж. М. Джочем (J.M. Jauch. Are quanta real?):
САЛВИАТИ: Представьте, что я даю вам два ряда чисел, например:
7 8 5 3 9 8 1 6 3 3 9 7 4 4 8 3 0 9 6 1 5 6 6 0 8 4 …
и
1, -1/3, +1/5, -1/7, +1/9, -1/11, +1/13, -1/15, …
Если бы я спросил вас, СИМПЛИЦИО, какое следующее число в первом ряду, что бы вы сказали?
СИМПЛИЦИО: Я бы не мог ответить. На мой взгляд, это случайный набор чисел, и в нем нет никакого закона.
САЛИВИАТИ: А как насчет второго ряда?
СИМПЛИЦИО: Это проще простого. Следующим числом будет +1/17.
САЛВИАТИ: Верно. Но что бы вы сказали, узнав, что первый ряд также построен по закону, причем точно по такому же, какой вы только что открыли для второго ряда?
СИМПЛИЦИО: Это мне кажется маловероятным.
САЛВИАТИ: На самом деле, это так и есть, поскольку первый ряд — просто начало десятичной дроби суммы второго ряда. Она равняется π/4.
СИМПЛИЦИО: У вас в запасе всегда есть какой-нибудь математический трюк, но я не понимаю, какое отношение это имеет к абстракции и реальности.
САЛВИАТИ: Для абстракции это легко заметить. Первый ряд выглядит случайным, пока мы не разовьем с помощью абстрагирования несложный фильтр, позволяющий нам замечать простую закономерность за кажущейся хаотической абстракцией.
Именно таким образом были открыты законы природы. Явления природы предстают перед нами как хаотические, пока мы не выберем некие значительные события и абстрагируемся от мелких, незначительных обстоятельств, в которых они происходили, так что эти события становятся идеализированными. Только тогда они предстают во всем блеске своей регулярности.
САГРЕДО: Чудесная мысль! Выходит, что пытаясь понять природу, мы должны воспринимать события так, словно это сообщения, которые надо расшифровать. Каждое сообщение выглядит случайным, пока мы не найдем кода для его прочтения. Этот код принимает абстрактную форму, поскольку мы сознательно игнорируем некоторые неважные детали; таким образом, отчасти мы сами выбираем содержание сообщения. Эти неважные сигналы — что-то вроде «шумового фона», который ограничит аккуратность нашего прочтения.
Но поскольку код не абсолютен, в нашем сыром материале может содержаться несколько сообщений, так что перемена кода позволит нам прочесть как значительное сообщение то, что прежде было просто шумом. И наоборот: в новом коде прежнее сообщение может стать бессмысленным.
Таким образом, код предполагает свободный выбор между разными, дополняющими друг друга аспектами, каждый из которых с одинаковым правом может именоваться реальностью, если я позволю себе использовать это сомнительное слово.
О некоторых из этих аспектов мы, возможно, на сегодняшний день даже не подозреваем, но они могут стать явными для наблюдателя с иной системой абстракций.
Но скажите мне, Салвиати, как в таком случае можно утверждать, что мы что-то открыли в реальном мире? Не значит ли это, что мы просто создаем вещи в согласии с нашими внутренними образами, и что действительность находится только у нас в голове?
САЛВИАТИ: Я не думаю, что это так — тем менее, этот вопрос требует более глубокого размышления.[40]
Джоч говорит здесь о «сообщениях», посланных не разумными существами, но самой природой. Однако вопрос об отношении смысла и сообщения, на который мы пытались ответить в главе VI, может быть задан и здесь. Хаотична ли природа, или же в ней имеется некая закономерность? И какова роль интеллекта в поисках ответа на этот вопрос?
Теперь оставим в стороне философию и подумаем над вопросом регулярности рядов, выглядящих хаотическими. Может ли быть; что у функции Q(n) из главы V есть также и простое, нерекурсивное объяснение? Можно ли увидеть любую проблему, как фруктовый сад, с такого угла, что ее секрет становится явным? Или же в теории чисел есть проблемы, остающиеся загадкой, с какого бы угла мы их не рассматривали?
После этого вступления мне кажется, что настало время точно определить термин «предсказуемо длинный поиск». Для этого мы воспользуемся языком БЛУП.
Основные шаги в языке Блуп
Мы займемся здесь поисками натуральных чисел с различными свойствами. Чтобы мы могли говорить о длине поиска, нам необходимо определить некие основные шаги, из которых состоит каждый поиск. Тогда мы сможем измерять длину поиска количеством шагов. Вот некоторые шаги, которые можно считать основными:
сложение двух натуральных чисел;
умножение двух натуральных чисел;
определение равенства двух чисел;
определение того, какое из двух чисел больше.
Петли и верхние границы
Если мы попытаемся сформулировать некий тест, — например, на простоту чисел, — в терминах таких шагов, мы вскоре увидим, что нам необходимо включить в него управляющую структуру — описание того, в каком порядке надо действовать: когда надо отойти назад и попытаться сделать что-то снова, или пропустить несколько шагов, или остановиться и т. п.
Любой алгоритм — описание того, как выполнить определенное задание — обыкновенно состоит из смеси (1) набора конкретных операций и (2) контрольных высказываний. Таким образом, разрабатывая наш язык для описания предсказуемо длинных вычислений, мы должны включить в него также основные контрольные структуры. Отличительное свойство Блупа — это ограниченное количество его контрольных структур. В нем нельзя совершать произвольные шаги или повторять группы шагов до бесконечности. Практически единственная контрольная структура Блупа — это ограниченные петли: набор команд, которые можно повторять снова и снова, но лишь ограниченное число раз; это число называется верхней границей, или потолком петли. Если потолок данной петли 300, то она может быть выполнена 0,7 или 300 раз — но не 301.
Программист не должен вводить в программу точной величины всех верхних границ; в действительности, он может и не знать этого заранее. Вместо этого, каждый потолок может быть вычислен до того, как программа начинает выполнять соответствующую петлю. Например, если вы собираетесь вычислить величину 2 3 n, у вас будут две петли. Сначала вы подсчитаете 3 n; для этого вам придется применить умножение n раз. Затем вы возьмете полученное число и возведете два в эту степень. Таким образом, верхняя граница второй петли — результат вычислений, произведенных вами в первой петле.
В программе Блуп это выражается следующим образом:
ОПРЕДЕЛИТЬ ПРОЦЕДУРУ «ДВА-В-СТЕПЕНИ-ТРИ-В-СТЕПЕНИ»[N]:
