Математический аппарат инженера

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

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

- 625 -

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

Однако такой путь принципиально не пригоден для решения неограниченной проблемы слов. Поскольку длина дедуктивной цепочки, простирающейся между эквивалентными словами (если такая цепочка существует), может оказаться сколь угодно большой, то не существует никакой возможности указать такое конечное число k, которое гарантирует решение проблемы путем простого перебора. Поэтому для получения желаемых результатов необходимо применять другие идеи, основанные на анализе самого механизма преобразования слов посредством допустимых подстановок.

В некоторых случаях могут быть обнаружены и использованы свойства, остающиеся неизменными для всех слов дедуктивной цепочки (дедуктивные инварианты). Так, в каждой из допустимых подстановок исчисления из (5) левая и правая части содержат одно и то же число вхождений буквы а. Следовательно, в любой дедуктивной цепочке все слова также должны содержать одно и то же число вхождений буквы а. На основе этого дедуктивного инварианта можно установить, какие слова не могут быть эквивалентными (например, слова abacdac и abaadac — не эквивалентны).

Проблема слов в ассоциативном исчислении имеет огромное значение в связи с тем, что к ней сводятся многие геометрические, алгебраические и логические задачи. Так, любую формулу логики высказываний и предикатов можно трактовать как слова в некотором алфавите, содержащем логические символы, высказывания, предикаты и предметные переменные. Процесс эквивалентного преобразования или вывода логического следствия может быть представлен как преобразование слов, причем роль допустимых подстановок играют логические законы или аксиомы. Таким образом, вопрос о выводимости какой-либо формулы становится вопросом существования дедуктивных цепочек, ведущих от слов, представляющих посылки, к словам, представляющим следствие. В ряде интерпретаций ассоциативного исчисления, в частности в теории вывода, используются ориентированные подстановки вида L → M, которые допускают лишь подстановку слева направо (слова L в слово M). Это соответствует лабиринтам, по каждому коридору которого можно двигаться только в одном направлении.

- 626 -

7. Нормальный алгоритм Маркова. Система допустимых подстановок в некотором алфавите, снабженная точным предписанием о порядке и способе их использования, позволяет осуществить детерминированный процесс, который последовательно преобразует некоторое слово в новые слова, эквивалентные исходному. Говорят, что задан алгоритм в алфавите А

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

Важный шаг на пути уточнения понятия алгоритма сделан А.А. Марковым, который дал стандартные раз и навсегда определенные указания о порядке использования подстановок. Определение нормального алгоритма Маркова сводится к следующему.