АЛГОРИТМ В АЛФАВИТЕ

Расстановка ударений: АЛГОРИ`ТМ В АЛФАВИ`ТЕ

АЛГОРИТМ В АЛФАВИТЕ А - «точное общепонятное предписание, определяющее потенциально осуществимый процесс последовательного преобразования абстрактных слов в алфавите А, процесс, допускающий любое слово в А в качестве исходного» (см. [1], с. 51).

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

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

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

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.