Даглас Хофштадтер - ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда

ДВА В СТЕПЕНИ ТРИ В СТЕПЕНИ [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 имеет свойство Черепахи». Таким образом, в смысле выразительной мощи ТТЧ — это именно то, что нам требуется.

Однако вопрос «Какие свойства представлены в ТТЧ?» эквивалентен вопросу «Насколько мощной аксиоматической системой является ТТЧ?» Можно ли сказать, что в ней представлены все возможные предикаты? Если это так, то ТТЧ может ответить на любой вопрос теории чисел — то есть она полна.