Алгоритмические проблемы теории групп и полугрупп. 1994 г.

удовлетворяющий равенствам ^9). Кроме того, по лемме 3 У можно взять равным Д г * ‘ 4 ^ в , , \ в гч ) , . (В) Выдернем теперь в ( 8 ) э-ю нить. Получим: ‘'~А = =г; ( 10 ) Исходя из рассухденкИ, приведенных в (А ), существует ■ *“ д \ 2 Д б , \ б ^ , удовлетворяющий ( 10 ) . Пусть теперь ^ * - х . у . Тогда 2 * принадлежит Б - . х ч 6 , 4 в * (Ч Ч ))'А= ( 6 м ци /- Ч с Ч » и , - ( Ч 0 - ’ |\ч 1 °г ) у'', ( е ч , ^ г ) ХУ Й и «ч\ ^ ) 5 ’ Л- '^ ч ) ° Г ) ■>(т.-=4|« ) хаки.! образом, удовлетворяет ( 8 ) и имеет требуемый вид. Лемма докавана. 0ПРДЩ1ЕНИВ 4 . Будем говорить, что в группе б - нераз­ решима проблема сопряженности подгрупп, если не существует алгоритма XX , позволяющего для любых двух ее конечно по - рожденных подгрупп И 4 , Иг установить, сопряжены они в £- или нет. ОПРВДЕЛШИЕ 5 . Частной проблемой сопряженности подгрупп группы (г п ее ¡фиксированной конечно-порожденной подгруппы Но назовем проблему построения алгоритма Х ь . позволяю - щего определить для любой конечно порожденной подгруппы И группы (г , сопряжена ли она с фиксированной подгруппой Ц 1Б0РША 3 . В группе ЗЦ, неразрешима проблема сопря - женности подгрупп. ДОКАЗАТЕЛЬСТВО. содержит в качестве подгруппы прямое произведение .двух свободных групп ранга 2 < 6,4 * ■ ^ 4 <)<5$ч"> • Возьмем в качестве фиксированной подгруппы Н\ , б гм 6 5 , ^ ( 6 Ч , е гм') , . . . Яу\ ( е ч , 6 £-'<')> рассмотренную выше. В £41 доказано, что если в прямом про­ изведении двух свободных групп ранга 2 разрешима частная проблема оопряженности подгрупп, то разрешима л частная проблема вхождения. Следовательно, для того , чтобы опреде­ лить, принадлежит ли произвольное слово 'д/ группы < 6 , -, 6 т. > Х < 6 Ч , б гч > фиксированной подгруппе Н * или .нет, достаточно знать, будут лк сопряжены подгруппы НА и 69