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

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

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

а) Рассматриваются всевозможные рекурсивные схемы- системы равенств, определяющие п- местные частично рекурсивные функции. Две схемы, определяющие функции и , наз. функционально эквивалентными, если для любых натуральных чисел имеет место условное равенство (оно считается верным, если обе его части осмысленны одновременно и в случае осмысленности принимают одинаковые значения). С. К. Клини (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.

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


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Игры ⚽ Нужна курсовая?

Полезное


Смотреть что такое "АЛГОРИТМОВ ЭКВИВАЛЕНТНОСТЬ" в других словарях:

  • Эквивалентность детерминированных и недетерминированных конечных автоматов — Конечный автомат  в теории алгоритмов математическая абстракция, позволяющая описывать пути изменения состояния объекта в зависимости от его текущего состояния и входных данных, при условии что общее возможное количество состояний конечно.… …   Википедия

  • АЛГЕБРА ЛОГИКИ —         система алгебраич. методов решения логич. задач, а также совокупность задач, решаемых такими методами. А. л. в узком смысле слова алгебраич. (табличное, матричное) построение классич. логики высказываний, в котором рассматриваются… …   Философская энциклопедия

  • АЛГОРИТМ —         [от algorithm!; algorismus, первоначально лат. транслитерация имени ср. азиат. учёного 9 в. Хорезми (Мухаммед бен Муса аль Хорезми)], программа, определяющая способ поведения (вычисления); система правил (предписаний) для эффективного… …   Философская энциклопедия

  • АЛГОРИТМИЧЕСКАЯ ПРОБЛЕМА — проблема, в к рой требуется найти единый метод ( алгоритм).для решения бесконечной серии однотипных единичных задач. Такие проблемы иногда наз. также массовыми проблемами. А. п. возникали и решались в различных областях математики на протяжении… …   Математическая энциклопедия

  • ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ — управ ляющих систем преобразования, сохраняющие отношение эквивалентности (о. э.) управляющих систем (у. с.). Используются в задачах оптимизации, контроля, а также как средство характеризации (напр., аксиоматизации) определенных классов у. с.;… …   Математическая энциклопедия

  • Арифметика — Ганс Себальд Бехам. Арифметика. XVI век Арифметика (др. греч. ἀ …   Википедия

  • Недетерминированная машина Тьюринга — Машина Тьюринга Варианты машин Универсальная машина Тьюринга Квантовая машина Тьюринга en:Read only Turing machine en:Read only right moving Turing Machines Вероятностная машина Тьюринга Недетер …   Википедия

  • Coq — (фр. coq  петух)  интерактивное программное средство доказательства теорем, использующее собственный язык функционального программирования (Gallina) с зависимыми типами. Позволяет записывать математические теоремы и их… …   Википедия

  • Автоматов теория —         часть теоретической кибернетики (См. Кибернетика), объектом исследования которой являются различные преобразователи дискретной информации; возникла в начале 50 х гг. 20 в. в связи с требованиями практики проектирования вычислительных… …   Большая советская энциклопедия

  • КОМБИНАТОРНЫЙ АНАЛИЗ — комбинаторная математика, комбинаторика, раздел математики, посвященный решению задач выбора и расположения элементов нек рого, обычно конечного, множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения… …   Математическая энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»