Т. А. Сливина математическая логика и теория алгоритмов

Определение. Ассоциативным исчислением называется совокупность всех слов в некотором алфавите вместе с какой-нибудь конечной системой допустимых подстановок.
Дли задания ассоциативного исчисления достаточно указать соответствующие алфавит и систему подстановок.
Если слово R может быть преобразовано в слово S посредством однократного применения допустимой подстановки, то и S может быть преобразовано в R таким же путем. В таком случае R и S называют смежными словами. Последовательность слов
R_l, R₂, ..., R_n-1, R_n
таких, что каждая пара слов R_i и R._i+1 (i = 1,2,...,n-l)
являются смежными, называют дедуктивной цепочкой, ведущей от слова R к слову S.
Если существует дедуктивная цепочка, ведущая от слова R к слову S, то, очевидно, существует и дедуктивная цепочка, ведущая от слова S к слову R, в этом случае слова R и S называют эквивалентными и обозначают: R-S.
Для каждого ассоциативного исчисления возникает своя специальная проблема эквивалентности слов:
Для любых двух слов в данном исчислении требуется узнать, эквивалентны они или нет.
Проблема эквивалентности слов для ассоциативных исчислений была сформулирована в 1911 году. Тогда же был предложен алгоритм для распознания эквивалентности слов в некоторых ассоциативных исчислениях специального вида.
Естественно возникла задача об отыскании такого общего алгоритма, который был бы применим к любому ассоциативному исчислению.
В 1946 и 1947 годах российский математик А. А. Марков и американский математик Э. Пост, независимо один от другого, построили конкретные примеры ассоциативных исчислений, для каждого из которых проблема эквивалентности слов алгоритмически не разрешима, и, следовательно, не существует алгоритма для распознания эквивалентности слов в любом исчислении
В 1955 году российский математик П. С. Новиков доказал алгоритмическую неразрешимость проблемы тождества групп, формально эта проблема представляет собой частный случай проблемы эквивалентности слов в ассоциативном исчислении.
Примеры, построенные А. А. Марковым и П. С. Новиковым для опровержения алгоритмической разрешимости исследуемых проблем были громоздкими и насчитывали сотни допустимых подстановок.
Петербургскому математику Г. С. Цейтину удалось построить пример алгоритмически неразрешимого исчисления, в котором используется лишь семь допустимых подстановок.