1.6. Алюритмы 75
сматривать как сложную, рекурсивно определяемую операцию
над последовательностями знаков; подробнее об этом см.
3.5.7.
Поэтому понятие элементарности всегда относительно.
В зависимости от информации, содержащейся в обрабаты-
ваемых сообщениях, часто, наоборот, рассматривают как эле-
ментарные такие такты обработки, которые, собственно гово-
ря,
являются сложными. Основанием для этого может служить,
например,
тот факт, что такие макротакш фактически состоят
из
конечного числа описанных выше текстовых замен, причём
их внутренняя
структура
несущественна для предпринимаемой
обработки. Так обстоит дело, скажем, для сложения, вычита-
ния,
умножения и деления с остатком, в
случае
когда сообще-
ния
пред&тавлены целыми числами в некоторой цифровой фор-
ме записи. В остальном же несущественно, представлена по-
следовательность инструкций в виде диаграммы или как-нибудь
более схематично, равно как несущественно и то, описаны от-
дельные такты обработки словесно или заданы посредством
•формул.
Собственно действия с числами в цифровой записи
относятся,
таким образом, к классу алгоритмов над цепочками
знаков.
Здесь в арифметике мы обнаруживаем исторические
корни
слова algorismo; еще Лейбниц говорил об „алгоритме
умножения".
1.6.4.2.
Рекурсивные
алгоритмы
по Маккарти
И
всё-таки при описании алгоритмов, вообще говоря, не-
целесообразно составлять правило обработки из простых шагов
текстовой замены, как это делается в алгоритмах Маркова.
Мозаичность описания посредством обособленных операций
текстовой замены без нужды затрудняет составление алгоритма,
а также проверку того, реализует ли записанный алгоритм по-
ставленную цель. При этом громоздким становится описание
даже
„школьного" выполнения арифметических действий над
числами в цифровой форме записи. Использование вычислитель-
ной
машины в качестве инструмента наводит пользователя на
мысль рассматривать некоторые изначально сложные такты
обработки как элементарные; хотя, впрочем, сведение этих так-
тов обработки к текстовым заменам может происходить по-
разному на разных вычислительных машинах.
Другую
форму описания алгоритмов, обладающую вдобавок
тем преимуществом, что её принципиальные элементы не огра-
ничиваются явными действиями над последовательностями зна-
ков,
мы положим в основу в следующей главе. Эти алгорит-
мы — мы
будем
называть их
подпрограммами
— определяют
отображения посредством формальных композиций (последо-