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

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

Н. А. Криницкий.