Текст книги "ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда"
Автор книги: Даглас Хофштадтер
Жанры:
Философия
,сообщить о нарушении
Текущая страница: 36 (всего у книги 64 страниц)
Черепаха: Прекрасно; но что означает «достаточно тщательный»?
Ахилл: Это значит, что читатель должен будет искать в тексте некую крохотную, но важную деталь, которая укажет на действительный конец. И ему придется исхитриться, чтобы среди множества подобных деталей найти настоящую.
Черепаха: Что-то вроде изменения частоты букв или длины слов? Внезапная россыпь грамматических ошибок?
Ахилл: Совершенно верно. Какое-то шифрованное послание, которое поможет внимательному читателю найти конец книги. Еще можно вывести новых персонажей или придумать события, несоответствующие остальной истории. Наивный читатель проглотит это, не задумываясь, в то время как умудренный опытом человек сможет точно указать, где проходит граница.
Черепаха: Какая оригинальная идея, Ахилл. Я расскажу о ней другу и, может быть, он захочет вставить ее в свой Диалог.
Ахилл: Этим он окажет мне честь.
Черепаха: Знаете, боюсь, что я совсем засыпаю, Ахилл. Пойду-ка, пожалуй, пока я еще в силах добраться до дому.
Ахилл: Мне было очень приятно, что вы просидели у меня так долго в такой поздний час только лишь с тем, чтобы составить мне компанию. Уверяю вас, что ваши теоретико-численные рассказы явились прекрасным противоядием против моего обычного верчения в постели. Кто знает, может быть, мне даже удастся сегодня заснуть. В знак благодарности позвольте преподнести вам подарок.
Черепаха: Ах, Ахилл, что за глупости…
Ахилл: Для меня это одно удовольствие, г-жа Ч. Подойдите-ка к комоду; на нем лежит маленькая старинная шкатулка.
(Черепаха подходит к комоду.)
Черепаха: Неужели вы имеете в виду эту золотую шкатулку?
Ахилл: Ее самую. Пожалуйста, примите ее в знак нашей дружбы.
Черепаха: Премного вам благодарна, Ахилл. Гмм… Что это за имена математиков на крышке, да еще по-английски? Что за интересный список…
D e M o r g a n
A b e l
B o o l e
В r о u w e r
S i e r p i n s k i
W e i e r s t r a s s
Ахилл: По идее, это должно быть Полным Списком Всех Великих Математиков. Только я никогда не мог понять, почему буквы, идущие вниз по диагонали, написаны жирным шрифтом.
Черепаха: Смотрите, тут внизу написано: «Отнимите 1 от диагонали, и вы найдете Баха в Лейпциге».
Ахилл: Я это тоже видел, но не могу сообразить, что бы это значило. Так я не запутывался с тех пор, когда пытался заниматься философией. Особенно меня тогда смутил Кант – оригинально, но уж больно туманно…
Черепаха: Прошу вас, ни слова о философии – я слишком устала. Лучше поползу-ка я домой. (Машинально открывает шкатулку.) Ах! Глядите, здесь внутри куча золотых монет! Да это же луидоры!
Ахилл: Вы доставите мне огромное удовольствие, приняв эти деньги, г-жа Ч.
Черепаха: Но… Но…
Ахилл: Пожалуйста, без возражений. Шкатулка и золото – ваши. И спасибо вам за несравненный вечер.
Черепаха: Как мило с вашей стороны. Надеюсь, вам удастся заснуть: выпейте стаканчик теплого молока, поставьте на патефон вашу любимую пластинку, и пусть вам приснится эта странная Гипотеза Гольдбаха и ее Вариации… Спокойной вам ночи. (Она берет золотую шкатулку, полную луидоров, и направляется к двери. В этот момент раздается громкий стук.) Кто бы это мог быть в такой поздний час, Ахилл?
Ахилл: Понятия не имею. Все это весьма подозрительно… Знаете что, спрячьтесь-ка на всякий случай за комодом!
Черепаха: Отличная мысль. (Заползает за комод.)
Ахилл: Кто там?
Голос: Откройте, полиция!
Ахилл: Входите, дверь не заперта!
(Входят два дюжих полицейских в новеньких, с иголочки, формах, со сверкающими кокардами на фуражках.)
Полицейский: Я – лейтенант Сильвер, а это – копертан Гулд. Проживает ли здесь некто по имени Ахилл?
Ахилл: Это я.
Полицейский: Мистер Ахилл, у нас есть все основания подозревать, что в вашей квартире находится золотая шкатулка с сотней луидоров. Она была украдена сегодня вечером из музея.
Ахилл: Ах, батюшки!
Полицейский: Она должна находиться здесь, потому что, кроме вас, подозревать некого. Придется вам пройти с нами… (Достает ордер на арест.)
Ахилл: Господи, как я счастлив, что вы наконец пришли! Весь вечер я мучился, слушая Черепашьи вариации на тему золотых шкатулок. Надеюсь, вы меня освободите! Прошу вас, господа, загляните за комод, и вы увидите там настоящего преступника!
(Полицейские заглядывают за комод; там, среди пыли и паутины, они видят дрожащую Черепаху с золотой шкатулкой в лапах.)
Полицейский: Ага! Вот она, злодейка! Никогда бы на нее не подумал – но поскольку она поймана с поличным…
Ахилл: Уведите поскорее отсюда эту преступницу, любезные господа. Слава Богу, мне уже никогда не придется слышать ни о ней, ни о ее Золотых Вариациях.
ГЛАВА XIII: Блуп, Флуп и Глуп
Самосознание и хаос
Блуп, Флуп и Глуп – это не имена гномов, не разговоры лягушек в пруду и не бульканье воды в засорившейся раковине. Это компьютерные языки, каждый из которых имеет особое предназначение. Они были придуманы специально для этой главы. Мы воспользуемся ими для того, чтобы объяснить новые значения слова «рекурсивный» – в частности, понятия примитивной рекурсивности и общей рекурсивности. Эти понятия помогут нам лучше объяснить механизм автореферентности в ТТЧ.
Здесь мы совершаем скачок от человеческого мозга и интеллекта к миру математики, техники и компьютеров. Этот переход, каким бы резким он не казался, все же имеет смысл. Мы только что убедились в том, что в сердце интеллекта лежит самосознание. Давайте теперь рассмотрим «самосознание» в более формальных контекстах, таких, как ТТЧ. Между ТТЧ и разумом – огромная дистанция; тем не менее, некоторые идеи окажутся весьма поучительными и, может быть, даже приложимыми к нашим рассуждениям о сознании.
Удивительно то, что самосознание в ТТЧ тесно связано с вопросом о порядке и хаосе среди натуральных чисел. В частности, мы увидим, что упорядоченная система, достаточно сложная, чтобы отразить саму себя, не может быть полностью упорядоченной – в ней обязательно окажутся некие странные, хаотические черты. Читателям, в которых есть что-то от Ахилла, трудно будет в это поверить. Однако здесь существует и некая «магическая» компенсация, что-то вроде порядка внутри хаоса; этот «хаотический порядок» изучается так называемой «теорией о рекурсивных функциях». К несчастью, здесь мы сможем дать только самое поверхностное понятие об этой интереснейшей теме.
Представимость и холодильники
Мы с вами уже довольно часто натыкались на такие выражения, как «достаточно сложный», «достаточно мощный» и тому подобное. Что именно они означают? Давайте вернемся к «войне» Краба с Черепахой и подумаем, какие качества необходимы предмету, чтобы его можно было бы назвать патефоном? Почему бы Крабу не сказать, что его холодильник – это «совершенный» патефон? В доказательство он мог бы положить на холодильник любую пластинку и сказать: «Вот видите, он ее проигрывает!» Если бы Черепаха захотела что-то противопоставить этому дзен-буддйстскому акту, она должна была ответить: «Нет, ваш холодильник такого низкого качества, что его нельзя назвать патефоном: он вообще не может воспроизводить звуков (а тем более, саморазбивальных звуков)». Черепаха может записать пластинку под названием «Меня нельзя сыграть на патефоне X», только если патефон X действительно является патефоном! Метод Черепахи весьма хитер, так как он играет не на слабости системы, а на ее силе. Поэтому, чтобы он подействовал, необходимы патефоны достаточно высокого качества.
То же самое верно и для формальных вариантов теории чисел. ТТЧ является формализацией теории чисел (Ч) именно потому, что ее символы действуют «так как надо»: они не молчат, как холодильник, а выражают существующие в теории чисел истины. Конечно, так же ведут себя символы системы pr. Можно ли и эту систему считать за формализацию Ч, или же она больше похожа на холодильник? На самом деле, она чуть получше холодильника, но все еще очень слаба. Система pr не включает достаточного количества основных истин Ч и поэтому не может считаться за «теорию чисел».
Что же такое «основные истины» Ч? Это примитивно рекурсивные истины, что означает, что они включают только предсказуемо конечные вычисления. Эти основные истины являются для Ч тем же, чем четыре постулата Эвклида для геометрии: они позволяют нам забраковать некоторых кандидатов еще до начала игры, на основании того, что они «недостаточно мощные». В дальнейшем, критерием «достаточной мощности» системы будет представимость в ней всех примитивно рекурсивных истин.
Топор Ганто в метаматематике
Важность этого понятия видна из следующего факта; если у вас есть достаточно мощная формализация теории чисел, то к ней приложим метод Гёделя – следовательно, ваша система неполна. С другой стороны, если ваша система недостаточно мощна (то есть, если не все примитивно рекурсивные истины являются ее теоремами), то она, именно в силу этого недостатка, все равно является неполной. Здесь перед нами тот же «Гантов топор», перенесенный в метаматематику: что бы система не делала, Гёделев Топор отсечет ее голову! Заметьте, что это положение дел также напоминает спор о высоком и низком качестве патефонов в «Акростиконтрапунктусе».
На самом деле оказывается, что метод Гёделя приложим даже к намного более слабым системам: критерий мощности, по которому все примитивно рекурсивные истины должны быть теоремами системы, оказывается слишком строгим. Это похоже на вора, который грабит только «достаточно богатых» людей – его жертва должна иметь в кармане по меньшей мере миллион долларов. К счастью, в случае ТТЧ, мы сможем стать такими грабителями, так как миллион у нее есть – иными словами, ТТЧ действительно содержит все примитивно рекурсивные истины в виде теорем.
Прежде чем углубиться в подробное обсуждение примитивно рекурсивных функций и предикатов, я постараюсь связать эту тему с темами предыдущих глав, чтобы дать читателю определенную перспективу.
Как обнаружить порядок с помощью правильного фильтра
Мы уже с самого начала столкнулись с тем, что формальные системы могут вести себя как неукротимые и опасные бестии, когда в них есть удлиняющие и укорачивающие правила, поскольку это может привести к бесконечному поиску среди строчек. Открытие Гёделевой нумерации показало, что у любого поиска строчки с определенным типографским свойством есть арифметический кузен: изоморфный поиск целого числа с соответствующим арифметическим свойством. Следовательно, чтобы найти разрешающий алгоритм для формальных систем, необходимо решить проблему непредсказуемо длинного поиска – хаоса – среди строчек. Возможно, что в «Арии с различными вариациями» я преувеличил хаос в задачах о целых числах. В действительности, математикам удалось укротить гораздо худшие случаи кажущегося хаоса, чем проблема «интересности»; в конце концов, все они оказались довольно милыми зверями. Нерушимая вера Ахилла в регулярность и предсказуемость чисел достойна немалого уважения по крайней мере потому, что она отражает взгляды, которых придерживались почти все математики до 1930-х годов. Чтобы показать, почему противопоставление порядка и хаоса такая деликатная и важная тема, и связать ее с вопросом о местоположении и извлечении значения, я хотел бы процитировать здесь замечательный и памятный отрывок из диалога «Реальны ли числа?» написанного в Галилеевом стиле покойным Ж. М. Джочем (J.M. Jauch. Are quanta real?):
САЛВИАТИ: Представьте, что я даю вам два ряда чисел, например:
7 8 5 3 9 8 1 6 3 3 9 7 4 4 8 3 0 9 6 1 5 6 6 0 8 4 …
и
1, -1/3, +1/5, -1/7, +1/9, -1/11, +1/13, -1/15, …
Если бы я спросил вас, СИМПЛИЦИО, какое следующее число в первом ряду, что бы вы сказали?
СИМПЛИЦИО: Я бы не мог ответить. На мой взгляд, это случайный набор чисел, и в нем нет никакого закона.
САЛИВИАТИ: А как насчет второго ряда?
СИМПЛИЦИО: Это проще простого. Следующим числом будет +1/17.
САЛВИАТИ: Верно. Но что бы вы сказали, узнав, что первый ряд также построен по закону, причем точно по такому же, какой вы только что открыли для второго ряда?
СИМПЛИЦИО: Это мне кажется маловероятным.
САЛВИАТИ: На самом деле, это так и есть, поскольку первый ряд – просто начало десятичной дроби суммы второго ряда. Она равняется π/4.
СИМПЛИЦИО: У вас в запасе всегда есть какой-нибудь математический трюк, но я не понимаю, какое отношение это имеет к абстракции и реальности.
САЛВИАТИ: Для абстракции это легко заметить. Первый ряд выглядит случайным, пока мы не разовьем с помощью абстрагирования несложный фильтр, позволяющий нам замечать простую закономерность за кажущейся хаотической абстракцией.
Именно таким образом были открыты законы природы. Явления природы предстают перед нами как хаотические, пока мы не выберем некие значительные события и абстрагируемся от мелких, незначительных обстоятельств, в которых они происходили, так что эти события становятся идеализированными. Только тогда они предстают во всем блеске своей регулярности.
САГРЕДО: Чудесная мысль! Выходит, что пытаясь понять природу, мы должны воспринимать события так, словно это сообщения, которые надо расшифровать. Каждое сообщение выглядит случайным, пока мы не найдем кода для его прочтения. Этот код принимает абстрактную форму, поскольку мы сознательно игнорируем некоторые неважные детали; таким образом, отчасти мы сами выбираем содержание сообщения. Эти неважные сигналы – что-то вроде «шумового фона», который ограничит аккуратность нашего прочтения.
Но поскольку код не абсолютен, в нашем сыром материале может содержаться несколько сообщений, так что перемена кода позволит нам прочесть как значительное сообщение то, что прежде было просто шумом. И наоборот: в новом коде прежнее сообщение может стать бессмысленным.
Таким образом, код предполагает свободный выбор между разными, дополняющими друг друга аспектами, каждый из которых с одинаковым правом может именоваться реальностью, если я позволю себе использовать это сомнительное слово.
О некоторых из этих аспектов мы, возможно, на сегодняшний день даже не подозреваем, но они могут стать явными для наблюдателя с иной системой абстракций.
Но скажите мне, Салвиати, как в таком случае можно утверждать, что мы что-то открыли в реальном мире? Не значит ли это, что мы просто создаем вещи в согласии с нашими внутренними образами, и что действительность находится только у нас в голове?
САЛВИАТИ: Я не думаю, что это так – тем менее, этот вопрос требует более глубокого размышления.[40]40
J. M. Jauch, «Are Quanta Real?», стр. 63-65.
[Закрыть]
Джоч говорит здесь о «сообщениях», посланных не разумными существами, но самой природой. Однако вопрос об отношении смысла и сообщения, на который мы пытались ответить в главе VI, может быть задан и здесь. Хаотична ли природа, или же в ней имеется некая закономерность? И какова роль интеллекта в поисках ответа на этот вопрос?
Теперь оставим в стороне философию и подумаем над вопросом регулярности рядов, выглядящих хаотическими. Может ли быть; что у функции Q(n) из главы V есть также и простое, нерекурсивное объяснение? Можно ли увидеть любую проблему, как фруктовый сад, с такого угла, что ее секрет становится явным? Или же в теории чисел есть проблемы, остающиеся загадкой, с какого бы угла мы их не рассматривали?
После этого вступления мне кажется, что настало время точно определить термин «предсказуемо длинный поиск». Для этого мы воспользуемся языком БЛУП.
Основные шаги в языке Блуп
Мы займемся здесь поисками натуральных чисел с различными свойствами. Чтобы мы могли говорить о длине поиска, нам необходимо определить некие основные шаги, из которых состоит каждый поиск. Тогда мы сможем измерять длину поиска количеством шагов. Вот некоторые шаги, которые можно считать основными:
сложение двух натуральных чисел;
умножение двух натуральных чисел;
определение равенства двух чисел;
определение того, какое из двух чисел больше.
Петли и верхние границы
Если мы попытаемся сформулировать некий тест, – например, на простоту чисел, – в терминах таких шагов, мы вскоре увидим, что нам необходимо включить в него управляющую структуру – описание того, в каком порядке надо действовать: когда надо отойти назад и попытаться сделать что-то снова, или пропустить несколько шагов, или остановиться и т. п.
Любой алгоритм – описание того, как выполнить определенное задание – обыкновенно состоит из смеси (1) набора конкретных операций и (2) контрольных высказываний. Таким образом, разрабатывая наш язык для описания предсказуемо длинных вычислений, мы должны включить в него также основные контрольные структуры. Отличительное свойство Блупа – это ограниченное количество его контрольных структур. В нем нельзя совершать произвольные шаги или повторять группы шагов до бесконечности. Практически единственная контрольная структура Блупа – это ограниченные петли: набор команд, которые можно повторять снова и снова, но лишь ограниченное число раз; это число называется верхней границей, или потолком петли. Если потолок данной петли 300, то она может быть выполнена 0,7 или 300 раз – но не 301.
Программист не должен вводить в программу точной величины всех верхних границ; в действительности, он может и не знать этого заранее. Вместо этого, каждый потолок может быть вычислен до того, как программа начинает выполнять соответствующую петлю. Например, если вы собираетесь вычислить величину 2 3 n, у вас будут две петли. Сначала вы подсчитаете 3n; для этого вам придется применить умножение 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 РАЗ;
БЛОК 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.
Блуп – язык для определения предсказуемо конечных вычислений. Стандартное название функций, которые можно просчитать на Блупе, – примитивно-рекурсивные функции; стандартное название свойств, которые можно обнаружить с помощью тестов на Блупе, – примитивно-рекурсивные предикаты. Так, функция 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] = НЕТ)
