Нормальный алгорифм Маркова
Норма́льный алгори́тм Ма́ркова — один из стандартизованных вариантов представления об алгорифме (алгоритме). Понятие нормального алгоритма введено А. А. Марковым в конце 1940-х годов.
Содержание
Описание
Нормальные алгоритмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах. Определение всякого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (к словам в котором алгоритм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор т. н. формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида 
, где L и D — два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида 
, где L и D — два произвольных слова в алфавите алгоритма. При этом предполагается, что вспомогательные буквы 
и 
не принадлежат алфавиту алгоритма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).
Примером схемы нормального алгоритма в пятибуквенном алфавите | * abc может служить схема
Любой нормальный алгорифм эквивалентен некоторой машине Тьюринга, и наоборот — любая машина Тьюринга эквивалентна некоторому нормальному алгорифму. Вариант тезиса Чёрча — Тьюринга, сформулированный применительно к нормальным алгорифмам, принято называть «принципом нормализации».
Нормальные алгорифмы оказались удобным средством для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгорифма идеи используются в ряде ориентированных на обработку символьной информации языков программирования — например, в языке Рефал.
Примеры
Пример 1
Использование алгоритма Маркова для преобразований над строками:
«Я купил кг Аов в Т М.»
При выполнении алгоритма строка претерпевает следующие изменения:
На этом выполнение алгоритма завершится (так как будет достигнута формула №5, которую мы сделали заключительной).
Пример 2
Этот набор правил делает более интересную вещь. Он преобразует двоичные числа в «единичные», то есть на выходе получается строка из N единичек, если на входе у нас было N в двоичной системе. Например, 101 преобразуется в 5 единиц:
Нормальные алгоритмы Маркова
Определение нормального алгоритма и его выполнение
Шаг работы алгоритма повторяется до тех пор, пока
а при преобразовании слова abbc этот же алгоритм будет неограниченно работать, так как имеет место цикличное повторение данных:
Возможности нормальных алгоритмов и тезис Маркова
Пример 1. Рассмотрим простейшую операцию увеличения десятичного числа на 1. В этом случае почти всегда необходимо увеличить последнюю цифру на 1, а последняя цифра отличается тем, что после нее идет символ «@». Поэтому первыми подстановками должны быть подстановки типа
Но если это цифра 9, то ее нужно заменить 0 и увеличение на 1 перенести в предыдущий разряд. Этому отвечает подстановка
Наконец, если число начинается с 9 и перед этой цифрой нужно поставить 1, то этому будет отвечать подстановка
а если это не так, то в конце работы алгоритма символы @ надо стереть, что выполнит подстановка
Таким образом, мы получаем следующий НАМ увеличения десятичного числа на 1:
Приведем работу построенного алгоритма для чисел 79 и 99:
Аналогичным образом разрабатывается нормальный алгоритм Маркова для уменьшения числа на 1 (см. упражнение 1.3.1).
Продемонстрируем работу алгоритма для числа 10:
Вместе с тем построение алгоритма в последнем приведенном примере подсказывает следующую методику разработки НАМ :
Нормальные алгоритмы Маркова
Определение нормального алгоритма и его выполнение
Шаг работы алгоритма повторяется до тех пор, пока
а при преобразовании слова abbc этот же алгоритм будет неограниченно работать, так как имеет место цикличное повторение данных:
Возможности нормальных алгоритмов и тезис Маркова
Пример 1. Рассмотрим простейшую операцию увеличения десятичного числа на 1. В этом случае почти всегда необходимо увеличить последнюю цифру на 1, а последняя цифра отличается тем, что после нее идет символ «@». Поэтому первыми подстановками должны быть подстановки типа
Но если это цифра 9, то ее нужно заменить 0 и увеличение на 1 перенести в предыдущий разряд. Этому отвечает подстановка
Наконец, если число начинается с 9 и перед этой цифрой нужно поставить 1, то этому будет отвечать подстановка
а если это не так, то в конце работы алгоритма символы @ надо стереть, что выполнит подстановка
Таким образом, мы получаем следующий НАМ увеличения десятичного числа на 1:
Приведем работу построенного алгоритма для чисел 79 и 99:
Аналогичным образом разрабатывается нормальный алгоритм Маркова для уменьшения числа на 1 (см. упражнение 1.3.1).
Продемонстрируем работу алгоритма для числа 10:
Вместе с тем построение алгоритма в последнем приведенном примере подсказывает следующую методику разработки НАМ :
Нормальный алгоритм Маркова
Норма́льный алгори́тм Ма́ркова — один из стандартизованных вариантов представления об алгорифме (алгоритме). Понятие нормального алгоритма введено А. А. Марковым в конце 1940-х годов.
Содержание
Описание
Нормальные алгоритмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах. Определение всякого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (к словам в котором алгоритм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор т. н. формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида , где L и D — два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида , где L и D — два произвольных слова в алфавите алгоритма. При этом предполагается, что вспомогательные буквы и не принадлежат алфавиту алгоритма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).
Примером схемы нормального алгоритма в пятибуквенном алфавите | * abc может служить схема
Любой нормальный алгорифм эквивалентен некоторой машине Тьюринга, и наоборот — любая машина Тьюринга эквивалентна некоторому нормальному алгорифму. Вариант тезиса Чёрча — Тьюринга, сформулированный применительно к нормальным алгорифмам, принято называть «принципом нормализации».
Нормальные алгорифмы оказались удобным средством для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгорифма идеи используются в ряде ориентированных на обработку символьной информации языков программирования — например, в языке Рефал.
Примеры
Пример 1
Использование алгоритма Маркова для преобразований над строками:
«Я купил кг Аов в Т М.»
При выполнении алгоритма строка претерпевает следующие изменения:
На этом выполнение алгоритма завершится (так как будет достигнута формула №5, которую мы сделали заключительной).
Пример 2
Этот набор правил делает более интересную вещь. Он преобразует двоичные числа в «единичные», то есть на выходе получается строка из N единичек, если на входе у нас было N в двоичной системе. Например, 101 преобразуется в 5 единиц:
Нормальный алгоритм
Норма́льный алгори́тм Ма́ркова (НАМ, также марковский алгоритм) — один из стандартных способов формального определения понятия алгоритма (другой известный способ — машина Тьюринга). Понятие нормального алгорифма введено А. А. Марковым (младшим) в конце 1940-х годов в работах по неразрешимости некоторых проблем теории ассоциативных вычислений. Традиционное написание и произношение слова «алгорифм» в этом термине также восходит к его автору, многие годы читавшему курс математической логики на механико-математическом факультете МГУ.
Нормальный алгорифм описывает метод переписывания строк, похожий по способу задания на формальные грамматики. НАМ является Тьюринг-полным языком, что делает его по выразительной силе эквивалентным машине Тьюринга и, следовательно, современным языкам программирования. На основе НАМ был создан функциональный язык программирования Рефал.
Содержание
Описание
Нормальные алгорифмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах.
Определение всякого нормального алгорифма состоит из двух частей: определения алфавита алгорифма (к словам из символов которого алгорифм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор так называемых формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида 
, где 
и 
— два произвольных слова в алфавите алгорифма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида 
, где и — два произвольных слова в алфавите алгорифма. При этом предполагается, что вспомогательные буквы 
и 
не принадлежат алфавиту алгорифма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).
Примером схемы нормального алгорифма в пятибуквенном алфавите 
может служить схема
Процесс применения нормального алгорифма к произвольному слову 
в алфавите этого алгорифма представляет собой дискретную последовательность элементарных шагов, состоящих в следующем. Пусть 
— слово, полученное на предыдущем шаге работы алгорифма (или исходное слово , если текущий шаг является первым). Если среди формул подстановки нет такой, левая часть которой входила бы в , то работа алгорифма считается завершённой, и результатом этой работы считается слово . Иначе среди формул подстановки, левая часть которых входит в , выбирается самая первая. Если эта формула подстановки имеет вид , то из всех возможных представлений слова в виде 
выбирается такое, при котором 
— самое короткое, после чего работа алгорифма считается завершённой с результатом 
. Если же эта формула подстановки имеет вид , то из всех возможных представлений слова в виде выбирается такое, при котором — самое короткое, после чего слово считается результатом текущего шага, подлежащим дальнейшей переработке на следующем шаге.
Например, в ходе процесса применения алгорифма с указанной выше схемой к слову 
последовательно возникают слова 
, 
, 
, 
, 
, 
, 
, 
, 
, 
и 
, после чего алгорифм завершает работу с результатом 
. Другие примеры смотрите ниже.
Любой нормальный алгорифм эквивалентен некоторой машине Тьюринга, и наоборот — любая машина Тьюринга эквивалентна некоторому нормальному алгорифму. Вариант тезиса Чёрча — Тьюринга, сформулированный применительно к нормальным алгорифмам, принято называть «принципом нормализации».
Нормальные алгорифмы оказались удобным средством для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгорифма идеи используются в ряде ориентированных на обработку символьной информации языков программирования — например, в языке Рефал.
Примеры
Пример 1
Использование алгоритма Маркова для преобразований над строками.
Я купил кг Аов в Т М.
При выполнении алгоритма строка претерпевает следующие изменения:
На этом выполнение алгоритма завершится (так как будет достигнута формула № 5, которую мы сделали заключительной).
Пример 2
Данный алгоритм преобразует двоичные числа в «единичные» (в которых записью целого неотрицательного числа N является строка из N палочек). Например, двоичное число 101 преобразуется в 5 палочек: |||||.
