Нормальный алгорифм

Материал из Википедии — свободной энциклопедии

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

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

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

$\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'$ в виде $R L S$ выбирается такое, при котором $R$ — самое короткое, после чего работа алгорифма считается завершённой с результатом $R D S$ . Если же эта формула подстановки имеет вид $L\to D$ , то из всех возможных представлений слова $V'$ в виде $R L S$ выбирается такое, при котором $R$ — самое короткое, после чего слово $R D S$ считается результатом текущего шага, подлежащим дальнейшей переработке на следующем шаге.

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

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

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

[править] Примеры

[править] Пример 1

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

Правила:

"А" → "апельсин"
"кг" → "килограмм"
"М" → "магазинчике"
"Т" → "том"
"магазинчи" →• "ларь" (заметьте, это заключительная формула!)
"в том ларьке" → "на том рынке"

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

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

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

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

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

[править] Пример 2

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

Правила: