ОБЩЕЛОГИЧЕСКОЕ ЗНАЧЕНИЕ КАТЕГОРИЙ РАВЕНСТВА И АССОЦИАТИВНОСТИ  

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

Ассоциативное исчисление имеет следую&щий вид. Предполагается (конечный) алфавит знаков (букв), из которых строятся слова в этом алфавите. Предполагается, далее, конечный перечень формул подстановок слов в слова, т.е. прави&ла вида PQXR <-> PQ2R> имеющих смысл: в слове PQXR мы имеем право заменить слово Qx словом Q2, а в слове PQ2R слово Q2 - сло&вом Qv Так, если задан алфавит А (например, состоящий из всех строчных букв кириллицы) и некоторый перечень формул под&становок, любая из которых может быть применена к данному слову, если в нем содержится (под)слово, входящее в левую либо правую часть рассматриваемой формулы подстановки, то тем са&мым задано определенное ассоциативное исчисление Uan и на множестве слов в алфавите А определено отношение типа равен&ства (тождества, эквивалентности): два слова S и Г тождественны тогда и только тогда, когда они графически совпадают или одно может быть получено из другого с помощью формул подстано&вок, примененных конечное число раз. Это отношение разбивает все множество слов в алфавите А на классы эквивалентности; эти классы и составляют элементы той полугруппы, которая соответ&ствует данному исчислению Uac\ что касается операции полугруп&пы, то ею является простое приписывание (например, справа) слова к слову.

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

Мы видим, таким образом, к сколь важным вопросам приводит использование свойств отношения равенства вместе с ассоциатив&ной операцией. Но именно это - равенство и ассоциативность - со&ставляло исходный пункт всей теоретической конструкции, возве&денной Германом, а потом и Робертом Грассманом. И когда мы ныне размышляем о проблематике разрешимости-неразрешимо&сти теорий, не худо бы помнить, что многие из них связаны с та&ким первичным отношением, как отношение типа равенства (то&ждество слов, изоморфизм, гомеоморфия и т.п.). Это отношение стало источником многих модельных объектов (выражение А. А. Ляпунова), удобных для исследования вопросов дедуктивной логики и теории алгоритмов, и это несмотря на то, что соответст&вующие алгебраические структуры могут оказаться (как с точки зрения их задания, так и их свойств) достаточно простыми - быть полугруппой.