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

4 . Проблема подстановки В этом пункте мы с помощью уравнения ( 3 ) из пункта 3 построим бескоэффициентное уравнение вида w( a, (, C, 6 , .... ) - — (все <Х, &, С, 7 - неизвестные) в группе для которого не существует алгоритма, распознающего его разрешимость. Предварительно установим две леммы. ЛЕММА 7 .. Пусть F2 - свободная группа ранга 2 со свободныш порождающими Т , и Х г . Пусть элементы <Я, i группы F? таковы,, что имеет место сравнение Ц л , й , ц Ц 4 , 1 \ , а 1 4 ] я ^ = j " jf 5 (Fi ) ) м я некоторо­ го Ц 7,3 ►Тогда а - УУ (^о с/ ^ ( Р г ) ) ; 4 - У * ' ( (F j) ДОКАЗАТЕЛЬСТВО. Пусть 6 L - T ? x f ( n o S Тогда [ f a a r f [ х г ^ Х г , Т г ^ л ^ ^ А , кСгг / :Г' > ^ о ^ г ] (mo d где Д = оА<[- J ? y . Приравнивая показатели степеней при одинаковых базисных коммутаторах в обеих частях сравнения из условия леммыг получаем систему ^ г Д +• /Vj? (ГД - О 2 « £ А + л/ ( £ / + Л ; - / 7 и г А ± п d f или: j (2 up +nfif+HoifJA - п { о Ц ь и - п у ) Ь - <. ( 9 ) Из последнего равенства сиотемы ( 3 ) следуете cl - i 7 ‘ чд. нц л t 1 ; Д - t i * Отсюда ^ =• О р тогда ^ д =г у , 178