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

то с С , , ( с ) - ^ Г с ь ) * ^ ( i i > r ®CV*J; и так далее, Положим d ^ [ ( ; ) - <^, »■ясно,, что тогда си•Бели Л", + / <п £ стема ( ? ) содержит в качестве подсистемы исходную диофан- тову систему ^ >- поэтому из разрешимости ( S ) следует разрешимость 5 , Покажем теперь, что верно и обратное. Пусть система разрешима. Положим d ^ ( i ; ) - 0 при ^ '7 / Тогда,, если среди индексов с., <■$ какие-то два не равны / „ то - J;t i J J ( Е ) - 0 , Если с г - {■$-/ , <•', Z 2 г то, как было показано выше, мы получаем одно из уравнений системы S . Если L, - £*г - i i то опять с С , ( ъ (С ) - ( Е ) ~ О . Если же С, - / и один из в 2 иди с ‘3 равен / , то ура­ внение е/.'Г . (Су) = J является следствием одного из уравнений системы 5 > (это можно проверить непо­ средственно ). Итак,, мы показали, что система ( ? ) , а значат,, и уравне ние ( 7 ) эквивалентны диофантовой системе S • Из сущест­ вования алгоритмически неразрешимой системы такого вида (см .[у ]) следует существование алгоритмически неразрешимого уравнения в группе F I ^ ( F ) Построение уравнения о" таким же свойством в группе р / у ( Q ) проводится полностью аналогично тому, как это делалось выше для уравнения ( 5 ); наконец, пользуясь леммой £ „ можно по индукции построить алгоритмически неразрешимое уравнение в группе F / ((?) при >1 z С , Теорема 2 доказана. 177