О сравнении классов схем

Программы для ЭВМ, будь-то программы, записанные на операторном языке, или программы на рекурсивном языке, универсальны в том смысле, что любую вычислимую функцию можно запрограммировать и найти ее значения для заданных значений аргументов. При этом не требуется богатого набора программных примитивов и базовых операций: достаточно тех средств, которые моделируются стандартными схемами. Это значит, что различные классы программ не имеет смысла сравнивать способности реализовать различные алгоритмы, — все они оказываются универсальными. В то же время программисты знают, чтоодни программные примитивы являются «более выразительными», чем другие, что запись алгоритмов с привлечением рекурсии короче, чем итерационное представление, но вычисления по такой программе могут потребовать больше времени, и т. д. При переходе к схемам программ возникает возможность поставить и исследовать проблему выражения одних наборов примитивов через другие в более чистом виде. Задачи такого типа образуют сравнительную схематологию, основу которой составляют теоремы о возможности или невозможности преобразования схем из одного класса в схемы другого. При этом наряду с основной задачей — выяснением соотношений между различными средствами программирования — решается и другая, внутренняя задача схематологии. Действительно, если мы умеем трансформировать один класс схем в другой, то сможем переносить результаты, полученные для некоторого класса схем, на другие классы.

Мы будем сравнивать классы схем, у которых базисы согласованны в том смысле, что множества переменных, базовых функциональных символов и предикатных символов одинаковы в данных базисах. Это дает возможность превращать в программы схемы из разных классов с помощью одной и той же интерпретации базисов. Например, полные базисы стандартных и рекурсивных схем согласованны, т. е. определение функциональной эквивалентности может быть обобщено на схемы из разных классов.

Схема S₁ из класса W и схема S₂ из класса W’ функционально эквивалентны, если для любой интерпретации I согласованных базисов классов W и W’ программы (S₁, I), (S₂, I)или обе зацикливаются, или обе останавливаются с одним и тем же результатом.

Класс схем W мощнее класса схем W’, или класс W’ транслируем в класс W, если для любой схемы из W’ существует эквивалентная ей схема в классе W. Классы W и W’ равномощны, если W’ мощнее W и W мощнее W’.

Доказано, что класс ССП транслируем в класс РС и класс РС не транслируем в класс ССП.

Рассмотренные примеры подтверждают первое утверждение для одинаковых интерпретаций I базисов. В этом случае РС R_S1 эквивалентна ССП S₁. При разных интерпретациях ССП и РС результаты будут различаться и следовательно программы (R_S1, I₁) и (S₁, I₂) будут различны.

Второе утверждение подкрепляется РС R_S3. Причина не транслируемости этой схемы обусловлена тем, что при варьировании интерпретаций возникает необходимость запомнить сколь угодно большое число промежуточных значений, в то время как память любой стандартной схемы ограничена.

Существуют некоторые классы РС, транслируемые в ССП. К ним относится класс линейных унарных РС, имеющих базис с единственной переменной x и одноместными функциональными и предикатными символами. Например:

R_S4: F(x); F(x)=ifp(x) then x elsef(x, F(g(x))) транслируема в ССП.