Проблема эквивалентности слов для ассоциативных исчислений

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

Рассмотрим некоторый алфавит А = {а,b,с,...} и множество слов в этом алфавите. Если слово L является частью слова М , то говорят, что слово L входит в слово М. Так, слово аса входит в слово bсаcаb, начиная с буквы а.

Будем рассматривать преобразование одних слов в другие с помощью некоторых допустимых подстановок вида

P — Q или P ®Q, где Р и Q два слова в том же алфавите А.

Применение ориентированной подстановки Р ® Q к слову R возможно в том случае, когда в нем имеется хотя бы одно вхождение левой части Р; оно заключается в замене любого одного такого вхождения соответствую щей правой частью Q.

Применение неориентированной подстановки Р — Q допускает как замену вхождения левой части правой, так и замену вхождения правой части левой.

Будем рассматривать, в основном, неориентированные подстановки.

Пример. Подстановка ас - аса применима к слову bсасаb двумя способами; замена вхождения аса в это слово дает слово bcacab, а замена вхождения ас дает слово bсасааb,

К слову аbсаb эта подстановка не применима.

Определение. Ассоциативным исчислением называется совокупность всех слов в некотором алфавите вместе с какой-нибудь конечной системой допустимых подстановок.

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

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

таких, что каждая пара слов и (i = l,2,...,n-l)

являются смежными, называют дедуктивной цепочкой, ведущей от слова R к слову S.

Если существует дедуктивная цепочка, ведущая от слова R к слову S, то, очевидно, существует и дедуктивная цепочка, ведущая от слова S к слову Д, в этом случае слова R и S называют эквивалентными и обозначают: R ~ S.

Для каждого ассоциативного исчисления возникает своя специальная проблема эквивалентности слов:

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

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

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

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

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

Примеры, построенные А. А. Марковым и П. С. Новиковым для опровержения алгоритмической разрешимости исследуемых проблем были громоздкими и насчитывали сотни допустимых подстановок.

Петербургскому математику Г. С. Цейтину удалось построить пример алгоритмически неразрешимого исчисления, в котором используется лишь семь допустимых подстановок.