Нормальный алгоритм
Норма́льный алгори́фм Ма́ркова — один из стандартизованных вариантов представления об алгорифме (алгоритме). Понятие нормального алгорифма введено А. А. Марковым в конце 1940-х годов.
Нормальные алгорифмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах. Определение всякого нормального алгорифма состоит из двух частей: определения алфавита алгорифма (к словам в котором алгорифм будет применяться) и определения его схемы. Схемой нормального алгорифма называется конечный упорядоченный набор т. н. формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида , где и — два произвольных слова в алфавите алгорифма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида , где и — два произвольных слова в алфавите алгорифма. При этом предполагается, что вспомогательные буквы и не принадлежат алфавиту алгорифма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).
Примером схемы нормального алгорифма в пятибуквенном алфавите может служить схема
Процесс применения нормального алгорифма к произвольному слову в алфавите этого алгорифма представляет собой дискретную последовательность элементарных шагов, состоящих в следующем. Пусть — слово, полученное на предыдущем шаге работы алгорифма (или исходное слово , если текущий шаг является первым). Если среди формул подстановки нет такой, левая часть которой входила бы в , то работа алгорифма считается завершённой, и результатом этой работы считается слово . Иначе среди формул подстановки, левая часть которых входит в , выбирается самая верхняя. Если эта формула подстановки имеет вид , то из всех возможных представлений слова в виде выбирается такое, при котором — самое короткое, после чего работа алгорифма считается завершённой с результатом . Если же эта формула подстановки имеет вид , то из всех возможных представлений слова в виде выбирается такое, при котором — самое короткое, после чего слово считается результатом текущего шага, подлежащим дальнейшей переработке на следующем шаге.
Например, в ходе процесса применения алгорифма с указанной выше схемой к слову последовательно возникают слова , , , , , , , , , и , после чего алгорифм завершает работу с результатом . Другие примеры смотрите ниже.
Любой нормальный алгорифм эквивалентен некоторой машине Тьюринга, и наоборот — любая машина Тьюринга эквивалентна некоторому нормальному алгорифму. Вариант тезиса Чёрча — Тьюринга, сформулированный применительно к нормальным алгорифмам, принято называть «принципом нормализации».
Нормальные алгорифмы оказались удобным средством для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгорифма идеи используются в ряде ориентированных на обработку символьной информации языков программирования — например, в языке Рефал.
Примеры
Пример 1
Использование алгорифма Маркова для преобразований над строками:
Правила:
- "А" → "апельсин"
- "кг" → "килограмм"
- "М" → "магазинчике"
- "Т" → "том"
- "магазинчик" →• "ларь" (заметьте, это заключительная формула!)
- "в том ларьке" → "на том рынке"
Исходная строка:
- "Я купил кг Аов в Т М."
При выполнении алгоритма строка претерпевает следующие изменения:
- "Я купил кг апельсинов в Т М."
- "Я купил килограмм апельсинов в Т М."
- "Я купил килограмм апельсинов в Т магазинчике."
- "Я купил килограмм апельсинов в том магазинчике."
- "Я купил килограмм апельсинов в том ларьке."
На этом выполнение алгоритма завершится (так как будет достигнута формула №5, которую мы сделали заключительной).
Пример 2
Этот набор правил делает более интересную вещь. Он преобразует двоичные числа в «единиричные», то есть на выходе получается строка из N единичек, если на входе у нас было N в двоичной системе. Например, 101 преобразуется в 5 единиц:
Правила:
- «|0» → "0||"
- «1» → "0|"
- «0» → ""
Исходная строка:
- «101»
Выполнение:
- «0|01»
- «00||1»
- "00||0|"
- "00|0|||"
- "000|||||"
- "00|||||"
- "0|||||"
- "|||||"
Это заготовка статьи по математике. Помогите Википедии, дополнив её. |