Эквивале́нтные преобразова́ния управля́ющих систе́м, преобразования, сохраняющие отношение эквивалентности управляющих систем. Используются в задачах оптимизации, контроля, а также как средство характеризации (например, аксиоматизации) определённых классов управляющих систем; вывод в формальных системах также можно рассматривать как эквивалентные преобразования управляющих систем. В качестве отношения эквивалентности обычно рассматривают функциональную эквивалентность, т. е. в этом случае эквивалентными являются управляющие системы, имеющие одинаковые функции. Иногда по тем или иным соображениям рассматривают и другие отношения эквивалентности.

С эквивалентными преобразованиями управляющих систем связан широкий круг задач, конкретная постановка которых варьируется в зависимости от особенностей рассматриваемого класса управляющих систем. Основные из этих задач следующие.

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

Наиболее распространены такие постановки задачи, когда средства решения ограничиваются следующим образом. Определяют понятие фрагмента (или подсхемы) управляющей системы и рассматривают преобразования управляющей системы, состоящие в замене одних фрагментов управляющей системы другими. Таким образом, пара $(\alpha, \beta)$ фрагментов определяет множество преобразований произвольной управляющей системы $\gamma$, каждое из которых состоит в замене некоторого вхождения фрагмента $\alpha$ в $\gamma$ фрагментом $\beta$ (если $\gamma$ не содержит вхождений фрагмента $\alpha$, то считается, что преобразование, определяемое парой $(\alpha, \beta)$, оставляет $\gamma$ без изменения). Пара фрагментов $(\alpha, \beta)$ называется правилом для данного класса управляющих систем, если преобразования, определяемые этой парой, сохраняют отношение эквивалентности, т. е. переводят произвольную управляющую систему из данного класса в эквивалентную ей. Некоторые правила могут быть снабжены условиями их применимости, описывающими ситуации, в которых их разрешается применять, и гарантирующими сохранение отношения эквивалентности. Если правило $(\alpha, \beta)$ применимо к любому вхождению фрагмента $\alpha$ во всякой управляющей системе, то оно называется локальным. Нелокальность правила обычно означает, что его применимость определяется строением всей управляющей системы. Понятие полноты системы правил часто определяют в следующей форме.

Говорят, что пара фрагментов $(\alpha, \beta)$ выводима из системы правил $\Sigma$, если фрагмент $\alpha$ с помощью правил из $\Sigma$ можно преобразовать во фрагмент $\beta$ (применение правил к фрагменту определяется так же, как и для управляющей системы). Система правил $\Sigma$ называется полной, если из неё выводимы все пары вида $(\alpha, \beta)$, где $\alpha$ и $\beta$ – эквивалентные управляющие системы. Обычно наряду с правилами рассматриваются схемы правил, содержащие те или иные параметры (свободные переменные). Каждая схема правил путём придания параметрам конкретных значений порождает в общем случае бесконечное множество правил, и наиболее распространённая постановка задачи состоит в том, чтобы для данного класса управляющих систем найти конечную полную систему схем правил.

2. Проблема полноты систем правил преобразований (как для индивидуальных систем, так и в алгоритмическом плане): по системе правил определить, является ли она полной или нет.

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

4. Построение оптимизирующих (или вообще целенаправленных) процедур преобразований. Наиболее часто речь здесь идёт о минимизации сложности схем управляющей системы либо о преобразовании управляющей системы в некоторую каноническую форму, единственную в классе эквивалентности. В последнем случае решение задачи даёт и разрешающую процедуру для отношения эквивалентности. Целью преобразований может быть также построение самокорректирующихся или других специальных управляющих систем. С задачей оптимизации связан целый ряд задач метрического характера, например получение оценок сложности решений, доли оптимальных управляющих систем и тому подобное.

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

Особенности конкретных классов управляющих систем накладывают отпечаток на постановку и методы решения указанных задач. Ниже рассмотрены некоторые примеры.

