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

УДК 519.4 В. Э.МПИЛЬРАЙН ИГУ ии.и.В.Лоионосова ОБ УРАВНЕНИЯХ В ГРУППАХ ШДА F / ^ n (R.) I* Введение Назовем класс уравнений алгоритмически неразрешимым в данной группе G , если не существует алгоритма, определя­ ющего, имеет ли произвольное уравнение из этого класса ре­ шение в G или нет. Пусть F - - нециклическая свободная группа; -э л ем е н т F „Пусть G - произвольная группа. Уравнения вида W ( t , ..... t n ) ~ ^ „ где ^ б б - фиксированный элемент, a -н еи звестны е, пробе­ гающие группу Q> , будем называть бескоэффициентными. Уравнения вида ^ , ...... § т ) * g , где %т -фиксированные элементы,, будем называть уравнениями общего вида.. Проблему алгоритмической разреши­ мости бескоэффициентных уравнений называют обычно проблемой подстановки (см .[ 2 ] ) . Пусть R о F ; через будем обозначать П -й член нижнего центрального ряда группы R Справедлива следующая ТЕОРЕМА X. Если в групповом кольце Z . ( F / £ i нет делителей нуля, то класс уравнений общего вида в группах: f / (Д ) алгоритмически неразрешим при f l t f и произвольном (не­ единичном) ранге группы р . Попутно нами построено уравнение общего вида в свободной нильлотентной группе ступени 5 ранга 2 , для которого не су­ ществует алгоритма, распознающего его разрешимость (этот результат независимо, но несколько ранее был получен Н.Н.Ре - пиным в f 4 ] ) . 164