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

В настоящей заметке доказывается, что существует алгоритм, позволяю­ щий по произвольному элементу g е G определить, существует или нет нату­ ральное число jc , такое, что g x е К . Ясно, что этот алгоритм решает и обоб­ щенную проблему слов. Используя этот результат, легко показать, что в классе групп с одним со­ отношением алгоритмически разрешима проблема вхождения в циклическую группу и проблема распознавания нетривиальности пересечения циклических подгрупп. Теорема 1. Пусть G=<t,b0,c0,...;R> - счетно порожденная группа с од­ ним определяющим соотношением, где R - циклически приведено. Если К - подгруппа, порожденная рекурсивным подмножеством L данных образующих группы G, то существует алгоритм, позволяющий по произвольному элементу g e G определить, существует или нет натуральное число х, такое, что g x е К . Доказательство. G = G, * F , где G, - группа с одним определяющим соотношением, порожденная образующими, входящими в R, a F - свободная группа, порожденная остальными образующими. 1. Пусть все образующие группы G, входят в L. Тогда К = F, * G ,, гд свободно порождается частью свободных образующих группы F, F = Fi *Fi , G = К * F2 = G, *F, * F2. Пусть g - произвольный элемент группы G, записан­ ный как слово в ее образующих. Очевидно, для g можно эффективно найти нормальную форму g =qt ...qn относительно разложения G = G, * Fx*F2. Если эта нормальная форма не затрагивает элементов из F2 , то g е К , и вопрос ре­ шен. Пусть g е К и <p(g) = п - длина его нормальной формы g = qt ...q„. Если относительно функции (р элемент g архимедов, т. е. <p(g2) > <p(g), то, очевидно, при всех натуральных х g x t К . Если g неархимедов, то его нормальная форма представляется в виде g = , где для g, имеется одна из трех возможно­ стей: g, е Fu g, е F2, g, eG |. Так как Fx и F2 - свободны, то в первых двух 195