Нормальные алгорифмы Маркова: модель подстановок

Когда говорят «алгоритм», обычно представляют пошаговую программу с переменными и циклами. Но в теории вычислений придумали модели, где никаких переменных нет вообще, а вся работа сводится к переписыванию строки по фиксированным правилам. Нормальные алгорифмы Маркова (НАМ) - одна из таких моделей: вы берёте слово, ищете в нём первое подходящее правило подстановки, заменяете кусок и повторяете, пока есть что заменять. Несмотря на крайнюю простоту, эта схема вычисляет ровно то же, что и машина Тьюринга. Разберём, как устроены правила, в каком порядке они применяются и почему «алгорифм» пишется через «ф».

Ниже - интерактивный разбор: задайте схему подстановок и входное слово, и ИИ протрассирует выполнение шаг за шагом.

Что такое нормальный алгорифм Маркова

Нормальный алгорифм Маркова - это способ преобразования слов в некотором алфавите при помощи упорядоченного списка правил подстановки. Модель предложил советский математик Андрей Андреевич Марков-младший в конце 1940-х годов как строгое уточнение интуитивного понятия «алгоритм». Написание «алгорифм» через «ф» - авторская традиция самого Маркова (от греческого происхождения слова), её сохраняют в литературе именно для этой конкретной модели.

Всё, чем оперирует НАМ, - это конечный алфавит $A$ (множество допустимых символов) и схема - пронумерованный сверху вниз список правил вида «найди подслово $\alpha$ и замени его на $\beta$». Никаких ячеек памяти, регистров или счётчиков: состояние вычисления - это целиком текущее слово.

Рассчитать для своей задачи

Идея роднит НАМ с другими формализмами переписывания строк. Если вам ближе ленточная модель, посмотрите разбор машины Тьюринга и проблемы остановки - НАМ доказуемо равномощен ей, но выглядит совершенно иначе.

Правила подстановки: обычные и заключительные

Каждое правило схемы записывают как $\alpha \to \beta$, где $\alpha$ и $\beta$ - слова в алфавите $A$ (возможно, пустые). Смысл: левую часть $\alpha$, найденную в текущем слове, заменяют на правую часть $\beta$.

Правила бывают двух видов:

• Обычная подстановка $\alpha \to \beta$ - после замены алгорифм продолжает работу: снова просматривает схему с самого начала.
• Заключительная подстановка $\alpha \to \cdot\, \beta$ (с точкой после стрелки) - после замены алгорифм останавливается, выдавая получившееся слово как результат.

Заключительные правила - единственный «штатный» способ завершить вычисление успешно. Если же ни одно правило схемы к текущему слову неприменимо (ни одна левая часть в нём не находится), алгорифм тоже останавливается - это второй вариант остановки.

Порядок применения: два «первых»

Главная тонкость НАМ - жёстко фиксированный порядок выбора. На каждом шаге алгорифм действует так:

$$\begin{aligned} &1.\ \text{просматривает правила сверху вниз;} \\ &2.\ \text{берёт } \textbf{первое} \text{ правило, чья левая часть есть в слове;} \\ &3.\ \text{заменяет } \textbf{самое левое} \text{ вхождение этой левой части.} \end{aligned}$$

То есть «первое» здесь двойное: первое подходящее правило в списке и первое (левое) вхождение его левой части в слове. Эта детерминированность отличает НАМ, например, от недетерминированных систем переписывания - здесь следующий шаг всегда определён однозначно.

Рассчитать для своей задачи

После замены - если правило было обычным - всё начинается заново с верхней строки схемы. Именно поэтому одно и то же правило может срабатывать много раз подряд, постепенно «прогоняя» слово.

Пример: удаление всех символов a

Возьмём алфавит $A = \{a, b\}$ и схему из одного обычного правила и одного заключительного:

$$\begin{aligned} &a \to \Lambda \\ &\Lambda \to \cdot\, \Lambda \end{aligned}$$

Первое правило заменяет первую найденную букву $a$ на пустое слово (стирает её). Второе правило с пустой левой частью применимо всегда и заключительное - оно срабатывает, когда букв $a$ уже не осталось, и завершает работу.

