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

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

Описание

Нормальные алгоритмы вербальны, то есть предназначены для применения к словам в различных алфавитах.

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

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

${\displaystyle \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.}$

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

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

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

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

Примеры

Пример 1

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

Алфавит:

{ а…я, А…Я, «пробел», «точка» }

Правила:

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

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

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

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

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

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

Пример 2

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

Алфавит:

{ 0, 1, | }

Правила:

1. 1 → 0|
2. |0 → 0||
3. 0 → "" (пустая строка)

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

101

Выполнение:

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

См. также

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

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

Языки, основанные на нормальных алгоритмах

• РЕФАЛ
• Thue

Прочие алгоритмы

Ссылки

Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите статью в соответствии с правилами написания статей .