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

А.А. Марков разработал строгую теорию определенного класса алгоритмов, которые называются нормальными алгорифмами Маркова. Для них исходными данными и результатами являются высказывания, записанные в виде слов, принадлежащих некоторому алгоритму А.

Если алфавит А входит во множество В, но А¹ В, то говорят, что В – расширение алфавита А.

Пусть RÎ A и существует некоторое PÎ R, в этом случае говорят, что Р – это вхождение подстроки в высказывание R.

Марковская подстановка – это замена первого вхождения подслова Р в слове R на слово Q: (P, Q)=P®Q.

Если PÏ R, то говорят, что Марковская подстановка не применима к слову R. Частными случаями Марковских подстановок являются пустые вхождения:

(, Q), (P,), (,). Здесь пустые слова в скобках эквивалентны Æ.

Пример 1:

Если R=192375923Î A, тогда

(923, 0000)Þ R=1000075923

Пример 2:

Пусть R=слово, тогда

(ра, да)Þ (не применимо)

Пример 3:

R=паровоз

(овоз, _)Þ R=пар_

Пример 4:

R=книга

(,) Þ R=книга

Большинство алгоритмов не являются нормальными алгорифмами. Однако, т. к. нормальные алгорифмы описаны с полной математической строгостью и точностью, то они могут служить средством обоснования математики и использоваться при исследовании алгоритмически неразрешимых проблем на основе гипотезы, называемой принципом нормализации. Он заключается в следующем: каков бы ни был алгоритм, для которого допустимыми исходными данными и соответствующими им результатами являются слова некоторого алфавита А, всегда существует эквивалентный ему нормальный алгоритм.