Р — Q или PQ, где Р и Q

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

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

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

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

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

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

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

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

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

R ₁, R ₂ … R _n-1, R _n

таких, что каждая пара слов

R _i, и R _n-1 (i = 1, 2,..., n-1) являются смежными, называют дедуктивной цепочкой, ведущей от слова R к слову S.

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

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

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

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

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

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

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

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

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