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

l i f t , , . , , % ц ) У , где 4 f ~ k j t / и каждая формула ^t имеет один из следующих видов: X p x j - , х е JCj - Х к , Л ( = х / , Х ( - С к , где Ск - нагуралыше число, такую, что для произволь­ ного натурального числа р имеет место эквивалентность: р е А тогда и только то гд а, когда формула 4 V ( р ) истинна на множест­ ве натуральных чисел. /г) По формуле построим формулу ФА ( X , ) сле­ дующим образом: ^ ^ ........ а , х р ) , где V'f получено из У заменой каждой формулы У/ вида X f * X j - x K на формулы вида хе х} - хк $ (х е , X j, Л к ) , формулы вида Х ( - с к на Х( - а , на и формулы вида х( - X j на нее же. Подходящим образом переименовав переменные и заменив стан­ дартным способом систему равенств в свободно;; полугруппе равно­ сильным ей одним равенством, подучим формулу Ф л ( х ) вида (Ззг„. .. , х„, nn . . . , tm )w ( x , x ; V , Xn't Хл * Цг.-.Ут, Л 1 , а р - гПх, х, ,...,х « ,у * о,, ар такую, что для произвольного натурального числа к имеет м ес- to следующая эквивалентность: кеА «*> тт2 >= Ф 4 (а, ) Взяв в кач естве А рекурсивно перечислимое, но нерекур­ сивное множество, мы получим доказательство теоремы 1 . Для получения доказательства теоремы 2 из доказател ьства теоремы I достаточно ввеоти эндоморфизм Л такой, что f, ( и А - а , , и задать предикаты Т ( х , у ) и $ ( х , у } г ) следующим Образом:' Т (X, у ) <—> d<h -Qixk^Oi * аг у & |Ц = | у| ), u, i/, t a ) ( V y , и ) # V x t h - * й г V % ш - и г 8 г & f t Ш ) * г Л 11/1 =* 1 ^ 1 ) . й.^вязи с рассмотренными в заметке вопросами представляет интерес, на наш взгл я д , Вопрос об алгоритмической разрешимбсти проблемы разрешимости в ТГ^ уравнений в словах и с одним про­ извольна»! фиксированным эндоморфизмом. Список использованной литературы б» 1 1 3 , Коуровская тетр адь. 1 0 -е и з д .,д о п , Новосибирск, 1986. [ 2 3 . Мальцев А.И, 0 свободных разрешимых группах//Докл.АН СССР. I 9 6 0 . T .I 3 0 , №3. С .4 9 5 -4 9 8 . ГЗЗ» Маканин Г .С , Проблема разрешимости уравнений в свобод­ ной подугруппе//Докл. АН СССР, 1 9 7 7 . Т .2 3 3 . f*2. С .2 8 7 -2 9 0 . 143. Маканин Г .С . Проблема разрешимости уравнений в свободной полу группы,^Ьт .сборник. 1 9 7 7 . Т .1 0 3 (1 4 5 ) : 2 ( 6 ) . 0,147-23*3.