АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП 1991 г.

УЖ 5 1 2 .5 3 2 В.Г.ДУРНЕВ Ярославский университет ОБ УРАВНЕНИЯХ С ЭНДОМОРФИЗМАМИ В СВОБОДНЫХ ГРУППАХ И ПОЛУГРУППАХ 1 . В "Коуровской тетради" Г 1 ] Г.С.Маканиным поставлен следую­ щий вопрос 1 0 .2 6 *. " . . . существует ли алгоритм, распознающий раз­ решимость в свободной группе уравнений вида где - автоморфизмы этой группы?" Цель настоящей заметки - показать, что если в сформулированном выше вопросе слово "автоморфизмы" заменить на слово "эндоморфизмы", то ответ на таким образом переформулированный вопрос будет отрица­ тельным. А Именно, имеет место следующая теорема. ТЕОРЕМА» МиЮно указать такие эвдоморфизМы f t , f t свободной группы в такое семейство уравнений ф , t л хг * ..., * / ', i / 1 Хг * , ..., х / г, у , , , а, 6) = 1 с неизвестными .£ / *.» » , #■, , . . » , у ^ и параметром х , что не существует алгоритма, позволяющего для произвольного натурального числа к определить , имеет ли уравнение iv(а fl, ..., •*/', х , г,..., Хн*. У'п>а>&)=1 решение в свободной группе F e . ДОКАЗАТЕЛЬСТВО, Рассмотрим следующие предикаты, являющиеся аналогами п р едм ето в, введенных А.И.Мальцевым в Г 2 3 . Пусть % у f t - следующие эндоморфизмы группы F t : Ъ ( а ) * а , % < S ) : 6 . ' Введем предикат T ( u , v ) T ( a , v ) < * > \ий = a u & v f i = S i r & { 3 z . i ^ ) ( z a S - & f i < • » )*/ . Нетрудно понять, что для произвольных элементов д , h группы F i t F t ^ T t y y h ) тогда и только то гд а, когда существует такое целое число rtty что д : й т , h - 6 Щ . Теперь введем основной для дальнейшего предикат «f ( и , 1 Г,ч: )у по­ лагая S fu .ir , 1Х)<=>{1*,у11 ) ( Т 1 \ ' ,х ) & у ц б :и 6 у & £ z - - y x 'cv 'Jt У \ U U 1 £ M5