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

где каздый Ь равен i или Z *• Пользуясь леммами 2 и 3 , заметим, что < С « Д С * ; , А, A J ; Г- • ;• < / > . - / f y j 4 ч 4 г г г , U * ,, Уг , «А <АЗУ - < 7 * J - ) ‘ 0 * 1 J ] < A J : г г г / ( А г . , А А ‘/Х^ ~ , Положим с/г Тогда уравнение < С * 2 / ^ ^ М ' К г г г Л У/) Ш примет вид P(ol„,..,oiK) ^ M . Осталось доказать, что уравнение (2) разрешимо тогда и только тогда, когда разрешима система ( / ) , Пусть уравнение (2) разрешимо. Покажем тогда, что если положить О ( Ь;) ■=-О для всех С , то все уравнения си- стемы U ) превратятся или в тождества, или в следствия уравнения (2 ). В самом деле, если среди индексов С 0 1-г,,.., окажется не менее двух единиц или не окажется ни одной единицы, то тогда <•»*«' ' 4 С ) ~ 4 4 4» i s ( V) 1 Оставшиеся 4 производные веса 5 (у которых ровно одна еди­ ница среди индексов L$ ) дают следствие уравне­ ния (2) - это можно проверить непосредственно. Таким образом, из разрешимости (2) следует разрешимость системы ( / ) . Обратное тривиально, так как уравнение (2) входит в систему ( / ) . Итак,, мы построили уравнение С = (&) в группе ( \ ( ey ? f ) „ для которого не существует алгоритма, распознающего его разрешимость. Теперь мы с его помощью построим уравнение в группе F l f o t H ) с таким же свойством. Г 71