В некоторых случаях могут быть обнаружены и использованы свойства, остающиеся неизменными для всех слов дедуктивной цепочки (дедуктивные инварианты). Так, в каждой из допустимых подстановок исчисления из (5) левая и правая части содержат одно и то же число вхождений буквы а. Следовательно, в любой дедуктивной цепочке все слова также должны содержать одно и то же число вхождений буквы а. На основе этого дедуктивного инварианта можно установить, какие слова не могут быть эквивалентными (например, слова abacdac и abaadac — не эквивалентны).
Проблема слов в ассоциативном исчислении имеет огромное значение в связи с тем, что к ней сводятся многие геометрические, алгебраические и логические задачи. Так, любую формулу логики высказываний и предикатов можно трактовать как слова в некотором алфавите, содержащем логические символы, высказывания, предикаты и предметные переменные. Процесс эквивалентного преобразования или вывода логического следствия может быть представлен как преобразование слов, причем роль допустимых подстановок играют логические законы или аксиомы. Таким образом, вопрос о выводимости какой-либо формулы становится вопросом существования дедуктивных цепочек, ведущих от слов, представляющих посылки, к словам, представляющим следствие. В ряде интерпретаций ассоциативного исчисления, в частности в теории вывода, используются ориентированные подстановки вида L → M, которые допускают лишь подстановку слева направо (слова L в слово M). Это соответствует лабиринтам, по каждому коридору которого можно двигаться только в одном направлении.
- 626 -
7. Нормальный алгоритм Маркова. Система допустимых подстановок в некотором алфавите, снабженная точным предписанием о порядке и способе их использования, позволяет осуществить детерминированный процесс, который последовательно преобразует некоторое слово в новые слова, эквивалентные исходному. Говорят, что задан алгоритм в алфавите А, который применим к слову L и перерабатывает его в слово М, если, отправляясь от L и действуя согласно предписанию, в конце концов получают М, на котором процесс обрывается. Множество слов, к которым применим данный алгоритм, называют его областью применимости. Два алгоритма в некотором алфавите называются эквивалентными, если области их применимости совпадают и результаты переработки или любого слова из общей области применимости также совпадают.
Важный шаг на пути уточнения понятия алгоритма сделан А.А. Марковым, который дал стандартные раз и навсегда определенные указания о порядке использования подстановок. Определение нормального алгоритма Маркова сводится к следующему.
Задается алфавит А и фиксируется в определенном порядке система ориентированных подстановок. Исходя из произвольного слова R в алфавите А, просматриваются подстановки в том порядке, в каком они заданы. Первая встретившаяся подстановка с левой частью входящей в R, используется для преобразования R, в которое вместо первого вхождения ее левой части подставляется ее правая часть, в результате чего получаем новое слово R1. Далее процесс повторяется, исходя из слова R1, R2 и т.д. до тех пор, пока этот процесс не останавливается. Признаками остановки процесса служат два случая: во-первых, когда получается такое слово Rn, что ни одна из левых частей допустимых подстановок в него не входят, и во-вторых, когда при получении Rn приходится применять последнюю подстановку.
Пусть, например, задан алфавит A = {1, +} и система подстановок + → ∧, 1→ 1 (∧ - пустое слово). Слово 111+11+1111+1 этот алгоритм перерабатывает так:
111+11+1111+1
11111+1111+1
111111111+1
1111111111
1111111111
Процесс оканчивается применением заключительной подстановки, которая перерабатывает слово само в себя. Как видим, алгоритм суммирует количество единиц, т.е. осуществляет операцию сложения. Эквивалентный ему алгоритм можно задать с помощью системы подстановок: 1+ → +1; +1→1; 1→1.
- 627 -
В соответствии со смелой гипотезой, основанной на накопленном опыте, предполагается, что любой алгоритм может быть представлен в виде нормального алгоритма Маркова. Иначе говоря, нормальный алгоритм Маркова принимается в качестве стандартной формы любого алгоритма.