Каталог статей /

Нормальный алгоритм

Нормальный алгоритм · Описание · Примеры · Близкие статьи · Официальный сайт ·


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

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

  • Russian to English Russian to German Russian to French Russian to Spanish Russian to Italian Russian to Japanese

Информация на сайте из открытых источников. Основа ВикипедиЯ. | Пожалуйста, внимательно прочитайте эту страницу!