2.1. О сравнении классов схем. Программы для ЭВМ, будь

то программы, записанные на операторном языке, или программы

на рекурсивном языке, универсальны в том смысле, что любую

вычислимую функцию можно запрограммировать и найти ее

значения для заданных значений аргументов. При этом, как уже

указывалось, не требуется богатого набора программных прими-

тивов и базовых операций: достаточно тех средств, которые мо-

делируются стандартными схемами, плюс одна интерпретирован-

ная операция и один предикат. Это значит, что различные классы

программ не имеет смысла сравнивать по мощности, понимаемой

как способность реализовать различные алгоритмы,— все они

оказываются универсальными. В то же время программисты знают,

что одни программные примитивы являются «более выразитель-

ными», чем другие, что запись алгоритмов с привлечением рекур-

сии короче, чем итерационное представление, но вычисления по

такой программе могут истребовать больше времени, и т. д. При

переходе к схемам программ возникает возможность поставить

и исследовать проблему выражения одних наборов примитивов

через другие в более чистом виде. Задачи такого типа образуют

сравнительную схематологию, основу которой составляют теоре-

мы о возможности или невозможности преобразования схем из

одного класса в схемы другого. При этом наряду с основной за-

дачей — выяснением соотношений между различными средствами

программирования — решается и другая, внутренняя задача схе-

матологии. Действительно, если мы умеем трансформировать один

класс схем в другой, то сможем переносить результаты, получен-

ные для некоторого класса схем, на другие классы.

В этой главе рассматриваются рекурсивные схемы, но так

как в следующей главе речь пойдет о других классах схем прог-

рамм, имеет смысл ввести необходимые понятия сравнительной

схематологии для произвольных классов схем программ.

Пусть У— класс схем программ в некотором базисе B, У —

класс схем программ в базисе У’. Базис любого из рассматривае-

мых классов схем включает множества: переменных, базовых

функциональных символов, предикатных символов, другие мно-

жества, специфичные для данного класса.

Мы будем сравнивать классы схем, у которых базисы согла-

сованны в том смысле, что первые три из перечисленных множеств

одинаковы в данных базисах. Это дает возможность превращать

в программы схемы из разных классов с помощью одной и той же

интерпретации базисов. Например, полные базисы стандартных

и рекурсивных схем согласованны, т. е. определение функцио-

дальней эквивалентности может быть обобщено на схемы из раз-

ных классов.

Схема S₁ нз класса У и схема S₂, из класса У’ функционально

эквивалентны., если для любой интерпретации I согласованных

базисов классов У u У’ программы (S₁, I), (S₂, I) или   обе

зацикливаются, или обе останавливаются с одним и тем же резуль-

татом.

Говорят, что класс схем У мощнее класса схем У’, или класс

У’ транслируем в класс У (обозначение: УУ’), если для любой

схемы из У’ существует эквивалентная ей схема в классе У.

Класс У строго мощнее класса У’ (У > У’), если У мощнее

У’ и в У существует схема, для которой нет эквивалентной схемы

в У’ (класс У’ не транслируем в класс У). Классы У и У’

равномощны, если У мощнее У’ и У’ мощнее У. Класс схем У

эффективно транслируем в класс схем У’, если существует алго-

ритм, преобразующий любую схему из У в эквивалентную схему

из У’. Классы У и У’ эффективно равномощны, если У эффек-

тивно транслируем в У’ и У’ эффективно транслируем в У.

Ниже, когда устанавливается транслируемость одного класса

схем в другой или их равномощность, фактически демонстрируется

эффективная транслируемость или эффективная равномощность.

2.2. Трансляция стандартных схем в рекурсивные. В рекур-

сивных схемах результат поставляет ровно один терм, а в стан-

дартных схемах заключительные оператор может содержать

любой конечный набор термов и тогда результат программы —

не один элемент из области интерпретации, а набор таких эле-

ментов. Однако такое отличие не имеет принципиального значе-

ния для транслируемости схем. Можно было бы определить ре-

курсивные схемы, поставляющие в качестве результата наборы

термов, например, используя интерпретированную функцию пе-

чать (т₁, . . ., т_n). Мы поступим проще — ограничим класс стан-

дартных схем схемами над базисом, содержащим заключительные

операторы только следующего вида: стоп(х), хХ.

Т е о р е м а (Маккарти). Класс стандартных схем транс-

лируем в класс рекурсивных схем.