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

Теперь оставим в стороне философию и подумаем над вопросом регулярности рядов, выглядящих хаотическими. Может ли быть; что у функции Q( n ) из главы V есть также и простое, нерекурсивное объяснение? Можно ли увидеть любую проблему, как фруктовый сад, с такого угла, что ее секрет становится явным? Или же в теории чисел есть проблемы, остающиеся загадкой, с какого бы угла мы их не рассматривали?

После этого вступления мне кажется, что настало время точно определить термин «предсказуемо длинный поиск». Для этого мы воспользуемся языком БЛУП.

Мы займемся здесь поисками натуральных чисел с различными свойствами. Чтобы мы могли говорить о длине поиска, нам необходимо определить некие основные шаги , из которых состоит каждый поиск. Тогда мы сможем измерять длину поиска количеством шагов. Вот некоторые шаги, которые можно считать основными:

сложение двух натуральных чисел;

умножение двух натуральных чисел;

определение равенства двух чисел;

определение того, какое из двух чисел больше.

Если мы попытаемся сформулировать некий тест, — например, на простоту чисел, — в терминах таких шагов, мы вскоре увидим, что нам необходимо включить в него управляющую структуру — описание того, в каком порядке надо действовать: когда надо отойти назад и попытаться сделать что-то снова, или пропустить несколько шагов, или остановиться и т. п.

Любой алгоритм — описание того, как выполнить определенное задание — обыкновенно состоит из смеси (1) набора конкретных операций и (2) контрольных высказываний. Таким образом, разрабатывая наш язык для описания предсказуемо длинных вычислений, мы должны включить в него также основные контрольные структуры. Отличительное свойство Блупа — это ограниченное количество его контрольных структур. В нем нельзя совершать произвольные шаги или повторять группы шагов до бесконечности. Практически единственная контрольная структура Блупа — это ограниченные петли : набор команд, которые можно повторять снова и снова, но лишь ограниченное число раз; это число называется верхней границей , или потолком петли. Если потолок данной петли 300, то она может быть выполнена 0,7 или 300 раз — но не 301.

Программист не должен вводить в программу точной величины всех верхних границ; в действительности, он может и не знать этого заранее. Вместо этого, каждый потолок может быть вычислен до того , как программа начинает выполнять соответствующую петлю. Например, если вы собираетесь вычислить величину 2 3 n, у вас будут две петли. Сначала вы подсчитаете 3 n ; для этого вам придется применить умножение n раз. Затем вы возьмете полученное число и возведете два в эту степень. Таким образом, верхняя граница второй петли — результат вычислений, произведенных вами в первой петле.

В программе Блуп это выражается следующим образом:

ОПРЕДЕЛИТЬ ПРОЦЕДУРУ «ДВА-В-СТЕПЕНИ-ТРИ-В-СТЕПЕНИ»[N]:

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

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

ЦИКЛ N РАЗ;

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

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

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

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

ЦИКЛ ЯЧЕЙКА(О) РАЗ:

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

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

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

ВЫХОД <= ЯЧЕЙКА(1);

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

Умение читать программу, написанную на компьютерном языке, и понимать, что она делает, приходит со временем. Но надеюсь, что этот алгоритм достаточно прост, чтобы его можно было понять без особого труда. В нем определяется процедура , имеющая одно входное значение — N; выходом этой процедуры будет искомая величина.

Данное определение процедуры имеет блочную структуру ; это означает, что некоторые его порции должны рассматриваться как единицы, или блоки . Все действия в блоке выполняются как одно целое. Каждый блок пронумерован (внешний блок получает номер 0) и ограничен НАЧАЛОМ и КОНЦОМ. В нашем примере в БЛОКЕ 1 и БЛОКЕ 2 было всего по одной инструкции, но вскоре мы будем иметь дело с более длинными блоками. Инструкция ЦИКЛ означает, что нужно повторить несколько раз блок, следующий ниже. Как вы видели выше, блоки могут быть вставлены один в другой.

Стратегия этого алгоритма ничем не отличается от той, которую я описал выше. Сначала вы берете вспомогательную переменную под названием ЯЧЕЙКА(0); для начала, вы придаете ей значение 1 и затем, исполняя цикл, вы несколько умножаете ее на 3 и повторяете это ровно N раз. Потом вы повторяете ту же процедуру для ЯЧЕЙКИ(1): придаете ей значение 1 и умножаете на 2 ровно ЯЧЕЙКА(0) раз; после этого вы останавливаетесь. Наконец, вы придаете выходу значение, полученное вами для ЯЧЕЙКИ(1). Именно эта величина достигает внешнего мира — это единственное действие процедуры, заметное извне.

Необходимо отметить кое-что относительно нотации. Прежде всего, значение указывающей налево стрелки следующее:

Вычислить выражение справа, взять результат и придать это значение ЯЧЕЙКЕ (или ВЫХОДУ) слева.

Таким образом, команда ЯЧЕЙКА(1) <= 3 * ЯЧЕЙКА(1) означает что вы должны утроить величину ЯЧЕЙКИ(1). Каждую ЯЧЕЙКУ можно представить как отдельное слово в памяти компьютера. Единственная разница между ЯЧЕЙКОЙ и настоящим словом заключается в том, что последнее может содержать только целые числа до определенного конечного предела, в то время как в ЯЧЕЙКЕ может храниться сколь угодно большое натуральное число.

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

Давайте теперь посмотрим на другую процедуру, которая покажет нам некоторые черты Блупа, делающие эту программу более общей. Каким образом можно найти значение M-N, если мы умеем только складывать? Трюк состоит в том, чтобы прибавлять различные числа к N до тех пор, пока мы не получим таким образом М. Но что, если М меньше N? Что, если нам нужно отнять 5 от 2? В области натуральных чисел ответа на этот вопрос нет. Но мы хотим, чтобы наша процедура Блуп все равно дала бы нам ответ — скажем, 0. Вот процедура Блупа, которая выполняет вычитание:

ОПРЕДЕЛИТЬ ПРОЦЕДУРУ «ВЫЧИТАНИЕ»[M,N]:

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

ЕСЛИ M < N, ТО;

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

ПОВТОРИТЬ ЦИКЛ НЕ БОЛЬШЕ ЧЕМ M + 1 РАЗ;