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

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

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

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

Как и машины Тьюринга, нормальные алгоритмы не производят собственно вычислений: они лишь производят преобразования слов, заменяя в них одни буквы другими по предписанным им правилам. В свою очередь, мы предписываем им такие правила, результаты применения которых мы можем интерпретировать как вычисления.

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

Конкатенацией слов