Схема нормального алгоритма

Схема нормального алгоритма — это формальное описание последовательности подстановок, задающих один из классов алгоритмов, называемых нормальными алгоритмами (или алгоритмами Маркова). Нормальный алгоритм представляет собой детерминированную вычислительную модель, оперирующую строками символов (словами) в некотором алфавите. Схема алгоритма является его неотъемлемой частью, определяющей правила преобразования исходного слова в результирующее.

Определение и основные понятия

Нормальный алгоритм был предложен советским математиком Андреем Андреевичем Марковым (младшим) в 1951 году как уточнение интуитивного понятия алгоритма. Схема нормального алгоритма — это конечный упорядоченный список формул подстановки. Каждая формула подстановки имеет вид u → v или u → · v, где u и v — слова (возможно, пустые) в некотором алфавите A. Символ «→» обозначает простую подстановку, а «→·» — заключительную подстановку.

Алфавит A — это конечное множество символов (букв), из которых строятся слова. Словом в алфавите A называется любая конечная последовательность символов из A. Пустое слово (обозначаемое, например, как Λ) также допускается.

Принцип работы нормального алгоритма

Работа нормального алгоритма над исходным словом P заключается в последовательном применении формул подстановки из схемы. Процесс выполнения алгоритма строго детерминирован и состоит из следующих шагов:

1. Поиск первой применимой подстановки. Алгоритм просматривает список формул подстановки сверху вниз. Для каждой формулы u → v (или u → · v) проверяется, входит ли слово u (левая часть) в текущее рабочее слово P. Если вхождение найдено, то выбирается самое левое вхождение u в P.
2. Выполнение подстановки. Если найдена подстановка u → v, то в слове P самое левое вхождение u заменяется на слово v. Полученное слово становится новым текущим словом P. Алгоритм переходит к шагу 1, начиная просмотр схемы с первой формулы.
3. Заключительная подстановка. Если найдена подстановка u → · v, то выполняется аналогичная замена, после чего работа алгоритма немедленно прекращается. Полученное слово считается результатом.
4. Остановка. Если ни одна из левых частей формул подстановки не входит в текущее слово P, алгоритм останавливается. Результатом считается текущее слово P.

Формальное определение схемы

Схема нормального алгоритма S в алфавите A — это конечная последовательность пар (u_i, v_i, ε_i), где:

• u_i и v_i — слова в алфавите A (возможно, пустые);
• ε_i — признак заключительной подстановки (ε_i = 0 для простой, ε_i = 1 для заключительной).

Схема записывается в виде: `` u_1 → v_1 u_2 → v_2 ... u_k → · v_k ... u_n → v_n ` Формулы с →·` могут располагаться в любом месте списка.

Примеры схем нормальных алгоритмов

Пример 1: Удвоение символа «a» в начале слова

Пусть алфавит A = {a, b}. Схема алгоритма, удваивающего каждую букву «a» в начале слова, пока не встретится «b» или конец слова:

1. a → aa
2. b → b
3. Λ → Λ

Работа алгоритма над словом «ab»:

• Исходное слово: ab.
• Шаг 1: Просмотр сверху. Формула 1: a входит в ab (самое левое вхождение). Замена a на aa. Получаем aab.
• Шаг 2: Просмотр сверху. Формула 1: a входит в aab (самое левое вхождение). Замена a на aa. Получаем aaab.
• Шаг 3: Просмотр сверху. Формула 1: a входит в aaab (самое левое вхождение). Замена a на aa. Получаем aaaab.
• Шаг 4: Просмотр сверху. Формула 1: a входит в aaaab (самое левое вхождение). Замена a на aa. Получаем aaaaab.
• Процесс продолжается бесконечно, так как после каждой замены в начале слова снова появляется a. Алгоритм не останавливается (зацикливается). Это демонстрирует, что нормальный алгоритм может не завершаться для некоторых входных данных.

Пример 2: Удаление всех символов «b» из слова

Алфавит A = {a, b}. Схема:

1. b → Λ
2. Λ → Λ

Работа над словом «abba»:

• Исходное слово: abba.
• Шаг 1: Формула 1: b входит в abba (первое вхождение на позиции 2). Замена на пустое слово. Получаем aba.
• Шаг 2: Формула 1: b входит в aba (позиция 2). Замена. Получаем aa.
• Шаг 3: Формула 1: b не входит в aa. Переход к формуле 2: Λ входит в aa (пустое слово входит в любое слово). Замена Λ на Λ не меняет слово. Применяется заключительная подстановка (так как →·). Алгоритм останавливается. Результат: aa.

Пример 3: Вычитание единицы в унарной системе счисления

Алфавит A = {|} (одна палочка). Схема алгоритма, уменьшающего число палочек на 1:

1. || → |
2. | → ·Λ

Работа над словом ||| (число 3):

• Шаг 1: || входит в ||| (самое левое вхождение). Замена на |. Получаем ||.
• Шаг 2: || входит в ||. Замена на |. Получаем |.
• Шаг 3: || не входит в |. Формула 2: | входит в |. Замена на Λ (пустое слово). Применяется заключительная подстановка. Алгоритм останавливается. Результат: Λ (число 0).

Свойства и возможности

Нормальные алгоритмы являются полной по Тьюрингу моделью вычислений. Это означает, что любой алгоритм, который может быть реализован на машине Тьюринга, может быть реализован и в виде нормального алгоритма, и наоборот. Схема нормального алгоритма позволяет реализовывать:

• Арифметические операции: сложение, умножение, вычитание (в унарной или другой системе счисления).
• Логические операции: обработка битовых строк.
• Преобразования строк: поиск, замена, удаление, вставка подстрок.
• Имитацию машин Тьюринга: существует стандартный метод построения нормального алгоритма, моделирующего работу заданной машины Тьюринга.

Применение

Нормальные алгоритмы и их схемы нашли применение в:

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

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

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

Интересные факты

• Андрей Андреевич Марков разработал нормальные алгоритмы в рамках своей работы по конструктивной математике и теории алгоритмов.
• Нормальные алгоритмы являются одним из немногих формальных определений алгоритма, которые были предложены советскими математиками.
• Существует понятие «нормальной формы» для алгоритмов, аналогичное нормальной форме для логических формул.

Источники

• Марков А. А. Теория алгоритмов. — М.: Наука, 1954.
• Мальцев А. И. Алгоритмы и рекурсивные функции. — М.: Наука, 1965.
• Успенский В. А., Семёнов А. Л. Теория алгоритмов: основные открытия и приложения. — М.: Наука, 1987.
• Кнут Д. Э. Искусство программирования. Том 1. Основные алгоритмы. — М.: Вильямс, 2006.