Алгоритм В Алфавите

А -"точное общепонятное предписание, определяющее потенциально осуществимый процесс последовательного преобразования абстрактных слов в алфавите А, процесс, допускающий любое слово в A в качестве исходного" (см. [1], с. 51). А. В а. Представляют собой частный случай общего понятия алгоритма. Исходными данными и возможными результатами применения А. В а. Являются конструктивные объекты достаточно общего типа - слова, и это обстоятельство определяет роль понятия А. В а. В математике. К 70-м гг. 20 в. Были выработаны различные уточнения (стандартизации) понятия А. В а. Наибольшую известность среди них получили нормальные алгорифмы А. А. Маркова и алгоритмы, определяемые на основе понятия Тьюринга машины. При построении конкретных А.

В а., иногда по соображениям технического характера, связанным с деталями определения алгоритма или кодировки исходных данных, приходится расширять исходные алфавиты путем введения дополнительных букв и рассматривать алгоритмы в так расширенных алфавитах. В таких ситуациях удобным инструментом является понятие алгоритма над данным алфавитом, т. Е. Алгоритма в нек-ром расширении этого алфавита. Для двух алгоритмов над данным алфавитом могут быть естественным образом введены понятия эквивалентности и полной эквивалентности относительно него этих алгоритмов. Лит.:[1] Марков А. А., Теория алгорифмов, "Тр. Матем. Ин-та АН СССР", 1954, т. 42. Н. М. Нагорный.