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

когда уравнение (/(Л,,Лг Л .... , i K) - g ( Л , Аг) удовлетворяется такими Ь- , что все они лежат в /? . Поэтому к этому урав­ нению мы можем применять все рассуждения, проведенные нами для уравнения ( / ) в группе P / / t LF) , заменяя UJ -про­ изводные на £ -производные. Таким образом, это уравнение эквивалентно исходному диофантову уравнению ....... ~ - YH ,, которое можно взять таким, что для него не сущест­ вует алгоритма,, распознавшего его разрешимость (см. [ /] ) .. Отсюда следует, что и для построенного нами уравнения ( 5 ) в группе F / jfg U2) не существует алгоритма, распознаю­ щего его разрешимость. Уравнение с таким же свойством в группе F [ ( Я) при произвольном л 7 . V теперь легко построить по индукции с использованием леммы 6 : если U - д. - такое уравнение в группе F ( , то L u f ' , * , J - / - такое уравнение в группе F . Теорема I доказана. Для доказательства теоремы 2 сначала построим уравнение в свободной нилыютентной группе ступени 3 (достаточно большого ранга), для которого не существует алгоритма,, распознающего разрешимость. Для этого мы будем интерпрети­ ровать в группе р / ^ ( . F ) произвольную систему ^ диофантовых уравнений,, каждое из которых относится к одному ив следующих типов: /. - о V , 1£ i,},* £/Ч 2. oL*-Fcl• *■ oj. С J К i 1 £ i\^K * h Ъ. ol. - ol. * J > i - ‘ J М ч. л. г т 1 £ < £ М , т 6 2 Сначала перенумеруем все уравнения системы следую­ щим образом: уравнения первого типе занумеруем натураль- 175