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

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

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

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

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

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

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

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

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

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

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

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

      ЯЧЕЙКА(О)