Эквивалентные преобразования

управ ляющих систем - преобразования, сохраняющие отношение эквивалентности (о. э.) управляющих систем (у. с.). Используются в задачах оптимизации, контроля, а также как средство характеризации (напр., аксиоматизации) определенных классов у. с.; вывод в формальных системах также можно рассматривать как Э. п. управляющих систем. В качестве о. э. обычно рассматривают функциональную эквивалентность, т. е. в этом случае эквивалентными являются у. с., имеющие одинаковые функции. Иногда по тем или иным соображениям рассматривают и другие о. э. С Э. п. отношение функциональной эквивалентности оказывается разрешимым лишь в тех случаях, когда соответствующий класс функций достаточно беден. Поэтому развиваются другие подходы, в частности подход, основанный на изучении схем алгоритмов. Схемы алгоритмов отличаются от алгоритмов в основном способом приписывания им функций. При этом отношение эквивалентности схем алгоритмов рассматривается как определенная аппроксимация отношения функциональной эквивалентности алгоритмов, так что решение проблемы Э. п. для схем алгоритмов можно считать приближенным решением этой проблемы для алгоритмов. Однако и здесь положительные решения удается получать лишь для достаточно грубых приближений, близких к конечным автоматам. Возможность получения положительных решений для класса всех алгоритмов появляется при ослаблении понятия полноты системы правил, напр. при отказе от требования конечного числа применений правил. Точное, система правил наз. предельно полной, если, применяя ее правила, можно любые два эквивалентных алгоритма преобразовать в пределе, т. е. за бесконечное число шагов, в один (в общем случае бесконечный) вычислительный комплекс. Конечную предельно полную систему схем локальных правил оказалось возможным построить для функционально полного класса всюду определенных программ в нек-ром простом базисе. Реальный смысл предельной полноты состоит, в частности, в том, что предельно полные системы являются полными в обычном смысле для класса программ, вычисляющих конечные функции. В связи с задачей оптимизации у. с. важную роль играют направленные преобразования, дающие в конечном с/чете оптимальные или близкие к ним у. с. В частности, большой интерес представляет изучение возможностей монотонных преобразований, к-рые на каждом шаге не повышают сложность у. с. в том или ином смысле.