Машина Маркова

Машина Маркова

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


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

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

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



Big image