Нормальные Алгоритмы Маркова. Построение алгоритмов из алгоритмов.
    В 1956 году отечественным математиком А.А. Марковым было предложено новое уточнение понятия алгоритма, которое позднее было названо его именем.
    В этом уточнении выделенные нами 7 параметров были определены следующим образом:
    Совокупность исходных данных - слова в алфавите S;
    Совокупность возможных результатов - слова в алфавите W;
    Совокупность возможных промежуточных результатов - слова в алфавите
    Р=SWV, где V - алфавит служебных вспомогательных символов.
    Действия:
    Действия имеют вид либо ???, либо ? ( ?, где ?, ? ?P*, где
    P* - множество слов над алфавитом Р, и называется правилом подстановки. Смысл этого правила состоит в том, что обрабатываемое слово ? просматривается слева направо и ищется вхождение в него слова ?.
    Определение.3.1. Слово ? называется вхождением в слово ?, если существуют такие слова ? и ? над тем же алфавитом, что и ? и ?, для которых верно: ?=???.
    Если вхождение ? в ? найдено, то слово ? заменяется на слово ?.
    Все правила постановки упорядочиваются. Сначала ищется вхождение для первого правила подстановки. Если оно найдено, то происходит подстановка и преобразуемое слово опять просматривается слева направо в поисках вхождения. Если вхождение для первого правила не найдено, то ищется вхождение для второго правила и т.д. Если вхождение найдено для i-го правила подстановки, то происходит подстановка, и просмотр правил начинается с первого, а слово просматривается сначала и слева направо.
    Вся совокупность правил подстановки называется схемой алгоритма.
    Правило начала - просмотр правил всегда начинается с первого.
    Правило окончания - выполнение алгоритма заканчивается, если:
    было применено правило подстановки вида ? ( ?,
    не применимо ни одно правило подстановки из схемы алгоритма.
    7. Правило размещения результата - слово, полученное после окончания выполнения алгоритма.
    Рассмотрим пример 1 из лекции 2:
    построить алгоритм для вычисления
    U(n)=n+1;
    S={0,1,2,3,4,5,6,7,8,9}; S=W; V={*,+}.
    
    Cхема этого НАМ показана на рисунке 3.1.
    
    
    
    
    
    
    
    
    Перегоняем служебный символ * в конец слова n, чтобы отметить последнюю цифру младших разрядов.
    
    
    
    
    
    
    
    
    
    
    
    
    
    Увеличиваем на единицу, начиная с цифр младших разрядов.
     Вводим служебный символ * в слово, чтобы им отметить последнюю цифру в слове.
    Рис.3.1. Схема НАМ для вычисления U1(n)=n+1
    
    Нетрудно сообразить, что сложность этого алгоритма, выраженная в количестве выполненных правил подстановки, будет равна:
    (k+1)+(l+1),
    где k - количество цифр в n, l - количество 9, которые были увеличены на 1.
    Но в любом случае сложность НАМ для U1(n) больше сложности Машины Тьюринга для этой же функции, которая равнялась k+1.
    Обратите внимание, что у НАМ порядок следования правил подстановки в схеме алгоритма существенно влияет на результат, в то время как для МТ он не существеннен.
    Построим НАМ для примера 2 из лекции 2:
    построить алгоритм для вычисления
    U2((n)1)=(n-1)1
    Итак, S={|}; W=S; V=?, т.е. ............