Прогоним на слове $abaab$:

$$\begin{aligned} abaab &\to baab && (\text{сработало } a \to \Lambda) \\ baab &\to bab \\ bab &\to bb \\ bb &\to \cdot\, bb && (\text{сработало } \Lambda \to \cdot\, \Lambda) \end{aligned}$$

Результат - $bb$: алгорифм вычеркнул все $a$. Пока в слове есть хотя бы одна $a$, выбирается первое правило (оно стоит выше). Как только $a$ исчезают, первое правило неприменимо, управление доходит до второго - и алгорифм заключительно останавливается.

Связь с машиной Тьюринга и тезис Маркова

Нормальные алгорифмы Маркова эквивалентны по вычислительной мощности машине Тьюринга: любую функцию, вычислимую одной моделью, можно вычислить и другой. А значит, НАМ равномощны и частично рекурсивным функциям, и лямбда-исчислению - все эти формализации «вычислимости» совпали, что и стало одним из аргументов в пользу тезиса Чёрча - Тьюринга.

В отечественной традиции отдельно формулируют принцип нормализации (тезис Маркова): всякий алгоритм в интуитивном смысле эквивалентен некоторому нормальному алгорифму над подходящим алфавитом. Это марковский аналог тезиса Чёрча - Тьюринга, и доказать его строго нельзя по той же причине: «интуитивный алгоритм» - понятие неформальное.

Рассчитать для своей задачи

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

Где это пригождается

Несмотря на абстрактность, модель Маркова - не музейный экспонат:

• Теоретическая информатика. НАМ - удобная модель для доказательств о вычислимости и разрешимости, потому что в ней нет «лишних» сущностей вроде ленты и головки.
• Системы переписывания термов и строк (term/string rewriting) в основаниях функциональных языков и доказательствах теорем растут из той же идеи направленной замены подслов.
• Учебная база. В курсах теории алгоритмов НАМ показывают рядом с машиной Тьюринга, чтобы продемонстрировать: «алгоритм» можно формализовать принципиально разными способами с одинаковым результатом.

Эквивалентность разных формализаций вычислимости видна и на примере примитивно рекурсивных функций - ещё одной модели, задающей класс вычислимых функций совсем иным языком.

Частые ошибки

• Путают порядок «первое правило» и «первое вхождение». Сначала выбирают самое верхнее применимое правило, и только потом - самое левое вхождение его левой части. Не наоборот.
• Забывают, что после обычной подстановки схема просматривается заново с начала. Алгорифм не «идёт по списку дальше» - он всегда возвращается к первому правилу.
• Не ставят точку у заключительного правила - и схема зацикливается там, где должна была остановиться.
• Считают, что неприменимость всех правил это ошибка. Это штатная остановка: слово, к которому ни одно правило не подходит, и есть результат.
• Пишут «алгоритм Маркова» в этой теме. Для модели подстановок принято написание «алгорифм»; «алгоритм Маркова» чаще означает совсем другое - цепи Маркова в теории вероятностей.

FAQ

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

Почему «алгорифм», а не «алгоритм»? Это написание ввёл сам А. А. Марков, опираясь на греческое происхождение слова. Оно закрепилось как термин именно для марковской модели подстановок, чтобы отличать её и не путать, например, с цепями Маркова.

Как нормальный алгорифм останавливается? Двумя способами: либо срабатывает заключительное правило (со стрелкой-точкой), либо к текущему слову неприменимо ни одно правило схемы. В обоих случаях текущее слово объявляется результатом.

Коротко

Нормальный алгорифм Маркова вычисляет, переписывая слово по упорядоченному списку правил подстановки: на каждом шаге берётся первое применимое правило и его самое левое вхождение, а заключительные правила (со стрелкой-точкой) завершают работу. Несмотря на отсутствие памяти и состояний, эта модель равномощна машине Тьюринга, лежит в основе систем переписывания строк и иллюстрирует тезис Маркова о формализации понятия алгоритма.