Нормальные алгорифмы Маркова

Рассмотренный механизм системы неоднородных продукций не является откровением, чем-то уникальным и особенным. Существуют другие подходы, ортогональные рассмотренному, в которых также используется понятие продукции. Поэтому так важно четко определять интерпретации для посылки, заключения и самой связки. Прекрасный пример на эту тему предоставляет модель вычислимости, которая называется «нормальные алгорифмы^[1] Маркова». Нормальные алгорифмы имеют прямое отношение к языку РЕФАЛ — одному из немногих отечественных языков программирования ИИ, описанному в конце главы.

Андрей Андреевич Марков, 1903—1979 — советский математик, сын известного русского математика А. А. Маркова.

Основные труды посвящены теории динамических систем, топологии, топологической алгебре, теории алгоритмов и конструктивной математике.

В 1947 г. доказал неразрешимость проблемы равенства в ассоциативных системах, в 1958 г. — проблемы гомеоморфии в топологии, создал школу конструктивной математики и логики в СССР, является автором понятия нормального алгорифма. Писал стихи:

«Историю делают сильные лица./Они достигают всего, что хотят./Они запрягают в свои колесницы/Богов и ученых, быков и котят.

Бывает, однако, лица с замашками/В помойную яму летят вверх тормашками".

Нормальный алгорифм Маркова работает со словами — конечными последовательностями символов конечного алфавита 2. Нормальный алгорифм над алфавитом I задается списком (последовательностью) Q продукций (или правил) со следующими особенностями:

• • каждая продукция в Q имеет вид, а —> р, где а, р е I* (т.е. правила имеют вид: слово —> слово);
• • некоторые продукции в Q отмечены как заключительные, они имеют вид, а р, где а, р е Е* (т.е. отмечены точкой).

Для данной входной цепочки (входного слова) а нормальный алгорифм Маркова последовательно применяет продукцию из Q в соответствии со следующими указаниями:

• (1) если к цепочке, а применимо больше одной продукции из Q, то применяется всегда самая первая из них по списку из Q;
• (2) если продукция, а —> р применима к а более чем одним способом, то она применяется к самому левому вхождению, а в о;
• (3) процесс останавливается, давая в результате цепочку а, когда применяется заключительная продукция либо когда никакая продукция из (2уже не применима к с.

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

Запись числа состоит из символов 0 и 1. Добавим в алфавит еще две вспомогательные буквы — а и Ь. Алгорифм состоит из восьми правил. Для удобства правила перенумерованы, эти номера не являются частью записи алгорифма:

• 1) «О -> 0″;
• 2) а -> 1 а;
• 3) Оа -> Об;
• 4) 1а->1Ь;
• 5) ()/;—>. 1;
• 6) 1/; —» М);
• 7) Ъ —1;
• 8) -> а.

Пусть теперь дано слово.

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

• 1) 101 «101 (8)
• 2) „101 -> 1"01 (2)
• 3) 1"01->10"1 (1)
• 4) 10"1->101“ (2)
• 5) 101а->1016 (4)
• 6) 1016-> ЮМ) (6)
• 7) ЮМ)-к 110 (5)

Последним применилось пятое правило, оно является заключительным. Процесс закончился, и получен правильный ответ. Следует отметить, что на третьем шаге (1"01 —» Ю"1) правило применяется к «0, а не к 1», в силу указания (1).

Рассмотрим другой пример нормального алгорифма Маркова, состоящего из следующих правил:

• 1) 10->011
• 2) 1->01
• 3) 0->

Пусть дано слово 101.

Рассмотрим протокол работы алгорифма:

• 1) 101->0111 (1)
• 2) 0111 —>111 (2)
• 3) 111->111 (2)
• 4) 111 ->111 (2)

В данном примере алгорифм никогда не завершится, гак как среди правил нет ни одного заключительного, а правило (2) применимо всегда.

Вышеприведенный алгорифм был приведен в качестве примера некорректного алгорифма для решения следующей задачи: требуется преобразовать двоичные числа в «единиричные», т. е. на выходе получить строку из N «палочек», если на входе у нас было N в двоичной системе (например, 101 преобразуется в |||||).

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

• 1) ' 0 -" 0||;
• 2) 1 -> 0|;
• 3) 0->.

Пусть дано слово 101.

Рассмотрим протокол работы алгорифма:

• 1) 101->0|01 (2)
• 2) 101 —"0|01 (2)
• 3) 0|01->00||1 (1)
• 4) 00||1 ->00||0| (2)
• 5) 00||0| -> 00|0||| (1)
• 6) 00|0||| -> ОООЦШ (1)
• 7) 0001->00||||| (3)
• 8) 00|||||->0||||| (3)
• 9) ОНИ I (3)

Больше применимых правил нет, и процесс заканчивается. Как видим, в «поправленном» примере алгоритм завершается и выдает ожидаемый результат. На последних шагах правило применяется именно к первым нулям из-за указания (2) (всегда с начала слова).

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

• [1] Андрей Андреевич Марков (и его ученики) в своих оригинальных работах использовали написание «алгорифм». В соответствии с традицией, в обороте «нормальный алгорифм» мы оставляем букву «ф», хотя в остальных случаях используем слово «алгоритм», как это принято в современном русском языке.