ДВА В СТЕПЕНИ ТРИ В СТЕПЕНИ [2].
результатом чего было бы 512.
Если у вас есть только цепь определений процедур, то ни одна из них не исполняется; для этого необходим некий вызов, вводящий специфические числовые величины. Только тогда процедуры начинают действовать. Это напоминает мясорубку, ждущую, чтобы в нее заложили порцию мяса — или, скорее, целую цепь мясорубок, связанных таким образом, что каждая из них получает сырье от предыдущих. Сравнение с мясорубками, возможно, не слишком аппетитно; однако в случае программ Блупа это понятие очень важно. Такие программы мы будем называть «программами без вызова». Пример подобной программы показан на рис. 72.
Блуп — язык для определения предсказуемо конечных вычислений. Стандартное название функций, которые можно просчитать на Блупе, — примитивно-рекурсивные функции; стандартное название свойств, которые можно обнаружить с помощью тестов на Блупе, — примитивно-рекурсивные предикаты. Так, функция 23n — примитивно-рекурсивная функция, а утверждение «n — простое число» — примитивно-рекурсивный предикат.
Интуиция подсказывает нам, что свойство Гольдбаха — примитивно-рекурсивное; чтобы сделать это яснее, я приведу определение процедуры Блупа, которая показывает, как можно проверить наличие или отсутствие этого свойства:
ОПРЕДЕЛИТЬ ПРОЦЕДУРУ «ГОЛЬДБАХ?» [N]:
БЛОК 0: НАЧАЛО
ЯЧЕЙКА(О) <= 2;
ПОВТОРИТЬ ЦИКЛ НЕ БОЛЬШЕ N РАЗ;
БЛОК 1: НАЧАЛО
ЕСЛИ {ПРОСТОЕ? [ЯЧЕЙКА(О)]
И ПРОСТОЕ? [МИНУС [N, ЯЧЕЙКА(0)]]},
ТОГДА:
БЛОК 2:НАЧАЛО
ВЫХОД 2: <= ДА;
ВЫЙТИ ИЗ БЛОКА 0;
БЛОК 2: КОНЕЦ
ЯЧЕЙКА(0) <= ЯЧЕЙКА(0) + 1;
БЛОК 1:КОНЕЦ;
БЛОК 0: КОНЕЦ.
Как обычно, мы предполагаем, что выходом будет НЕТ, если не доказано обратное, и мы просто ищем при помощи «грубой силы» такие пары чисел, которые в сумме дают N. Если они оба — простые числа, то мы выходим из внешнего блока; в противном случае, мы пробуем снова, пока не исчерпаем все возможности.
(Внимание: тот факт, что свойство Гольдбаха — примитивно-рекурсивное, не означает, что вопрос «все ли числа обладают свойством Гольдбаха» прост. Это далеко не так!)
Рис. 72. Структура программы без вызова в Блупе. Чтобы такая программа была самодостаточная, каждое определение процедуры может вызывать только те процедуры, определенные выше него.
Предлагаемые упражнения
Сможете ли вы написать похожую процедуру Блупа, которая проверяла бы наличие у числа свойства Черепахи (или Ахилла)? Попытайтесь! Если вам это не удается, то только лишь потому, что вы не знаете, какой будет верхняя граница? Возможно ли, что существует какое-то фундаментальное препятствие, вообще не позволяющее формулировать подобные алгоритмы в Блупе? А что, если задать те же вопросы касательно свойства интересности, определенного в Диалоге?
Ниже я привожу некоторые функции и свойства; попробуйте определить для каждого из них, является ли оно примитивно-рекурсивным (то есть, программируемым на Блупе). Для этого вы должны будете хорошенько подумать, какой тип операций потребуется для соответствующих вычислений и можно ли определить потолок для всех циклов данной процедуры.
ФАКТОРИАЛ [N] = N! (ФАКТОРИАЛ ОТ N)
(например, ФАКТОРИАЛ [4] = 24)
ОСТАТОК [M.N] = остаток после деления М на N
(например, ОСТАТОК [24,7] = 3)
ЦИФРА π [N] = N-ная цифра π после запятой
(например, ЦИФРА π [1] = 1,
ЦИФРА π [2] = 4,
ЦИФРА π [1 000 000] = 1)
ФИБО[М] = N-ное число ряда Фибоначчи
(например, ФИБО [9] = 34)
ПРОСТОЕ ЧИСЛО ЗА [N] = наименьшее простое число, следующее за N
(например, ПРОСТОЕ ЧИСЛО ЗА [33] = 37)
СОВЕРШЕННОЕ [N] = N-ное «совершенное» число, такое как, например, 28, чьи множители в сумме дают само это число: 28 =1+2+4+7+14
(например, СОВЕРШЕННОЕ [2] = 28)
ПРОСТОЕ? [N] = ДА если N простое число, в противном случае, НЕТ.
СОВЕРШЕННОЕ [N]? = ДА если N совершенное число, в противном случае, НЕТ.
ОБЫКНОВЕННОЕ? [А, В, С, N] = ДА, если A N+ В N= С N верно; в противном случае, НЕТ.
(например, ОБЫКНОВЕННОЕ ? [3, 4, 5, 2] = ДА,
ОБЫКНОВЕННОЕ ? [3, 4, 5, 3] = НЕТ)
ПЬЕР? [А,В,С] = ДА, если A N+ В N= С N верно для N > 1; в противном случае, НЕТ.
(например, ПЬЕР? [3, 4, 5] = ДА,
ПЬЕР? [1,2,3] = НЕТ)
ФЕРМА? [N] == ДА, если А N + В N = С N верно для неких положительных величин А, В, и С; в противном случае, НЕТ.
(например, ФЕРМА? [2] = ДА)
ЧЕРЕПАШЬЯ ПАРА? [M, N] = ДА если M и M + N простые числа; в противном случае, НЕТ.
(например, ЧЕРЕПАШЬЯ ПАРА? [5, 1742] = ДА
ЧЕРЕПАШЬЯ ПАРА? [5, 100] = НЕТ)
ЧЕРЕПАХА [N] = ДА, если N - разность двух простых чисел, в противном случае, НЕТ.
(например, ЧЕРЕПАХА [1742] = ДА,
ЧЕРЕПАХА [7] = НЕТ)
ХОРОШО СФОРМИРОВАННАЯ 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 имеет свойство Черепахи». Таким образом, в смысле выразительной мощи ТТЧ — это именно то, что нам требуется.
Однако вопрос «Какие свойства представлены в ТТЧ?» эквивалентен вопросу «Насколько мощной аксиоматической системой является ТТЧ?» Можно ли сказать, что в ней представлены все возможные предикаты? Если это так, то ТТЧ может ответить на любой вопрос теории чисел — то есть она полна.
