Что такое Нормальный алгоритм Маркова
Нормальный алгоритм Маркова (НАМ) - это одна из фундаментальных моделей вычислений, придуманная в 1947 году советским математиком Андреем Марковым (в оригинальных трудах автора используется термин "алгорифм" - через букву Ф). По вычислительной мощности НАМ полностью эквивалентен машине Тьюринга.
История создания:
НАМ был разработан как альтернатива машине Тьюринга для формализации понятия алгоритма. Марков доказал, что любой алгоритм можно выразить через правила подстановки строк - простую, но мощную идею.
Как это работает?
Алгоритм получает слово и список правил замены. На каждом шаге он просматривает правила по порядку: нашел совпадение с левой частью - заменяет первое вхождение на правую часть и начинает проверку сначала. Если правило терминальное (с точкой) - останавливается. Если ни одно правило не подошло - тоже стоп.
Где это применяется:
- Теория вычислений - доказательство алгоритмической неразрешимости задач (например, проблемы эквивалентности слов).
- Формальные грамматики - правила вывода в лингвистике (иерархия Хомского во многом опирается на системы подстановок).
- Компиляторы и парсеры - лексический и синтаксический анализ программного кода базируется на принципах переписывания строк.
- Символьные вычисления - системы компьютерной алгебры (например, автоматическое упрощение математических формул).
Интересный факт: Нормальные алгоритмы часто путают с Цепями Маркова (которые лежат в основе современного ИИ и LLM). Однако Цепи Маркова создал отец ученого - А. А. Марков (старший) в 1906 году, а Нормальные алгоритмы - его сын в 1947 году.