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