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

Понятие "нормальный алгоритм" ввел в 1947 г. советский ученый А.А. Марков в качестве одного из уточнений представления об алгоритме. Он положил, что нормальный алгоритм, являясь алгоритмом в некотором алфавите V_T, порождает в нем некоторый детерминированный процесс переработки только одного слова Р_о и только в одном алфавите.

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

Нормальный алгоритм Маркова есть указание использовать упорядоченный список правил подстановки:

_i  _i,

где _i и _i — слова в алфавите V_T.

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

Р_о P₁ P₂ ... P_i ... Q.

Для организации последовательного использования правил вывода заключительного слова все они должны быть индексированы

i  [1, 2, 3...].

Если Р_i - цепочка подслов (₁₂) в алфавите V_т (₁ и ₂ слова, возможно, пустые в алфавите V_T) и среди множества правил есть подмножество {_i}, то выбрать правило, имеющее наименьший номер и выполнить подстановку в слово (₁₂)  (₁_i ₂).

Суть упорядоченного использования правил состоит в том, что каждое переработанное слово вновь поступает в "начало" работы алгоритма и вновь проверяется на подстановку правил в соответствии с протоколом.

. Среди множества правил подстановки есть простые правила, которые обозначают так: ₁  ₁ и заключительные: _i    _i .

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

Процесс может оборваться самостоятельно на некотором слове, в которое не входит ни одна из левых частей правил. Так формируется "тупик".

Для того, чтобы построить модель нормального алгоритма, необходимо в соответствии с правилами подстановки найти множество распознавателей вхождения слов _i в слово P_i и множество операторов подстановки слова _i в слово P_{i+1 i}.

На граф-схеме алгоритма (см. рис.5.19) следует выделить два типа вершин:

• распознаватели вхождения - PB_i ;

• операторы подстановки - ОП_i.

Распознаватели вхождения соединяются последовательно в соответствии с заданной нумерацией правил. Второй выход распознавателя вхождения при обнаружении _i в слове Р_i передает информацию о слове P_i в оператор подстановки — ОП_i, где выполняется соответствующая замена слова  на слово , т.е. ₁  ₂  ₁  ₂ .

Выход оператора подстановки направляет преобразованное слово в начало алгоритма, если применена простая подстановка, и

в конец алгоритма, если применена заключительная подстановка.

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

М₁:= базовая функция С_n(х)=0 в десятичной системе счисления.

Пусть х =’ # XXX ... #.’ число в десятичной системе счисления, а X – цифра. Алфавит V_t содержит три символа v_t = {X, #, (},

Протокол.

1) # X  ( X;

2) (X  0 ( ;

3) ( #   #..

Пусть x = 289. Тогда #289# #(289# #0(89# #00(9# #000(# #000#.

На рис. 5.20 приведена блок-схема этого алгоритма.

М₂:= базовая функции (х) в десятичной системе счисления.

(х)= # XXX ... # =0.

Пусть х =’ # XXX ... #.’ число в десятичной системе счисления, а X – цифра. .

Алфавит содержит четыре символа V_t={X, #, (, )}.

Протокол.

1. #X(X; 3) (#)#; 5) X)  (X+1);

2. (XX(; 4) 9) )0; 6) #)1.

Пусть x=0.

Тогда #0# #(0# #0(#  #0)#  #1#.

Пусть x=289.

Тогда #289# #(289# #2(89# #28(9# #289(# #289)# #28)0# #290#.

Пусть x=999.

Тогда #999# #(999# #9(99# #99(9# #999(##999)# #99)0# #9)00# #)000# #1000#. На рис. 5.21 приведена блок-схема этого алгоритма.

М₃:= преобразование цифры в унарный код.

Если Р_о = # X₁Х₂Х₃ ...#, то Q = # |^x1#|^x2#|^x3# ... .

Алфавит V_t для преобразования цифры в код содержит символы V_Ò = {X, #, /, (}.

Протокол.

1. # X (X; 3) ( 0  # ; 5) |X |(X;

2. (X (X-1 |; 4) #||#; 6) |# |.

Пусть x=234.

Тогда # 234# (234# (1 | 34# (0 || 34# # || 34# #|| (34# # || (2 | 4# # || ( 1 || 4# # || ( 0 ||| 4# # ||#||| (4# # || # |||# (3 |# # ||# |||# ( 2 || # # || # ||| ( 1 |||# # || # ||| ( 0 ||||# || # ||| # ||||#  || # ||| # |#|||#  || # ||| # ||#||# || # ||| # |||#|# || # ||| # ||||# .

На рис. 5.22 приведена блок-схема этого алгоритма.

М₄:= вычисление суммы двух чисел в унарном коде,

т.е. f (х; у) = | ^{x + y}.

Если Р_о =#|^x+|^y#, то Q =# |^{x + y}#.

Алфавит для М₃ есть V_t = { |, +, #, (}.

Протокол.

1) #|  (| ;

2) (|  |( ;

3) (+  |( ;

3. |(#  •# .

Пусть х=2, у=3. Тогда

Р_о =.# ||+||| #  #(||+|||# # |(|+|||# # ||(+|||##|||(|||# # ||||(|| # # ||||| (|##||||||(##|||||# =Q.

На рис. 5.23 приведена блок-схема этого алгоритма.

М₅:= вычисление произведения двух чисел в унарном коде. f(х; у)=|^x* ^y.

. Если Р_о= #|^x_*|^y #, то Q = #|^{x y} #.

Алфавит содержит символы V_т ={| ; *, #, (, )}.

Протокол.

1) | | (|; 4) )( ( ); 7) ( ) );

2) |# (#; 5) )| |); 8) ) |;

3) |( (|); 6) (| (; 9) |#  •|#.

Вычисление произведения двух чисел х = 3 и у = 2 имеет вид:

#|||_*||#  #|||(_*|#  #||(|)_*|#  #|(|)|)_*|#  #(|)|)|)_*|#  #()|)|)_*|#  #)|)|)_*|#  #|))|)_*|#  #|)|))_*|#  #||)))_*|#  #||)))(# #||))()#  #||)())#  #||()))# #|(|))))#  #(|)|))))#  #()|))))# #)|))))#  #|)))))#  #||))))#  #|||)))#  #||||))#  #|||||)#  #||||||# .

Анализ трех типов моделей показал, что основные свойства дискретности, детерминизма, массовости и результативности остаются неизменными для различных способов описания. Различия наблюдаются лишь в использовании алгоритмических объектов.

Если для рекурсивных функций объектами являются числовые функции, а процесс вычисления задан операторами суперпозиции, рекурсии и минимизации, то для машин Тьюринга такими объектами являются символы алфавитов внешней и внутренней памяти, а процесс вычисления задан функциями выхода, перехода и перемещения. Для нормального алгоритма Маркова алгоритмическими объектами являются слова, а процесс вычисления задан правилами подстановки, изменяющими состав и структуру исходного слова до искомого результата.

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

Все модели обеспечивают способ получения ее значений. Но процесс вычисления может быть определен для для всего множества значений независимых переменных аргумента. Особо при использовании оператора минимизации.

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

Если частично вычислимая функция определена на множестве целых положительных чисел и принимает значение на том же множестве, то ее называют частично рекурсивной функцией. Функцию, определенную на всем множестве целых положительных чисел и принимающую значение на том же множестве, называют общерекурсивной функцией.

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

Распространена гипотеза, известная под названием тезиса Черча, о том, что всякая функция, вычислимая некоторым алгоритмом, есть частично рекурсивная функция; и наоборот, всякая частично рекурсивная функция вычислима некоторым алгоритмом.