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

Норма́льный алгори́тм Ма́ркова — один из стандартизованных вариантов представления об алгорифме (алгоритме). Понятие нормального алгоритма введено А. А. Марковым в конце 1940-х годов.

Описание

Нормальные алгоритмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах. Определение всякого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (к словам в котором алгоритм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор т. н. формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида $L\to D$, где L и D — два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида $L\to\cdot D$, где L и D — два произвольных слова в алфавите алгоритма. При этом предполагается, что вспомогательные буквы $\to$ и $\to\cdot$ не принадлежат алфавиту алгоритма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).

Примером схемы нормального алгоритма в пятибуквенном алфавите | * abc может служить схема

$\left\{\begin{matrix} |b&\to& ba|\\ ab&\to& ba\\ b&\to&\\ {*}|&\to& b*& \\ {*}&\to& c& \\ |c&\to& c\\ ac&\to& c|\\ c&\to\cdot\end{matrix}\right.$

Процесс применения нормального алгоритма к произвольному слову V в алфавите этого алгорифма представляет собой дискретную последовательность элементарных шагов, состоящих в следующем. Пусть V' — слово, полученное на предыдущем шаге работы алгорифма (или исходное слово V, если текущий шаг является первым). Если среди формул подстановки нет такой, левая часть которой входила бы в V', то работа алгоритма считается завершённой, и результатом этой работы считается слово V'. Иначе среди формул подстановки, левая часть которых входит в V', выбирается самая верхняя. Если эта формула подстановки имеет вид $L\to\cdot D$, то из всех возможных представлений слова V' в виде RLS выбирается такое, при котором R — самое короткое, после чего работа алгоритма считается завершённой с результатом RDS. Если же эта формула подстановки имеет вид $L\to D$, то из всех возможных представлений слова V' в виде RLS выбирается такое, при котором R — самое короткое, после чего слово RDS считается результатом текущего шага, подлежащим дальнейшей переработке на следующем шаге.

Например, в ходе процесса применения алгорифма с указанной выше схемой к слову | * | | последовательно возникают слова | b * | , ba | * | , a | * | , a | b * , aba | * , baa | * , aa | * , aa | c, aac, ac | и c | | , после чего алгорифм завершает работу с результатом | | . Другие примеры смотрите ниже.

Любой нормальный алгорифм эквивалентен некоторой машине Тьюринга, и наоборот — любая машина Тьюринга эквивалентна некоторому нормальному алгорифму. Вариант тезиса Чёрча — Тьюринга, сформулированный применительно к нормальным алгорифмам, принято называть «принципом нормализации».

Нормальные алгорифмы оказались удобным средством для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгорифма идеи используются в ряде ориентированных на обработку символьной информации языков программирования — например, в языке Рефал.

Примеры

Пример 1

Использование алгоритма Маркова для преобразований над строками:

Правила:

1. "А" → "апельсин"
2. "кг" → "килограмм"
3. "М" → "магазинчике"
4. "Т" → "том"
5. "магазинчике" → ·"ларьке" (заметьте, это заключительная формула!)
6. "в том ларьке" → "на том рынке"

Исходная строка:

"Я купил кг Аов в Т М."

При выполнении алгоритма строка претерпевает следующие изменения:

1. "Я купил кг апельсинов в Т М."
2. "Я купил килограмм апельсинов в Т М."
3. "Я купил килограмм апельсинов в Т магазинчике."
4. "Я купил килограмм апельсинов в том магазинчике."
5. "Я купил килограмм апельсинов в том ларьке."

На этом выполнение алгоритма завершится (так как будет достигнута формула №5, которую мы сделали заключительной).

Пример 2

Этот набор правил делает более интересную вещь. Он преобразует двоичные числа в «единичные», то есть на выходе получается строка из N единичек, если на входе у нас было N в двоичной системе. Например, 101 преобразуется в 5 единиц:

Правила:

1. «|0» → "0||"
2. «1» → "0|"
3. «0» → ""

Исходная строка:

«101»

Выполнение:

1. «0|01»
2. «00||1»
3. "00||0|"
4. "00|0|||"
5. "000|||||"
6. "00|||||"
7. "0|||||"
8. "|||||"

См. также

Прочие абстрактные исполнители и формальные системы вычислений

• Машина Тьюринга (автоматное программирование)
• Машина Поста (автоматное программирование)
• Рекурсивная функция (теория вычислимости)
• Лямбда-исчисление (функциональное программирование)
• императивное программирование)