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

Расстановка ударений: АЛГОРИ`ТМОВ ЭКВИВАЛЕ`НТНОСТЬ

АЛГОРИТМОВ ЭКВИВАЛЕНТНОСТЬ - бинарное отношение, связывающее алгоритмы фиксированного типа и выражающее тот факт, что у всяких двух связанных этим отношением алгоритмов при совпадении определенного вида исходных данных совпадают и результаты работы (а также, быть может, и нек-рые дополнительные сведения относительно выполненных при этом вычислений - так наз. истории вычислений). Ниже приведено несколько типичных примеров таких отношений.

а) Рассматриваются всевозможные рекурсивные схемы - системы равенств, определяющие n-местные частично рекурсивные функции. Две схемы, определяющие функции φ и ψ, наз. функционально эквивалентными, если для любых натуральных чисел x₁, ..., x_n имеет место условное равенство

(оно считается верным, если обе его части осмысленны одновременно и в случае осмысленности принимают одинаковые значения). С. К. Клини (S. C. Kleene; см., напр., [1], с. 314) показал, что для любого всюду определенного вычислимого оператора над рекурсивными схемами можно указать схему S такую, что S и (S) функционально эквивалентны (так наз. теорема о неподвижной точке). Отсюда, в частности, вытекает теорема Успенского-Райса о неразрешимости произвольного инвариантного относительно функциональной эквивалентности свойства рекурсивных схем при условии, что имеются схемы S₁ и S₂ такие, что S₁ обладает этим свойством, a 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.

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

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.