Нормальные алгорифмы А.А. Маркова

А.А. Марков (1903-1979 гг.) – советский математик, занимавшийся математической логикой и конструктивной математикой разработал так называемые нормальные алгорифмы (это название используется только применительно к модели Маркова), основанные на полусистемах Туэ (ассоциативное исчисление, разработанное шведским математиком Акселем Туэ). Задаётся конечный алфавит A и конечное множество подстановок P. Работа алгоритма состоит из выполнения двух операторов: распознавателя и подстановки [36].

Оператор-распознаватель находит вхождение левой части подстановки в слово I, а оператор-подстановка заменяет это вхождение правой частью подстановки.

Совокупность всех слов в данном алфавите вместе с системой подстановок – ассоциативное исчисление.

Нормальный алгорифм останавливает процесс в случаях:

1. Подходящая подстановка не найдена.

2. Применена последняя подстановка.

Пример. А={0,1}.

Система подстановок Р:

где Ñ – обозначает последнюю подстановку.

Пусть I=0100011.

Тогда с учетом первого вхождения левой части второй подстановки (00→1) в слово I, получаем: 011011. Далее, применяя подстановку (110→1), получим 0111. Наконец, применив подстановку (111→0 Ñ), получаем результат 00. Конец работы алгоритма.

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

По существу это последовательные преобразования входных слов, составленных из символов конечного алфавита.

Различные формализации понятия алгоритмы, предложенные разными авторами, оказались в точности эквивалентными.