Уточнение понятия алгоритм Определение 1: Символом будем называть любой печатный знак. Определение 2: Алфавитом называется любое конечное множество символов. Определение 3: Словом назовем конечную последовательность символов из алфавита. Определение 4: Длиной слова называется число символов в слове. Определение 5: Объектом алгоритма называются слова в некотором заданном алфавите. входное слово алгоритм выходное слово

Нормальные алгоритмы Маркова (НАМ) Формулой подстановки (ФП) называется запись вида, где и - слова из некоторого алфавита (возможно и пустые). При этом называется левой частью ФП, а - правой частью. Сама подстановка (как действие) задается ФП и применяется к некоторому слову Р. Суть операции : в слове Р отыскивается часть, совпадающая с левой частью ФП (т.е. ), и она заменяется на правую часть ФП (т.е. на ):

Сделаем некоторые уточнения. 1. Если не входит в Р, то подстановка считается неприменимой к Р. 2. Если входит в Р несколько раз, то, по определению, заменяется только первое вхождение в Р. 3. Если правая часть ФП – пустое слово, то подстановка сводится к вычеркиванию части из Р. 4. Подстановка по формуле - это приписывание слева к слову.

Определение НАМ и правила его выполнения Нормальным алгоритмом Маркова (НАМ) называется конечный упорядоченный набор формул подстановки: k 1 … k k Причем в ФП могут использоваться два вида стрелок: обычная стрелка ( ) и спец. стрелка «с хвостиком» (׀ ). ФП с обычной стрелкой называется обычной формулой, а со стрелкой «с хвостиком» - заключительной формулой. В чем разница между этими формулами?

Р ассмотрим правила выполнения НАМ 1. З адается некоторое входное слово Р. 2. Просматриваются сверху вниз ФП и выбирается первая из тех, левая часть которой входит в Р. К Р применяется подстановка, определяемая этой формулой. Получается новое слово Р. 3. Теперь слово Р берется за исходное и к нему применяется та же самая процедура, т.е. снова сверху вниз просматриваются ФП начиная с первой (это очень важно) и ищется первая формула, применимая к слову Р, применяется соответствующая подстановка и получается новое слово Р. И так далее…

1) Если на очередном шаге была применена обычная ФП ( ), то процесс применения НАМ продолжается. 2) Если же на очередном шаге была применена заключительная ФП ( ׀ ), то после ее применения работа НАМ прекращается. То слово, которое получилось в этот момент, и есть выходное слово, т.е. результат применения НАМ ко входному слову Р.. 3) Если на очередном шаге к текущему слову неприменима ни одна ФП, то и в этом случае работа НАМ прекращается и ответом считается текущее слово. 4) Если НАМ никогда не остановится при применении к заданному входному слову, то говорят, что НАМ неприменим к этому входному слову

Примеры НАМ Пример 1. А={a,b,c}. Требуется вместо Р получить столько палочек, сколько раз буква с входит в Р. Например: abccac ==>. Пример 2. А={a,b,*}. Пусть Р имеет вид *Q, где Q - любое слово из букв а и b. Требуется получить слово Q*, т.е. надо перегнать звездочку в конец входного слова. Например: *abb ==> abb*. Пример 3. А={a,b}. Требуется добавить в конец Р букву а. Например: abb ==> abba. Пример 4. А={a,b}. Требуется перенести первую букву слова Р в конец.

Алгоритмически неразрешимые проблемы Проблема само применимости Введем понятие запись алгоритма (на примере НАМ): Пусть имеется НАМ: … k k Вытягиваем его в одну линию, разделяя соседние правила подстановки символом «;» (считаем, что этот символ не входит в алфавит алгоритма): 1 1 ; 2 2 ; … ; k k Вот такое слово и называется записью нашего НАМ.

Алгоритмы, которые применимы к своей записи, называются само применимыми. Теорема. Не существует алгоритма, который по записи любого алгоритма определял бы, само применим он или нет. Доказательство (от противного): Предположим, что такой алгоритм существует (обозначим его А) и действует он следующим образом: для любого алгоритма Е А( )=С, если Е само применим, А( )=Н, если Е несамо применим Составим следующий алгоритм В: С C Н ׀ Н Этот алгоритм зацикливается, если ему на вход дают слово С, и останавливается, если на входе – слово Н.

Рассмотрим теперь композицию алгоритмов В и А и обозначим ее К: К=В¤А (Напомним, что К(Р)=В(А(Р)) для любого слова Р). А теперь поставим такой вопрос: алгоритм К - само применим или нет? Попытаемся на него ответить: а) Предположим, что К – само применим. Тогда имеем: К( ) = B( A( )) = B(C) - зацикливаемся Следовательно, К несамо применим. Итак, предположение, что К - само применим привело к противоречию, т.е. это предположение ложно. б) Предположим теперь, что К - несамо применим. Тогда имеем: К( ) = B( A( )) = B(H) = H Следовательно, К само применим. Таким образом, и в этом случае мы пришли к противоречию.

1) не существует алгоритма А; 2) не существует алгоритма В; 3) не существует композиции В¤А