АЛГОРИТМОВ ЭКВИВАЛЕНТНОСТЬ

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

а) Рассматриваются всевозможные рекурсивные схемы- системы равенств, определяющие п- местные частично рекурсивные функции. Две схемы, определяющие функции и , наз. функционально эквивалентными, если для любых натуральных чисел имеет место условное равенство (оно считается верным, если обе его части осмысленны одновременно и в случае осмысленности принимают одинаковые значения). С. К. Клини (S.C. Kleene; см., напр., [1], с. 314) показал, что для любого всюду определенного вычислимого оператора над рекурсивными схемами можно указать схему Sтакую, что и функционально эквивалентны (так наз. теорема о неподвижной точке). Отсюда, в частности, вытекает теорема Успенского - Раиса о неразрешимости произвольного инвариантного относительно функциональной эквивалентности свойства рекурсивных схем при условии, что имеются схемы и такие, что обладает этим свойством, а им не обладает.Из этой теоремы следует неразрешимость и самого отношения функциональной эквивалентности.

б) Рассматриваются нормальные алгорифмы над фиксированным алфавитом А . Два таких алгорифма и наз. эквивалентными относительно А(см. [2], с. 51), если для любого слова Рв Авыполняется следующее условие: если один из этих алгорифмов перерабатывает Рв нек-рое слово Q, снова оказывающееся в алфавите А, то и второй из них также перерабатывает Рв Q. Те же алгорифмы наз. вполне эквивалентными относительно А, если для любого Рв Авыполняется условное равенство

Оба эти отношения неразрешимы.

в) Рассматриваются логич. схемы алгоритмов (схемы Янова, см. [3]). Реализацией такой схемы наз. последовательность операторов, выполняемых при прохождении по этой схеме от начала до конца. Две схемы наз. эквивалентными, если множества их реализаций совпадают. Отношение эквивалентности схем Янова оказалось разрешимым, и для него была построена полная система эквивалентных преобразований (см. [3], [4]).

Детальное изучение отношений А. э. представляет большой интерес в связи с рядом актуальных задач (особенно в области теории схем программ), требующих для своего решения развитой техники эквивалентных преобразований алгоритмов. Таковы, напр., задача трансляции алгоритмов (перевод с одного алгорптмич. языка на другой) и их оптимизации (преобразование с целью улучшения "рабочих характеристик"). В этом круге вопросов особое внимание уделяют (см., напр., [5]) возможности отыскания таких разрешимых отношений А. э., к-рые допускали бы удобные в приложениях полные системы эквивалентных преобразований. Концепция, намеченная в [3], во многом предопределила общий подход к исследованию отношений А. э.

Лит.:[1] Клини С. К., Введение в метаматематику, пер. с англ., М., 1957; [2] Марков А. А., Теория алгорифмов, М., 1954; [3] Янов К). И., "Проблемы кибернетики", 1958, в. 1, с. 75-127; [4] Ершов А. П., "Проблемы кибернетики", 1968, в. 20; [5] е го же, там же, 1973, в. 27.

Н. М. Нагорный.