Математическая энциклопедия - алгоритм в алфавите

А -"точное общепонятное предписание, определяющее потенциально осуществимый процесс последовательного преобразования абстрактных слов в алфавите А, процесс, допускающий любое слово в A в качестве исходного" (см. [1], с. 51). А. в а. представляют собой частный случай общего понятия алгоритма.

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

Лит.:[1] Марков А. А., Теория алгорифмов, "Тр. матем. ин-та АН СССР", 1954, т. 42. Н. М. Нагорный.

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

И. М. Виноградов

1977—1985