§ 12.3. Проблема слов в ассоциативном исчислении

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

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

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

Любая конечная последовательность букв некоторого алфавита называется словом в этом алфавите.

Так, в алфавите из трех букв словами будут последовательности и т. д. Пустое слово, не содержащее ни одной буквы, обозначим символом А.

Рассмотрим два слова: слово L и слово М в некотором алфавите А.

Если слово является частью слова М, то говорят, ЧТО слово L входит в слово М или что имеется вхождение слова L в М. В качестве примера можно привести два слова: .

В общем случае слово L может входить в слово М несколько раз; так слово два раза входит в слово .

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

где — слова в том же алфавите.

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

Подстановка же неприменима к слову , так как в это слово не входят ни слово , ни слово .

К полученным с помощью допустимых подстановок словам можно снова применить допустимые подстановки: так будут получены новые слова и т. д.

Совокупность всех слов в данном алфавите вместе с системой допустимых подстановок называется ассоциативным исчислением. Чтобы задать ассоциативное исчисление, достаточно задать алфавит и систему подстановок.

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

Последовательность слов называется дедуктивной цепочкой, ведущей от слова к слову Q, если каждые из двух рядом стоящих слов этой цепочки являются смежными.

Два слова и Q называются эквивалентными, если существует дедуктивная цепочка, ведущая от слова к слову Q. Отношение эквивалентности обозначается так: . Очевидно, что если , то , так как допустимые подстановки можно применять в обе стороны.

Пример. Зададим следующее ассоциативное исчисление:

Слова и в этом исчислении являются смежными, так как слово может быть преобразовано в слово с помощью применения подстановки .

Слово не имеет смежных слов, так как к нему неприменима ни одна подстановка.

Слово эквивалентно слову , так как существует дедуктивная цепочка смежных слов:

Здесь последовательно применены подстановки.

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

Любые две площадки этого лабиринта, соответствующие смежным словам, соединяются коридором.

Если теперь два слова и Q эквивалентны, то в построенном лабиринте это означает, что площадка, соответствующая слову Q, достижима с площадки, соответствующей слову , т. е. что в этом лабиринте существует путь, ведущий от площадки Р к площадке .

Иногда рассматривается специальный вид ассоциативного исчисления, которое задается алфавитом и системой ориентированных подстановок вида . Стрелка здесь означает, что подстановку разрешается производить лишь слева направо, т. е. заменять вхождение слова Р на слово Q, но не наоборот. Такое ассоциативное исчисление может быть изображено бесконечным лабиринтом, по каждому из коридоров которого разрешается двигаться только в одном направлении.

Ясно, что в таком ассоциативном исчислении из эквивалентности ни в коей мере не следует, что . Мы не будем рассматривать проблемы, связанные с таким особым ассоциативным исчислением.

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

Это та же проблема достижимости, которая была рассмотрена в примере с лабиринтом, однако лабиринт теперь стал бесконечным. Поэтому естественно, что разработанный раньше метод поиска становится теперь непригодным, так как уже нельзя в конечное время обследовать весь бесконечный лабиринт.

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

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

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

Разумеется, описанный здесь алгоритм переборки можно усовершенствовать, избавившись от излишних повторений (т. е. от петель в лабиринте).

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

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

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

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

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

Сами подстановки имеют вид логических правил или тождеств, например (двойное отрицание можно снять) или

правило исключения и т. д.

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

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

Существует и алгоритм распознавания выводимости, то есть может быть проверено, является ли любое утверждение следствием аксиом или нет.

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

Итак, в итоге мы имеем вариант ассоциативного исчисления — логическое исчисление с указанной системой допустимых подстановок. Вопрос о распознавании выводимости становится вопросом существования дедуктивной цепочки, ведущей от слова, изображающего посылку, к слову, изображающему следствие.

Таким образом, и в этом случае мы пришли к проблеме эквивалентности слов в ассоциативном исчислении.

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

В следующем параграфе мы приведем примеры, показывающие, что арифметические процессы также могут трактоваться как ассоциативное исчисление.

Естественно предположить, что построение ассоциативных исчислений может быть универсальным методом для задания детерминированного процесса «переработки» исходных данных, т. е. для задания алгоритма. Но чтобы сделать такое предположение, надо прежде всего уточнить, что мы имеем в виду, говоря об алгоритме в некотором алфавите.