Одним из основных вопросов, возникающих в процессе преобразования алго-ритмов, является их эквивалентность. Напомним, что два алгоритма считаются эквивалентными, если они имеют одну и ту же область определения, реализуемые ими функции совпадают, а система правил различна.
Можно определить сильную и слабую эквивалентность алгоритмов. Два алгоритма будем Называть слабо эквивалентными, если они имеют одну и ту же область определения и результаты переработки одинаковых слов из этой области совпадают.
Два алгоритма будем называть сильно эквивалентными, если они имеют одинаковую область определения и совпадают не только результаты переработки слов из этой области, но и сам процесс их переработки.
В “чистом виде” понятие эквивалентности двух алгоритмов U1 и U2 будем определять следующим образом. Для каждого алгоритма вводится понятие “входа” и “выхода”. Для каждого входа, который имеет смысл для данного алгоритма, выполнение алгоритма может приводить к некоторому выходу. Пусть х1 и х2 —
входы алгоритмов U1 и U2 соответственно. Алгоритмы U1 и U2 считаются эквивалентными, если из условия х1 == х2 следует, что если хотя бы один алгоритм, например U1, имеет выход у1, то и другой алгоритм также имеет выход у2, причем у1 == у2.
Таким образом, эквивалентность “в чистом виде” имеет место тогда, когда равенство входов приводит к равенству выходов. На практике большое значение имеет более общий способ введения эквивалентности, а именно определение эквивалентности с точностью до изоморфизма. В этом случае для выяснения вопроса об эквивалентности сопоставляются друг с другом не равные входы и выходы, а лишь находящиеся в соответствии, задаваемом изоморфизмом.
В этом случае между некоторыми входами х1 алгоритма U1 и входами х2 алгоритма U2 конструктивно задается некоторый изоморфизм I (в данном случае понимаемый просто как однозначное соответствие). Аналогично задается некоторый изоморфизм J между выходами у1 и у2 алгоритмов U1 и U2 соответственно.
Предикат от двух конструктивных объектов А и В “быть в соответствии, заданном изоморфизмом L ” будем обозначать через Аl ~ В.
Эквивалентность теперь будет определяться следующим образом. Алгоритмы U1 и U2 считаются эквивалентными, если из условия х1 ~ х2 следует, что если хотя бы один алгоритм имеет выход у1,то и другой алгоритм также имеет выход у2, причем у1 ~ у2.
Разные виды эквивалентности отличаются тем, как определяются “входы” и “выходы” алгоритма, а также тем, как фактически выбираются изоморфизмы I и J.
Между различными видами эквивалентности можно ввести частичное отношение порядка, выражающееся словами “сильнее” и “слабее”. Будем считать, что отношение эквивалентности Э1 слабее отношения эквивалентности Э2, если любые алгоритмы U1 и U2, эквивалентные в смысле Э2, эквивалентны и в смысле Э1, и в то же время есть хотя бы одна пара алгоритмов U1,U2 таких, что U1, U2, которые эквивалентны в смысле Э1 и не эквивалентны в смысле Э2.
Очевидно, чем слабее отношение эквивалентности, тем шире классы алгоритмов, эквивалентных согласно этому отношению. Естественным является стремление расширить классы эквивалентных алгоритмов, вводя более слабое определение эквивалентности. Однако при слишком слабом определении эквивалентности массовые проблемы, возникающие в теории алгоритмов, и среди них основная проблема распознавания эквивалентности алгоритмов, могут оказаться неразрешимыми. С другой стороны, слишком сильное определение эквивалентности чрезмерно сужает классы эквивалентных алгоритмов. Правильный выбор понятия эквивалентности играет большую роль как с точки зрения возможности получения содержательных теорем, так и с точки зрения их практической применимости.
На степень широты понятия эквивалентности наиболее существенно влияет выбор определения “выхода” алгоритма. Не во всех случаях нас могут интересовать в качестве выхода только те конструктивные объекты, которые формально объявляются результатами по окончании выполнения алгоритма. В некоторых случаях для нас является важной информация о каких-либо промежуточных результатах или о том, в какой последовательности выполнялись элементарные акты алгоритма и т. д. Поэтому в самом общем смысле под выходом алгоритма следует понимать какую-то запись всей той информации, которую можно получить, наблюдая процесс выполнения алгоритма.
Таким образом, чем больше информации, полученной в ходе выполнения алгоритма, несет в себе выход, тем более сильным оказывается отношение эквивалентности, основанное на таком определении выхода. Другими словами, все разнообразие эквивалентных алгоритмов состоит в том, что один и тот же конечный результат получается разными путями. Следовательно чем больше истории о том, как выполнялся алгоритм, содержит в себе выход, тем к более сильному понятию эквивалентности он приводит. Это объясняется тем, что в один класс эквивалентных алгоритмов попадают только те из них, история выполнения которых соответствует истории, зафиксированной в данном выходе.
Исчерпывающую информацию о том, как происходило выполнение алгоритма, можно получить, рассматривая в качестве выхода алгоритма всю последовательность выполнявшихся операторов — значение операторного алгоритма. В этом случае алгоритмы считаются эквивалентными, если их значения совпадают при одинаковых входах. Такое определение эквивалентности рассматри-валось Ю.И.Яновым, для операторных алгоритмов Ляпунова. В этом случае им была доказана разрешимость проблемы эквивалентности. Однако такое определение эквивалентности является слишком сильным и многие алгоритмы, которые разумно считать эквивалентными, при таком определении оказываются неэквивалентными.
Исходя из этого в качестве выхода операторного алгоритма целесообразно рассматривать нечто такое, что по количеству информации о ходе выполнения алгоритма было бы чем-то средним между значением алгоритма и значением результативного переменного по окончании выполнения алгоритма. С этой точки зрения будем рассматривать в качестве выхода S-представления тех переменных, значения которых нас интересуют в качестве результатов выполнения операторного алгоритма.
Если ввести определения эквивалентности, базирующееся на использовании S-представления в качестве выхода, то тогда можно сказать, что два алгоритма эквивалентны по отношению к выделенным переменным в том случае, если соответствующие переменные при совпадающих входах вычисляются по одинаковым формулам. S-представление переменного есть не что иное, как явное выражение формулы, по которой вычислялось результирующее значение переменного для данных исходных значений функциональных переменных.
Как известно, в программировании важную роль играют именно такие преобразования алгоритмов, которые оставляют расчетные формулы (S-представления) неизменными. Действительно, такие основные приемы программирования, как разбиение задачи на части, расчленение формул, выделение промежуточных результатов, преобразование логических операторов, экономия команд и ячеек памяти, приводят к таким преобразованиям алгоритмов, которые сохраняют S-представления результативных переменных.