Значення алгоритмів еквівалентності в математичній енциклопедії
Значення алгоритмів еквівалентності в математичній енциклопедії:
бінарне відношення,що зв'язує алгоритми фіксованого типу і виражає той факт, що у будь-яких двох пов'язаних цим ставленням алгоритмів при збігу певного виду вихідних даних збігаються і результати роботи (а також, можливо, і деякі додаткові відомості щодо виконаних при цьому обчислень - так званої історії обчислень). Нижче наведено кілька типових прикладів таких взаємин.
а) Розглядаються всілякі рекурсивні схеми-системи рівностей, що визначаютьп-місцеві частково рекурсивні функції. Дві схеми, що визначають функції та , зв. функціонально еквівалентними, якщо для будь-яких натуральних чисел має місце умовна рівність (вона вважається вірною, якщо обидві її частини осмислені одночасно і у разі свідомості набувають однакових значень). С. К. Кліні (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.