Эквивалентные преобразования в алгебрах. Каждой алгебре некоторой сигнатуры соответствует бесконечный класс управляющих систем – множество всех термов (формул) данной сигнатуры (вместе с определяемыми ими функциями). Естественным отношением эквивалентности на множестве термов является отношение функциональной эквивалентности: термы $t_1$ и $t_2$ эквивалентны тогда и только тогда, когда они определяют одну и ту же функцию с точностью до несущественных аргументов. В этом случае обычно пишут: $t_1=t_2$ (или $t_1=t_2$), и такие выражения называются тождествами или равенствами данной алгебры. В качестве фрагментов термов рассматриваются подтермы, т. е. такие части, которые сами являются термами. Так как любая замена подтерма эквивалентным ему термом сохраняет отношение эквивалентности, то любое тождество алгебры (рассматриваемое как неупорядоченная пара термов) является локальным правилом. Всякое тождество алгебры можно рассматривать и как схему правил, параметрами которой являются переменные. Поэтому для алгебр задача 1 приобретает следующий вид: для данной алгебры найти конечную полную систему тождеств, рассматриваемых как схемы правил, т. е. в этом случае задача 1 эквивалентного преобразования совпадает с задачей алгебраической аксиоматизации алгебр.

Существование конечной полной системы тождеств является функциональным свойством алгебр, т. е. оно полностью определяется классом функций, выразимых в данной алгебре, и не зависит от сигнатуры. Любая функционально полная (конечная) алгебра имеет конечную полную систему тождеств; любая двухэлементная алгебра имеет конечную полную систему тождеств; существуют трёхэлементные группоиды, конечные полугруппы и бесконечные группы, не имеющие конечных полных систем тождеств; любая конечная группа имеет конечную полную систему тождеств; для алгебр всех рекурсивных функций, а также для алгебры регулярных событий задача 1 решается отрицательно.

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

Эквивалентные преобразования контактных схем. Как и для термов, понятие фрагмента совпадает с понятием контактной схемы. Требует уточнения только определение множества полюсов во вхождении фрагмента в схему. Две контактные схемы, между полюсами которых установлено взаимно однозначное соответствие, считаются эквивалентными, если функция проводимости между произвольными полюсами одной схемы совпадает с функцией проводимости между соответствующими полюсами другой. Если пары эквивалентных контактных схем рассматривать как схемы правил, параметрами которых являются буквы, приписанные рёбрам схем, и считать, что каждая такая схема порождает правила только путём переименования этих букв, то для класса всех контактных схем не существует конечной полной системы схем правил. В то же время для любого $n$ для класса всех контактных схем, рёбрам которых приписано не более $n$ различных букв, конечная полная система таких схем правил существует. Если же допустить порождение конкретных правил из схем путём согласованной замены рёбер с одинаковыми буквами произвольными контактными схемами, то и для класса всех контактных схем может быть построена конечная полная система правил.

Эквивалентные преобразования автоматов. Для конечных автоматов не существует конечной полной системы локальных правил преобразований. Однако с использованием нелокальных правил или схем правил, зависящих от специальных параметров, задача 1 для них может иметь положительное решение. С конечными автоматами связана алгебра регулярных событий, элементами которой являются множества слов, представимые (распознаваемые) конечными автоматами, а сигнатурными операциями служат объединение $x \vee y$, конкатенация $x y$ и итерация $x^*$. Для этой алгебры не существует конечной полной системы тождеств. Однако подалгебра, состоящая из всех событий, содержащих пустое слово, имеет конечную полную систему тождеств.

Эквивалентные преобразования алгоритмов. Для полного класса алгоритмов и функционального отношения эквивалентности проблема эквивалентных преобразований имеет отрицательное решение, поскольку отношение функциональной эквивалентности в этом случае не является рекурсивно перечислимым. Поэтому для получения положительных решений либо сужают класс алгоритмов, либо прибегают к модификации постановки проблемы. Для задания подклассов алгоритмов часто используют конечные автоматы, автоматы с магазинной или стэковой памятью, дискретные преобразователи различного вида, программы с ограничениями на топологическую структуру или на объём рабочей памяти и т. д. Иногда подклассы алгоритмов выделяются по функциональному признаку путём задания класса вычислимых функций. В последнем случае обычно задаётся определённое базисное множество функций, которое замыкается с помощью таких операций, как суперпозиция, рекурсия, ограниченное суммирование и т. п. Однако для выделяемых таким путём классов алгоритмов отношение функциональной эквивалентности оказывается разрешимым лишь в тех случаях, когда соответствующий класс функций достаточно беден.

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

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