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

БЛОК 1:НАЧАЛО

ЕСЛИ ВЫХОД + N = M, ТО:

ПРЕРВАТЬ ЦИКЛ 1;

ВЫХОД <= ВЫХОД + 1;

БЛОК 1:КОНЕЦ;

БЛОК 0:КОНЕЦ.

Здесь мы предполагаем, что ВЫХОД начинается с нуля. Если М меньше N, то вычитание становится невозможным, и мы сразу перескакиваем к БЛОКУ 0; в таком случае, ответ равняется 0. Именно это означает строчка ВЫЙТИ ИЗ БЛОКА 0. Но если М не меньше N, то мы пропускаем эту строчку и выполняем следующую команду (здесь это повторение цикла). Так работают в Блупе команды типа ЕСЛИ.

Итак, мы входим в ЦИКЛ 1, называющийся так потому, что он предлагает нам повторить БЛОК 1. Мы пробуем добавить к N сначала 0, затем 1, 2 и т. д., пока не находим числа, дающего в результате М. В этот момент мы ПРЕРЫВАЕМ цикл, в котором мы находимся, то есть переходим к команде, сразу следующей за КОНЦОМ этого цикла. В данном случае, мы попадаем к команде БЛОК 1: КОНЕЦ. Это последняя команда нашего алгоритма. ВЫХОД теперь содержит правильный ответ.

Заметьте, что у нас есть две различных команды, позволяющие нам перепрыгнуть вниз: ВЫЙТИ и ПРЕРВАТЬ. Первая относится к блокам, вторая — к циклам. ВЫЙТИ ИЗ БЛОКА н означает перейти к его последней строчке, в то время как ПРЕРВАТЬ ЦИКЛ н значит перепрыгнуть к строчке, сразу следующей за последней строчкой БЛОКА N. Это различие важно только тогда, когда вы находитесь внутри цикла и хотите его продолжить — но при этом хотите выйти из соответствующего блока; это исполняет команда ВЫЙТИ.

Заметьте также, что слова НЕ БОЛЬШЕ ЧЕМ теперь находятся перед верхней границей цикла; это говорит нам, что цикл может быть прерван до того, как достигнута его верхняя граница.

Остается объяснить две важные особенности Блупа. Первая из них состоит в том, что однажды определенная процедура может быть вызвана при определении следующих процедур. Она рассматривается в таком случае как нечто целое, как основной шаг . Эту черту Блупа можно назвать автоматическим созданием блоков. Это сравнимо с тем, как хороший фигурист выучивает новые движения: вместо длинной последовательности основных мускульных действий, он повторяет ранее выученные движения, которые, в свою очередь, состоят из ранее выученных движений — и так далее. Возможно, что нам придется отступить на несколько уровней, пока мы не придем к уровню «основных мускульных действий». Так же, как репертуар движений фигуриста, репертуар петель и прыжков Блупа растет очень быстро.

Другая важная черта Блупа — это то, что выходом некоторых процедур в нем может быть ДА или НЕТ вместо числового значения. Такие процедуры являются не функциями , но тестами . Чтобы указать на эту разницу, в конце названия теста ставится вопросительный знак. Кроме того, стандартным выбором ВЫХОДА здесь, разумеется, будет не 0, а НЕТ.

Давайте посмотрим, как работают эти черты Блупа в алгоритме, проверяющем, какие числа являются простыми.

ОПРЕДЕЛИТЬ ПРОЦЕДУРУ «ПРОСТОЕ?» [N]:

БЛОК 0:НАЧАЛО

ЕСЛИ N = О, ТО:

ВЫЙТИ ИЗ БЛОКА 0;

ЯЧЕЙКА(0) <= 2;

ПОВТОРИТЬ ЦИКЛ НЕ БОЛЕЕ ЧЕМ МИНУС [N,2] РАЗ:

БЛОК 1: НАЧАЛО

ЕСЛИ ОСТАТОК [N, ЯЧЕЙКА(0)] = 0, ТО;

ВЫЙТИ ИЗ БЛОКА 0;

ЯЧЕЙКА(0)<= ЯЧЕЙКА(0) +1;

БЛОК 1: КОНЕЦ;

