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

для Н0 (лемма 7 ). Теперь допустим, что существует алгоритм, позволяющий для подмножества 5 Т с р и любой конечно лог... генной подгруппы Н свободной группы F построить ОС - изолятор 7# (Н ) Покажем, что в этом случае Я рекурсивно. Действитель­ но, возьмем произвольное простое число р и- любое слово ureFt и г f f , не являющееся истинной степенью ни одного v e F , и рассмотрим подгруппу Н -< и г/1> . По предположению можно эффективно построить 9 ^ (Н ) , а следовательно, можно выяс­ нить, принадлежит или нет и г подгруппе J j.fc u r /1* ) , Т^м самым эффективно выясняется, принадлежит ли р , множеству 7L Отсюда следует, что Я рекурсивно [ 6 ] СЛЕДСТВИЕ. Если 3[ не рекурсивно, то не существует ал­ горитма, позволяющего для любой конечно порожденной подгруппы Н свободной группы F построить Я - изолятор. Список использованной литературы 1. Конторович П.Г. Группы о базисом расщепления, П /А 1 атем .со. 1946. Выл.19. С.283 - 308. 2. Конторович П.Г.,Группы с оазисом расщепления, Ш//М атем.сб. 1948. Выл.22. С.79 - 100. 3 . Конторович П Л . Группы с базисом расщепления, I //М атем.сб. • 1950. Вып.26. С. a i l - 320. 4. Т. Р Мс Ъоппиа/г. R o o t- c lo u u ir t in f r e t grt> u /is// J. XoTLcLon . m a te . See. (2). f (19 70). C. /91-/92. 5 . Магнус В ., Kappao А ., Солитвр Д. Комбинаторная теория групп. М.: Наука, 1974. ^ 6 . Мальцев А.И. Алгоритмы и рекурсивные функции, м .: Наука,1966 13