Структуры данных и модели вычислений
Алгорифмы Маркова
Термин "алгорифм" является устаревшим вариантом современного термина "алгоритм", однако по отношению к алгоритмам Маркова принято использовать авторский вариант.
Информация, обрабатываемая алгорифмом Маркова, представляется словом в некотором фиксированном алфавите .
Алгорифм (программа) представляется последовательностью пар слов в алфавите . Пары, составляющие алгорифм, называются также подстановками и записываются в виде
где , — слова в алфавите , причем может быть пустым (обозначаем ). Программа имеет вид
Некоторые подстановки помечаются восклицательным знаком и называются заключительными.
Функционирование. Во входном слове ищется фрагмент, совпадающий с левой частью первой подстановки. Если фрагмент находится, то самый левый такой фрагмент во входном слове заменяется на ее правую часть, в противном случае рассматривается вторая подстановка из алгорифма и так далее. Вычисления заканчиваются, когда ни одна из левых частей подстановок не является фрагментом обработанного к данному моменту слова или когда выполнена заключительная подстановка. Заметим, что описанный таким образом процесс может оказаться и бесконечным.
Замечание.
Алгорифмы Маркова составляют теоретическую основу системы программирования, использующую язык РЕФАЛ.
Пример.
Алфавит . Здесь запятая не является символом алфавита.
Рассмотрим программу
Убедитесь в том, что она входное слово вида переработает в слово , в котором число символов "1" — такое же, как во входном слове. Можно считать, что программа выполняет сложение натуральных чисел, представленных в унарной системе счисления.
Пример.
Алфавит .
Программа
Рассмотрим протокол вычислений на входном слове . Справа указаны применяемые подстановки.
Если считать, что во входном слове закодирована задача умножения в унарной системе счисления, то в выходном слове получен ответ 6.
Докажите, что программа дает верный ответ при любом корректном входном слове.