ВЫХОД <= ДА;

БЛОК 0: КОНЕЦ.

Заметьте, что в этом алгоритме я вызвал две процедуры: МИНУС и ОСТАТОК. (Имеется в виду, что последняя была определена раньше; вы можете попробовать найти ее определение сами.) Этот тест на простоту чисел работает, перебирая один за другим потенциальные множители N, начиная с двух и кончая не более чем N-1. Если при делении N на любое из этих чисел остаток равняется нулю, то мы перескакиваем к концу алгоритма, поскольку на этой стадии ВЫХОД еще стандартный — НЕТ. Только если N не делится ни на одно из этих чисел, оно сможет пройти весь ЦИКЛ 1; тогда мы придем к команде ВЫХОД <= ДА, и после ее выполнения процедура будет закончена.

Мы только что видели, как определяются процедуры в Блупе; однако, определение процедуры — лишь часть программы. Программа состоит из цепи определений процедур , каждая из которых вызывает определенные ранее процедуры. За этим может следовать один или несколько вызовов определенных таким образом процедур. Таким образом, примером полной программы Блупа было бы определение процедуры ДВА В СТЕПЕНИ ТРИ В СТЕПЕНИ, с последующим вызовом

ДВА В СТЕПЕНИ ТРИ В СТЕПЕНИ [2].

результатом чего было бы 512.

Если у вас есть только цепь определений процедур, то ни одна из них не исполняется; для этого необходим некий вызов, вводящий специфические числовые величины. Только тогда процедуры начинают действовать. Это напоминает мясорубку, ждущую, чтобы в нее заложили порцию мяса — или, скорее, целую цепь мясорубок, связанных таким образом, что каждая из них получает сырье от предыдущих. Сравнение с мясорубками, возможно, не слишком аппетитно; однако в случае программ Блупа это понятие очень важно. Такие программы мы будем называть «программами без вызова». Пример подобной программы показан на рис. 72.

Блуп — язык для определения предсказуемо конечных вычислений. Стандартное название функций , которые можно просчитать на Блупе, — примитивно-рекурсивные функции ; стандартное название свойств, которые можно обнаружить с помощью тестов на Блупе, — примитивно-рекурсивные предикаты . Так, функция 2 3 n— примитивно-рекурсивная функция, а утверждение «n — простое число» — примитивно-рекурсивный предикат.

Интуиция подсказывает нам, что свойство Гольдбаха — примитивно-рекурсивное; чтобы сделать это яснее, я приведу определение процедуры Блупа, которая показывает, как можно проверить наличие или отсутствие этого свойства:

ОПРЕДЕЛИТЬ ПРОЦЕДУРУ «ГОЛЬДБАХ?» [N]:

БЛОК 0: НАЧАЛО

ЯЧЕЙКА(О) <= 2;

ПОВТОРИТЬ ЦИКЛ НЕ БОЛЬШЕ N РАЗ;

БЛОК 1: НАЧАЛО

ЕСЛИ {ПРОСТОЕ? [ЯЧЕЙКА(О)]

И ПРОСТОЕ? [МИНУС [N, ЯЧЕЙКА(0)]]},

ТОГДА:

БЛОК 2:НАЧАЛО

ВЫХОД 2: <= ДА;

ВЫЙТИ ИЗ БЛОКА 0;

БЛОК 2: КОНЕЦ

ЯЧЕЙКА(0) <= ЯЧЕЙКА(0) + 1;

БЛОК 1:КОНЕЦ;

БЛОК 0: КОНЕЦ.

Как обычно, мы предполагаем, что выходом будет НЕТ, если не доказано обратное, и мы просто ищем при помощи «грубой силы» такие пары чисел, которые в сумме дают N. Если они оба — простые числа, то мы выходим из внешнего блока; в противном случае, мы пробуем снова, пока не исчерпаем все возможности.

(Внимание: тот факт, что свойство Гольдбаха — примитивно-рекурсивное, не означает, что вопрос «все ли числа обладают свойством Гольдбаха» прост. Это далеко не так!)

Рис. 72. Структура программы без вызова в Блупе. Чтобы такая программа была самодостаточная, каждое определение процедуры может вызывать только те процедуры, определенные выше него.