Нормальные алгоритмы Маркова

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

История

Идея нормальных алгоритмов возникла в контексте развития теории алгоритмов в середине XX века. А. А. Марков (1903—1979) работал в области математической логики, теории множеств и конструктивной математики. В 1951 году он впервые опубликовал работу «Теория алгорифмов», где изложил основы нормальных алгоритмов. Термин «алгорифм» (старое написание слова «алгоритм») Марков использовал сознательно, подчёркивая преемственность с работами аль-Хорезми.

Разработка нормальных алгоритмов была мотивирована стремлением создать интуитивно понятную, но строгую формализацию алгоритмического процесса, которая не требовала бы сложных абстракций, как, например, машина Тьюринга. Марков хотел построить теорию, основанную на простых преобразованиях слов. В 1954 году вышла его монография «Теория алгорифмов», которая стала классической работой в этой области.

В СССР нормальные алгоритмы активно изучались и использовались в математической логике, программировании (например, в системах обработки символьной информации) и в качестве учебного инструмента для демонстрации свойств алгоритмов. В западной науке эта модель менее известна, чем машина Тьюринга, но признаётся как одна из фундаментальных формализаций.

Определение и структура

Нормальный алгоритм Маркова оперирует со словами — конечными последовательностями символов из некоторого конечного алфавита. Алгоритм задаётся схемой — упорядоченным списком правил подстановки (или продукций). Каждое правило имеет вид:

U → V

или

U → · V

где U и V — слова в том же алфавите (возможно, пустые). Правило с точкой (·) называется заключительным.

Процесс выполнения

Выполнение нормального алгоритма над входным словом P происходит следующим образом:

1. Просматривается список правил в порядке их записи (сверху вниз).
2. Для текущего правила проверяется, встречается ли левая часть U в слове P (как подстрока). Поиск ведётся слева направо; выбирается самое первое вхождение U в P.
3. Если U найдено, то выполняется подстановка: это первое вхождение U заменяется на V. Получается новое слово P'.
4. Если правило было обычным (без точки), процесс повторяется с шага 1 (снова с первого правила, но уже для слова P').
5. Если правило было заключительным (с точкой), то алгоритм останавливается, и результатом считается слово P'.
6. Если ни одно правило не применимо (левая часть не найдена), алгоритм также останавливается, и результатом считается текущее слово P.

Таким образом, нормальный алгоритм — это детерминированный процесс, который либо останавливается, выдавая результат, либо зацикливается (бесконечно применяет правила, никогда не доходя до заключительного и не исчерпывая применимых).

Примеры

Пример 1: Удвоение буквы «а»

Алфавит: {a, b}. Правила:

1. a → aa
2. b → b (заключительное, хотя оно не меняет слово, но останавливает процесс)

Вход: ab

• Шаг 1: Применяем правило 1 к первой букве a → aab
• Шаг 2: Снова правило 1 к первой a → aaab
• Шаг 3: Снова правило 1 к первой a → aaaab (и так до бесконечности, если бы не было другого правила).

Однако, если бы правила были расположены иначе, например:

1. b → b (заключительное)
2. a → aa

Вход: ab

• Шаг 1: Правило 1 не применимо (нет b в начале? Нет, b есть, но правило 1 ищет b и находит его. Применяем: ab → ab (замена b на b). Правило заключительное → остановка. Результат: ab. Этот пример иллюстрирует критическую важность порядка правил.

Пример 2: Преобразование двоичных чисел в единичные

Алфавит: {0, 1, |}. Правила:

1. 1 → 0|
2. |0 → 0||
3. 0 → (пустое слово)
4. → · (заключительное правило с пустой левой частью, применяется в конце)

Вход: 101

• Шаг 1: Правило 1: 1 → 0|. Ищем первое 1 — это первый символ. 101 → 0|01.
• Шаг 2: Правило 1: 1 → 0|. Первое 1 теперь на третьей позиции. 0|01 → 0|00|.
• Шаг 3: Правило 2: |0 → 0||. Первое вхождение |0 — на второй-третьей позиции. 0|00| → 00||0|.
• Шаг 4: Правило 2: |0 → 0||. Первое вхождение |0 — на четвёртой-пятой позиции. 00||0| → 00|0|||.
• Шаг 5: Правило 2: |0 → 0||. Первое вхождение |0 — на третьей-четвёртой позиции. 00|0||| → 000|||||.
• Шаг 6: Правило 3: 0 → пусто. Удаляем все нули. 000||||| → |||||.
• Шаг 7: Правило 4: пустая левая часть всегда применима. → · → ||||| (заключительное). Результат: пять палочек, что соответствует числу 5 (101₂ = 5₁₀).

Этот пример демонстрирует, как нормальные алгоритмы могут выполнять арифметические операции.

Свойства и вычислительная мощность

Нормальные алгоритмы Маркова обладают следующими ключевыми свойствами:

• Детерминированность: Каждый шаг однозначно определён входным словом и схемой.
• Массовость: Алгоритм решает класс однотипных задач (например, преобразование любого двоичного числа в единичное).
• Результативность: Если алгоритм останавливается, результат однозначен.

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

Применение

Хотя нормальные алгоритмы Маркова редко используются для практического программирования, они нашли применение в нескольких областях:

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

Связь с другими формализмами

Нормальные алгоритмы Маркова тесно связаны с:

• Машина Тьюринга: Обе модели эквивалентны. Нормальный алгоритм может быть переведён в программу для машины Тьюринга и наоборот.
• Рекурсивные функции: Класс функций, вычислимых нормальными алгоритмами, совпадает с классом частично рекурсивных функций (тезис Чёрча — Тьюринга).
• Системы переписывания термов: Нормальные алгоритмы являются частным случаем систем переписывания строк (string rewriting systems), где правила применяются только к первому вхождению.
• Продукционные системы: Идеи Маркова повлияли на развитие продукционных систем в искусственном интеллекте (например, системы, основанные на правилах «если-то»).

Критика и ограничения

Основные недостатки нормальных алгоритмов как практического инструмента:

• Громоздкость: Даже простые алгоритмы могут требовать большого количества правил и длинных цепочек подстановок.
• Неинтуитивность для сложных задач: Разработка схемы для сложных вычислений (например, умножения многозначных чисел) является трудоёмкой.
• Отсутствие структурного контроля: В отличие от языков программирования, в нормальных алгоритмах нет циклов, ветвлений или процедур в явном виде — всё реализуется через порядок правил и подстановки.

Тем не менее, как теоретическая модель, нормальные алгоритмы остаются важным элементом математической логики и теории алгоритмов.

Источники

1. Марков А. А. Теория алгорифмов. — М.: Наука, 1954. — 376 с.
2. Марков А. А., Нагорный Н. М. Теория алгорифмов. — 2-е изд., перераб. и доп. — М.: Наука, 1984. — 432 с.
3. Мальцев А. И. Алгоритмы и рекурсивные функции. — М.: Наука, 1965. — 392 с.
4. Успенский В. А., Семёнов А. Л. Теория алгоритмов: основные открытия и приложения. — М.: Наука, 1987. — 288 с.
5. Клини С. К. Введение в метаматематику. — М.: Издательство иностранной литературы, 1957. — 526 с.