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

Взяв в кач естве А рекурсивно перечислимое, но нерекурсив­ ное множество, получим доказательство теоремы. В свявй с рассмотренными в статье вопросами представляет интерес, на наш взгл я д , вопроо об алгоритмической разрешимости Проблемы разрешимости в свободной группе уравнений с одним фикси­ рованным эндоморфизмом, 2 . Обозначим через П п , - < в г, ...,ап> свободную полугруппу ран­ га П со свободными образующими а г а п . Хорошо и звестно, что многие алгоритмические проблемы для полугруппы ТТд. разре­ шимы» Так, Г»С.Маканин(1 , 2 1 д оказал, что существует алгоритм, позволяющий по Произвольной системе уравнений в словах- в свобод­ ной полугруппе ТТrt определить, имеет ли она решение. Эго позво­ ляет легко доказать разрешимость проблемы эндоморфной (автоморф- иой) сводимости для наборов элементов полугруппы ТТ^ , т . е . су­ ществует алгоритм, позволяющий для любых двух наборов й <Си , , , , С т> элементов полугруппы (Т« определить, существует ли эндоморфизм (автоморфизм) У полугруппы ТТа такой, что С В То же время о стается открытым вопроо об алгоритмической разрешимости Ироблемы совместности для систем уравнений в сло­ вах и длинах» В статье рассматриваются уравнения в словах и с эндоморфиз­ мами (фиксированными)» Интерес к подобным уравнениям объясняется двумя обстоятельствами, Во-первых, в ряде работ изучались эле­ ментарные теории групп и полугрупп в сигнатурах, включающих в себя фиксированные эндоморфизмы! во-вторых, Г,С, Маканиным в "Кауровской тетради" сформулирован вопрос об алгоритмической , разрешимости проблемы разрешимости в свободной группе уравнений с автоморфизмами. Нашей целью явл яется доказательство следующих двух теорем* ТЕОРИИ 1» Можно у к азать такие эндоморфизмы V/ и Уг п о - лугрупйы ТТа и такое уравнение вида w ( x , x , , . у TJ TZ • ) у J -1 , * ■ , S f i "г, У/, ■■■, у.-п , Or, Ог) ~ * v ( s , X .. г * г Ъ •у 'til , ^ 1 , ■, , { / т , О ,, а г \ с неизвестными S r , , существует алгоритма, позволяющего для произвольного натурально­ го числа £ определить, имеет ли уравнение . - , S n , S r , У/, •• , &г, 1 =