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

' Доказательство теоремы I проводится в пункте 3 с помощью интерпретации произвольного диофантова уравнения в группе • Этот же принципиальный подход использовался и другими авторами (например* в [21),. но наш способ интер­ претации отличается от предыдущих и представляется более простым. Он основан на так называемом свободном дифферен­ циальном исчислении в групповом кольце свободной группы ' (см. [7 ]) и его обобщении,, предложенном автором. Изложению необходимых сведений посвящен пункт 2. С помощью этого метода могут быть интерпретированы также системы диофантовых уравнений (такой подход применялся, например,, в [ 3 ] ,[ 4 ] ) „ что позволяет получить следующий ре­ зультат: ТЕОРЕМА 2. Если в групповом кольце 2 (.F/K) нет делителей нулй, а ранг группы F достаточно велик, то в группах вида F / y „ (/?; при п г й класс уравнений общего вида алго­ ритмически неразрешим. Мы намеренно не уточняем, насколько велик здесь должен быть ранг группы F , поскольку это зависит от минимально возможного числа уравнений в алгоритмически неразрешимой диофантовой системе.. Попутно нами построено уравнение в свободной нильпотент- ной группе ступени 3 большого ранга, для которого не сущест­ вует. алгоритма, распознающего его разрешимость. В пункте 4 изучается проблема подстановки в группах вида Р / Y„[R) . Устанавливаются следующие факты: ТЕОРЕМА 3 . I ) В свободных нилыютентных группах ступени И > 5 ранга с/ "? 3 проблема подстановки неразрешима. 2) В группах вида F / f a t F ” ) г , то есть в свободных группах многообразий г1 произ­ вольного ранга, проблема подстановки неразрешима (здеоь 71 „ - многообразие всех нильпотентных групп ступени П , a 3 m - MH0r00rtPa3Be всех групп экспоненты т ). 165