Урок 11

Алгорифмы Маркова

Советский математик Андрей Андреевич Марков, который в середине XX века изучал разрешимость некоторых задач алгебры, предложил новую модель вычислений, которую он назвал нормальными алгорифмами.

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

Марков предположил, что любой алгоритм можно записать как НАМ. В отличие от машин Тьюринга и Поста НАМ — это "чистый” алгоритм, который не связан ни с каким "аппаратным обеспечением” (лентой, кареткой и т.п.). НАМ преобразует одно слово (цепочку символов некоторого алфавита) в другое и задается алфавитом и системой подстановок. Заметьте, что в жизни мы нередко применяем такие замены. Например, при умножении в столбик мы не вычисляем каждый раз произведение 7 × 8, а просто помним, что оно равно 56.

Пусть алфавит НАМ — это русские буквы, и задана система подстановок
а → н
ух → ло
м → с

Применим эту систему подстановок к начальному слову "муха”. Подстановки нужно просматривать по порядку, начиная с первой. Первая подстановка означает "если в слове есть буквы а, заменить пер-
вую букву а на букву н”. В слове муха есть буква "а”, поэтому заменяем ее на "н”. Получается "мухн”. Начинаем просмотр подстановок сначала. Букв "а” больше нет, поэтому переходим ко второй под-
становке. Сочетание "ух” есть в слове "мухн”, поэтому вторая подстановка срабатывает, и мы заменяем "ух” на "ло”: получается "млон”. Теперь ни первая, ни вторая подстановки не применимы, а использование третьей дает в результате слово "слон”. Больше ни одну подстановку сделать нельзя, и НАМ заканчивает работу. Таким образом, приведенная система подстановок преобразует слово "муха” в слово "слон”.

При поиске образца рабочая цепочка символов просматривается сначала. Если в строке словообразец встречается несколько раз, то за один шаг заменяется только первое из них. Так как на следующем шаге просмотр опять начинается с начала цепочки, после первой выполненной замены может "сработать” совсем другая подстановка. В записи подстановок слово-образец может быть пустым, в этом случае слово-замена приписывается в начало рабочей строки: → 0. Такая подстановка всегда должна быть последней в списке, иначе программа зациклится: в начало слова будут постоянно дописываться все новые и новые нули.

Если после слова-замены стоит точка, после выполнения такой подстановки работа программы заканчивается.
Например, если применить НАМ
      а → о.
к слову "карова”, то в результате получим "корова”, потому что после первого же действия работа программы закончится, и последняя буква не будет заменена.

Пример:

Построим НАМ для следующей задачи: удалить из строки, состоящей из букв a и b, первый символ.

Например, строка abba должна быть преобразована в bba.

Казалось бы, здесь нужно использовать систему подстановок

a → .
b → .

Однако такой НАМ будет неправильно работать для слов, начинающихся с буквы b, например, для слова bba, в котором будет удалена последняя буква, потому что первая подстановка выполнится раньше,
чем вторая. Перестановка двух строк также не дает решения — теперь алгоритм неправильно работает для слов, начинающихся с буквы a. Чтобы решить эту задачу, в алфавит НАМ добавляют еще один специальный символ, например, символ "*”. Этим символом помечают начало слова, используя подстановку      → *
Полный алгоритм выглядит так:
*a → .
*b → .
→ *

Как показано в теории алгоритмов, любой алгоритм для машин Тьюринга и Поста можно записать как НАМ, и наоборот. Поэтому все три рассмотренных подхода к строгому определению понятия "алгоритм” эквивалентны (равносильны).

Программное обеспечение:

 Алгоритм Маркова программа (К.Поляков)

Вопросы:

1. Что такое нормальный алгорифм Маркова?
2. Зачем используют специальные символы в НАМ?
3. Что означает эквивалентность различных универсальных исполнителей?

Задачи:

1. Что делают следующие НАМ, если применить их к символьной цепочке, состоящей из нулей и единиц:
а) 0 → 00
    1 → 11
б) *0 → 0*
    *1 → 1*
    * → =.
    → *
в) *0 → 00*
    *1 → 11*
    * → .
    → *

Как будет работать каждая из программ при различных начальных состояниях ленты?

2. Напишите НАМ, который "сортирует” цифры двоичного числа так, чтобы сначала стояли все нули, а потом — все единицы

3. Напишите НАМ, который умножает двоичное число на 2, добавляя 0 в конец записи числа

Дополнительный материал:

1. Майер Р.В. Алгоритмы Маркова (komp-model.narod.ru)

Использованная литература:

1. К.Ю. Поляков, Е.А. Еремин "Элементы теории алгоритмов". Журнал "Информатика" №1, 2012 г.