Содержание к диссертации
Введение
1. Проблема делимости в полугруппах без циклов . стр. 11
2. Проблема равенства слов в группах без циклов . стр. 40
3. Алгоритмические проблемы в полугруппе и ее минимальном групповом расширении .
4. Один пример группы с неразрешимой проблемой равенства .
Литература стр. 65
- Проблема делимости в полугруппах без циклов
- Проблема равенства слов в группах без циклов
- Алгоритмические проблемы в полугруппе и ее минимальном групповом расширении
- Один пример группы с неразрешимой проблемой равенства
Введение к работе
Проблема распознавания равенства слов (которую часто называют проблемой равенства слов или проблемой тождества) для групп была впервые сформулирована Дэном в І9ІІ г. Им же получено решение этой проблемы для свободных групп и для фундаментальных групп некоторых многообразий [2 i] . Аналогичная проблема для конечно-определенных полугрупп была поставлена в 1914 г. Туэ (.25 J
В 1932 г. В. Магнус [Ч] доказал разрешимость проблемы равенства слов для групп с одним определяющим соотношением. Интерес к такого рода проблемам особенно возрос после того, как в результате уточнения понятия алгоритма, достигнутого в 30-х годах, появилась возможность устанавливать неразрешимость тех или иных алгоритмических проблем. В 1947 г. А.А. Марков [?] и Э. Пост[24J независимо доказали неразрешимость проблемы равенства слов для полугрупп, а в 1952 г. П.С. Новиков [5, 40] построил первый пример группы с неразрешимой проблемой равенства слов. Примеры А.А. Маркова, Э. Поста и П.С. Новикова содержали большое количество определяющих соотношений. Впоследствии были построены более простые примеры полугрупп ( Г.С. Цейтин^ 8J і Г.С. Маканин \5\ » Ю.В. Матиясевич [&] ) и групп ( В.В. Бун [20] , В.В. Борисов [3>] ) с неразрешимой проблемой равенства слов. Построенная в полугруппа содеркит три определяющих соотношения, а группа из [3J - 12 определяющих соотношений.
Ввиду того, что общая проблема равенства слов в полугруппах и группах алгоритмически неразрешима, представляет интерес нахождение таких классов полугрупп и групп, в которых эта проблема может быть решена.
Среди результатов такого рода следует упомянуть кроме вышеуказанного результата В. Магнуса j^4] , также работы В.А. Тарта- ковского У?} , М.Д. Гриндлингера [22] и Р. Линдона [23 J , в которых доказывается разрешимость проблемы равенства слов для групп, в которых различные определяющие слова имеют малую ( по сравнению с их длинами ) обшую часть. Аналогичный результат для полугрупп получен В. Осиповой \j 2] . Доказана также разрешимость проблемы равенства слов в нильпотентных группах &]
СИ. Дцян в работе [і] доказал разрешимость проблемы равенства слов в полугруппах с одним несократимым соотношением, а также с одним соотношением вида Д - { .
В этой же работе СИ. Дцян ввел понятие системы соотношений, не содержащей левых (правых) циклов, которое является обобщением понятия одного несократимого соотношения на системы, состоящие из более чем одного соотношения.
Пусть дана система соотношений где A. О; - непустые слова в алфавите CLH Q2) -^c*m., Пусть слова Д. и О- начинаются с букв &ь и # соответст-венно. Левым графом системы (I) называется граф, содержащий \уь вершин 0L4 &2> -/ ам. и Я* неориентированных ребер (а^ ^ #g ) при е=t. и СС9 в этом определении взять последние буквы слов /\. и В. , то получим определение правого графа системы (I) . Если левый (правый) граф системы (I) не имеет циклов, то мы говорим, что система (I) не имеет левых (соответственно, правых) циклов.
В \j 1 доказано также, что полугруппа, система определяющих соотношений которой не содержит ни левых, ни правых циклов, изоморфно вкладывается в группу. Пусть в последовательности
А*х.-Х,-Хг-»..,-Хд*У (2) - 5 « выделены два элементарных преобразования PRQ*X--»X;„ = PSQ (S) UEVsXj-Xj*, * UDV f4) где с < j . будем говорить, что преобразование (3) происходит правее преобразования (4) , если имеем P^PER» где слово непусто и в последовательности буквы отрезка , выделенного в Х- + » не затрагиваются и переходят по индивидуальности в соответствующие буквы отрезка Е слова Х- , либо имеем V& V $V,i где слово S непусто и в последовательности X*S"PSQ-*..."* Х- ^ U ЕУЛ^ К буквы отрезка S ) выделенного в X * » не затрагиваются и переходят по индивидуальности в соответствующие буквы отрезка, выделенного В X;.
Два преобразования последовательности ( 2) назовем независимыми, если одно из них происходит правее другого.
Если при 1<] преобразование (3) происходит правее преобразования (4) , то мы можем переставить в (1) порядок этих преобразований, сохранив порядок остальных элементарных преобразований. Повторив такую перестановку нужное число раз, мы получим новую последовательность, переводящую X в У > в которой для любых двух независимых преобразований сначала производится то, которое происходит левее. Такие последовательности элементарных преобразований будем называть направленными вправо.
Аналогично определяется понятие последовательности элементарных преобразований, направленной влево.
Пусть полугруппа П задана системой определяющих соотношений.. без левых циклов.
Для любой пары различных букв («, v) алфавита полугруппы | { и любого слова OL Z введем понятие левого разложения слова a Z относительно буквы ь
Определение понятия левого разложения слова olZ относительно буквы I R (cll} і) проведем индукцией по длине слова а 2 . Разложение R.^ia.2^) будет существовать не для всякой пары Если же такое разложение существует, то в общем случае оно должно иметь вид где а.Нг Н^.-НД?', слова Н^г, -.-, Не, называемые левыми компонентами,суть непустые собственные начала определяющих слов, г? называется головкой, С. - правым крылом этого разложения. При этом с головкой R> обязательно связывается некоторое определяющее соотношение, имеющее вид R. = S с точностью до перестановки местами левой и правой части.
Иногда в разложениях звездочки будем опускать. Если разложение существует, то оно определяется однозначно.
Если в левом графе системы определяющих соотношений нет пути, ведущего от буквы OL v. Ь , то будем считать, что левое разложение Ял («.,») не существует. Если такой путь в левом графе есть, то он единственный, так как в левом графе нет циклов. Пусть С -смежная с <Х буква, лежащая на пути, соединяющем а с 6 » и а В -- с D (s) есть соответствующее определяющее соотношение с точностью до перестановки левой и правой части. Тогда положим, по определению,
Для определения Re (л2 с/ рассмотрим максимальное общее начало &F слов <* и oil . Пусть clEzclFEj и olL^clF ?, . Если л р , то положим, по определению, R,(a2,c) - a *ZV (&)
При этом вццеленное вхождение слова a назовем головкой разложения (б) и будем говорить, что с этой головкой связано определяющее соотношение ( 5) .
Пусть непусто. Если с^ пусто, то положим
ЯгЫ2,с)^ aF * (7)
При этом будем говорить, что разложение (7) не имеет головки, а &F есть первая компонента разложения.
Пусть оба слова Р и 7, непусты, т. е.
Так как д(с[7.г)<. д (Ol с) , то по индуктивному предположению определено разложение R*[oL22q)» Если Rm(d2tt 4) не существует, то будем говорить, что и R. (си с.у не существует. Пусть Jp(ci?2 а) существует и имеет вид н„*нг*...* н,**н', где Н, Н2 .... Нк ~ левые компоненты этого разложения, R, - его головка, связанная с некоторым соотношением R.- S » а Z - его правое крыло. Тогда положим, по определению, Rf(aZ,c)^ лР*Ия*Иг*...
Понятие направленной вправо (влево) последовательности преобразований и левого (правого) разложения слова Л относительно буквы fe были введены СИ. Дцяном в работе [2] , в которой был построен некоторый алгоритм Ot , который по слову X и букве 6 в случае, когда д делится слева (справа) на {, , указывает кратчайшую напрвленную вправо (влево) последовательность, переводящую слово Д в слово вида
Для удобства читателя мы приведем определение этого алгоритма.
Алгоритм ОЪ : Пусть полугруппа | 1 задана системой соотношений без левых циклов. Рассмотрим произвольное слово а и букву і .
Если д начинается с буквы ь , то д делится на ь слева.
Если X начинается с буквы <& » отличной от 4 , то п проверим существует ли левое разложение слова Д относительно буквы ь или нет. Если такое разложение не существует, то X не делится на ъ . Если же это разложение существует, то оно имеет вид: , Re(X,t)*H4*Ht*...*HK* R" X.
Если это разложение не имеет головки, то д не делится на ь слева. Пусть /v есть головка разложения КАК (>) и она соответствует определяющему соотношению R." S » тогда слово назовем результатом применения одного шага алгоритма и[ и т.
Проблемы равенства и делимости в полугруппах без левых циклов (правых)циклов были в работе [2] сведены к проблеме остановки алгоритма QL
В 1 настоящей работы с помощью этого алгоритма доказывается разрешимость проблем левой и правой делимости (и проблемы равенства) в полугруппе, система определяющих соотношений которой не содержит ни левых, ни правых циклов. Этот результат изложен в статье pfbl .
Вопрос о разрешимости проблемы делимости и даже проблемы равенства слов для полугрупп, системы определяющих соотношений которых не содержат циклов только с одной стороны, пока является открытым даже для полугрупп с одним определяющим соотношением, несмотря на то, что для групп с одним соотношением разрешимость проблемы равенства слов доказана В. Магнусом еще в 1932 г.. Г.У. Оганесян [-НІ используя результат, содержащийся в 1, доказал разрешимость проблемы делимости для полугрупп с одним определяющим соотношением вида #= а/Ц » где А - произвольное слово.
В 2 доказывается разрешимость проблемы равенства слов для групп, заданных системой определяющих соотношений в положительном алфавите, не содержащей циклов.
В 3 исследуется связь между алгоритмическими проблемами в полугруппе, изоморфно вложимой в группу, и в ее минимальном групповом расширении. Указывается пример полугруппы, для которой проблемы левой и правой делимости, а также проблемы равенства слов разрешимы, в то время как в ее минимальном групповом расширении проблема равенства слов неразрешима.
Содержание 2 и 3 изложено в работах \j Ц] и \J 5J .
В работе \\ 9] СИ. Адян доказал разрешимость проблемы равенства слов в случае, когда все определяющие слова группы имеют вид n г { , где П - достаточно велико, и группа не содержит элементов второго порядка. Возникает естественный вопрос о том, разрешима ли проблема равенства слов при малых значениях ГЬ .
В 4 настоящей работы строится пример группы с неразрешимой проблемой равенства слов, все определяющие соотношения которой имеют вид А ' і Зтот результат имеется в ]ib\ ,
Все понятия и обозначения, не оговоренные особо, понимаются так же, как в \jt 2 J .
Нумерация теорем в работе сплошная, леммы и формулы нумеруются в пределах каждого параграфа. - II -
Проблема делимости в полугруппах без циклов
В самом деле, пусть в некоторой полугруппе с разрешимой проблемой левой делимости нет левых циклов и нам нужно выяснить равны ли в ней слова д и У . Если X не делится слева на слово / , то, очевидно, слово X не может быть равно слову у . Если же А делится на У слева, то найдем слово с такое, что X - / Z . Если в полутруппе выполняется равенство X = У » то слово Z должно быть равным 1 . Так как в полугруппе с непустыми левыми и правыми частями определяющих соотношений никакое непустое слово не равно d , то равенство X - У может иметь место в том и только том случае, когда Z — і
Целью настоящего параграфа является доказательство разрешимости проблем левой и правой делимости (а, следовательно, и проблемы равенства слов) в полугруппах с системой определяющих соотношений, не содержащей ни левых, ни правых циклов. Для доказательства этого утверждения нам понадобятся некоторые леммы. ЛеммаІ. Пусть П ъ лг — а 1= $іУ (ГДеА;Д непустые слова ) - полутруппа, система определяющих соотношений которой не содержит циклов. Полугруппа Г\ изоморфна полугруппе, система определяющих соотношений которой не содержит циклов и состоит только из соотношений, в которых сумма длин определяющих слов равна трем. - 12 Доказательство. Возьмем какое-нибудь определяющее соотношение полугруппы П, : GL\ 0L: ... 0L- = (X: OL-. ... а« и заменим его следующей системой соотношений: a-L аь = х, , ai ah = fr Л = х2 Оіїч = Хг , &з\,5 -2 Жк-2 0-L" Х - &- = - где #;,Ч- - новые буквы. Очевидно, что при такой замене новая полугруппа изоморфна полугруппе Г\4 . Рассмотрим левый и правый граф новой системы определяющих соотношений. При переходе от первоначальной системы определяющих соотношений к новой системе в левом графе ребро, соединяющее CL с GL- , заменяется путем, соединяющим (Х с OL и состоящим из ребер (аІ4, xt) ( ,,xt) (Xl) ») ..! (х«.г, xK.J Очевидно, что левый граф новой системы соотношений циклов не содержит . В правом графе ребро (а- ОЬ ) заменится путем 1(Х с 0Ск)(Х Q-) и, кроме того, появятся новые ребра которые соединяют старые вершины с новыми. Очевидно, что и правый граф новой системы не содержит циклов. Проделаем эту процедуру последовательно для всех соотношений по - ІЗ лутруппы І \л , беря каждый раз новые дополнительные буквы. Таким образом, получится новая система трехбуквенных соотношений, не содержащая циклов. Полученная полугруппа Пг изоморфна полугруппе Гц . Лемма доказана.
Для наших рассмотрений удобно левый и правый графы системы трехбуквенных определяющих соотношений считать ориентированными, причем ребрами левого и правого графов, соответствующими соотношению а,- ёс , считать упорядоченные пары (&, &} и (а, с) . Первую букву ребра будем называть его началом, а вторую - концом. При этом циклами ориентированного графа будем называть циклы соответствующего неориентированного графа. Лемма 2. Пусть в левом графе полугруппы Г12 система определяющих соотношений которой не содержит циклов и состоит из трехбуквенных соотношений вершина ОС является началом двух различных ребер (а, й) и (о-,с) , т. е. система определяющих соотношений содержит два соотношения: a- &d и а се (і) Тогда полугруппа I 1 изоморфно вкладывается в полугруппу П3 » которая получается из полугруппы l\z заменой соотношений (і) на соотношения а.- II , gr с , е-- xd (г) Система определяющих соотношений полутруппы Пз не содержит циклов. Доказательство. Отсутствие циклов в системе определяющих соотношений полугруппы Пз очевидно. Докажем, что f]z изоморфно вкладывается в полугруппу Пз Прежде всего отметим, что соотношение a= ев, которое отсутствует в системе определяющих соотношений полутруппы Па, » вы" - 14 водится в {1 посредством следующего вывода: OL- &CL СРЄОІ- се. Присоединив соотношение CL- СЄ к системе определяющих соотношений полутруппы Пъ , получим полугруппу Пъ » изоморфную 11 . Пусть теперь слова д и У , не содержащие буквы х , равны в П5 . Покажем, что они равны ив Пг . Полугруппы П2 и \ъ изоморфно вкладываются в соответствующие группы \г и Г , получающиеся добавлением отрицательных букв и тривиальных определяющих соотношений (см. [і] , стр. 45) , причем ъ\ъ # равно ь 0L и группа \ъ изоморфна группе Г2 . Заменив в выводе переводящем Л в У в П3 , все вхождения X на ь а , получим вывод в группе I г , переводящий слово X » состоящее из положительных букв, в слово / , также состоящее из положительных букв. Так как jig вкладывается изоморфно в ) , то X равно У ив П2. Лемма 2 доказана. Лемма 3. Если в полутруппе \\z разрешима проблема левой делимости на 01 и в полугруппе Пг разрешима проблема левой делимости, то в \ \2 также разрешима проблема левой делимости. Доказательство.
Проблема равенства слов в группах без циклов
К новой полугруппе снова применим эту операцию и будем производить ее до тех пор, пока не получим полугруппу, удовлетворяющую условию б. Так как число вершин второго яруса конечно, то это обязательно произойдет. Полученная полугруппа и есть П В ней правыми последователями транзитных букв являются буквы второго яруса. На этом первая часть алгоритма заканчивает свою работу. Перейдем к описанию второй части алгоритма. Нам понадобится несколько вспомогательных утверждений. Лемма 8. Если полугруппа удовлетворяет условию I, то из /\В = CD следует, что А сравнимо слева с С Доказательство. Рассмотрим направленную вправо последовательность элементарных преобразований без поворотов Сем. \_2 \ , с. 613), переводящую АВ в CD . Так как вес полугруппы равен нулю, то в этой последовательности сначала производятся все преобразования а = ое слева направо, при этом длина образуемого слова увеличивается, а затем обратные преобразования, уменьшающие длину слова. В максимальном слове вывода есть начало, равное А » и начало, равное С . Очевидно, что они сравнимы.
Итак, вопрос о сравнимости двух букв или решается тривиальным образом, или сводится к сравнимости двух других букв. Так как число пар букв конечно, то после конечного числа таких сведений мы либо получим положительный ответ, либо придем к паре букв, лежащих в разных компонентах левого графа, либо попадем в цикл. Последние два случая означают, что рассматриваемые буквы несравнимы. Доказательство. Пусть Q = « &bGLZ) ..., dK\ Д . = gt» » группа и пусть система определяющих соотношений/Д» = Б-} содержит только положительные буквы и не имеет циклов. Тогда можно рассмотреть полугруппу П с теми же образующими и определяющими соотношениями. Согласно теореме І в полугруппе П разрешимы проблема равенства слов и обе проблемы делимости. Разрешимость проблемы равенства слов достаточно доказать не для группы Pi , а для изоморфной ей группы і , получающейся из і А добавлением соотношений Ль = 6 » которые мы будем называть отрицательными. Замечание I. Везде в дальнейшем если //t - полугруппа, то через І і мы будем обозначать группу с теми же образующими и определяющими соотношениями, а через /і - изоморфную ей группу с добавленными отрицательными соотношениями. СИ. Адян в работе [1J доказал, что полугруппа с системой определяющих соотношений, не содержащей циклов, изоморфно вкладывается в соответствующую группу, т. е. два слова в такой полугруппе равны тогда и только тогда, когда они равны в группе. Оказывается, что для группы ] справедливо аналогичное утверждение:
Если в выводе (4) имеются независимые преобразования, второе из которых производится левее первого, то поменяем их местами. Легко видеть, что после конечного числа таких перестановок можно получить вывод, не содержащий таких пар преобразований. В выводе, переводящем X в dL, производятся нетривиальные преобразования внутри слов Xt и У; и сокращения на границах этих слов. Слова в положительном (отрицательном)алфавите будем в дальнейшем для краткости называть положительными (отрицательными) . Если слово X равно 1, то непременно существует либо слово вида XV- X » равное некоторому положительному слову, либо слово вида X" У- » равное некоторому отрицательному. Слов такого вида конечное число, поэтому для того чтобы решать проблему ра венства слов в группе /л , достаточно уметь решать проблему равенства слов вида ХІУ Кг где Х и Л г - слова в положительном алфавите, а / - слово в отрицательном алфавите, некоторому слову в положительном алфавите. Действительно, если в разложении (7) слова Л нет трех последовательных членов, которые равны какому-нибудь положительному или отрицательному слову, то Л не равно А, если же такие три члена есть, то, заменив их на равное им слово, мы получим разложение Л с меньшим числом членов. После конечного числа таких шагов вопрос о равенстве А и І будет решен.
Нам теперь осталось доказать разрешимость проблемы равенства слов вида Х / Л г положительному слову. Последнее утверждение удобно доказывать для групп, удовлетворяющих некоторым специальным условиям, которые вводятся таким образом, что для любой полугруппы І ц оказывается возможным построить полугруппу Пг » удовлетворяющую этим условиям и такую, что проблемы равенства слов или делимости в І І4 , а также проблема равенства слов в \ разрешимы тогда и только тогда, когда разрешимы соответствующие проблемы в П2 и в 2 .К построению полугруппы Г/г мы сейчас и перейдем.
Алгоритмические проблемы в полугруппе и ее минимальном групповом расширении
В настоящем параграфе рассматривается вопрос о связи между проблемами равенства слов в конечно-определенной полугруппе, которая вложима в группу, и в группе / с теми же образующими и определяющими соотношениями. Оказывается, что даже в случае, когда в полугруппе разрешима не только проблема равенства слов, но и обе проблемы делимости, проблема равенства слов в группе может быть неразрешима. Чтобы доказать разрешимость проблем равенства слов и делимости в полугруппе ["] достаточно показать, что в ил для всякого слова А существует лишь конечное число слов, равных X . Для этого достаточно построить верхнюю границу длин всех слов, равных Л , как функцию от длины Л Из соотношений (3) - (10) видно, что если слова /\ и У равны, то число вхождений букв С)1) к, и S в А равно числу вхождений этих букв в / . Число вхождений букв t и может возрасти только в результате применения преобразований (1) и (2) и, следовательно, ограничено, если ограничено число вхождений букв CL- . Число вхождений букв ОС- может измениться только в результате применения преобразования (4). Итак, чтоб доказать существование верхнейграницы длин всех слов, равных слову А » достаточно показать, что во всех выводах, переводящих слово X в равное ему слово, число преобразований 4) ограничено сверху числом, зависящим от длины слова А Мы будем называть элементарное преобразование U Iе Е- С V - LLci,LFi Iе V преобразованием слева направо, а обратное к нему преобразование - преобразованием справа налево.
Лемма X. Если в кратчайшем выводе, переводящем слово Л в слово У некоторая буква С затрагивается преобразованиями типа (4) , то все эти преобразования являются либо преобразованиями слева направо, либо преобразованиями справа налево.
Доказательство. Пусть слово имеетвзд где Liz не содержит вхождений букв С и с . Мы будем называть канонической формой слова (Л относительно выделенных вхождений букв Сие слово cpi J , которое получается из (X » если при помощи преобразований (2) , (3) , (5),() и (9) переместить сначала букву , а затем букву с как можно дальше вправо. Очевидно, что если V получается из І4 применением одного элементарного преобразования, не являющегося преобразованием ти па (4) , то можно построить каноническую форму j (V) относи тельно тех же вхождений С и с , и существует элементарное преобразование, переводящее . Следовательно, если в выводе, не содержащем преобразований типа (4) , заменить все слова на их канонические формы относительно одних и тех же вхождений букв с. и с » получится вывод, в котором выделенные вхождения букв С и I не затрагиваются никакими преобразованиями. Мы будем называть такой вывод каноническим относительно выделенных вхождений букв Сие.
Рассмотрим теперь кратчайший вывод, переводящий д в У . Предположим, что в нем есть буква С , участвующая в преобразованиях типа (4) слева направо и справа налево. Тогда в этом выводе есть два последовательных преобразования типа (4) , затрагивающих эту букву С и являющихся преобразованиями в противоположных направлениях. Пусть, для определенности, первое из этих преобразований есть преобразование слева направо, а второе -справа налево.
Построим канонический вывод относительно выделенных в (її J вхождений Сие для той части вывода (II) , которая переводит слово Ц в слово V . Так как (j ШУ U иу# V , мы получим вывод, переводящий U. в V , в котором выделенные вхождения с и с не затрагиваются. Из этого следует, что можно построить вывод, переводящий Ал в Ул и вывод, переводя - 56 щии таким образом, что суша длин этих двух выводов будет равна той части вывода (її) , которая переводит U в V .
Если мы докажем, что t - j и что существует вывод, переводящий )\L в /г и имеющий такую же длину, как и построенный нами вывод, переводящий t 46 z в cFt X. , тогда, используя его и вывод, переводящий Л в / , мы сможем построить вывод, переводящий ){ в У , имеющий такую же длину, как и вывод (її) и содержащий поворот, что противоречит предположению о том, что вывод (її) - кратчайший. Итак, рассмотрит-! вывод
Так как буквы kt Г и S участвуют только в коммутациях, то все вставленные буквы t и S и все буквы / $ могут быть вычеркнуты из всех слов, входящих в вывод. Это дает вывод, не содержащий вставок букв k,tfz и С Так как буквы і и 1 не переходят друг через друга ни при каких преобразованиях, вывод может быть преобразован таким образом, чтоб каждая из вставленных букв или 1 сокращали -/ лась с той самой буквой с или Ъ с которой она была вставлена. Тогда из всех слов, входящих в вывод, можно вычеркнуть все буквы с и Ъ , не участвующие в преобразованиях типа (4) , вместе с теми буквами с и " , с которыми они были вставлены. Все вставки букв GLj , не участвующих в преобразованиях типа (4) , могут быть исключены аналогичным образом. Итак, остается исключить вставки букв /; и СС: , участвующих в преобразованиях типа (4) . Оказывается, однако, что в кратчайшем выводе таких вставок не может быть. Лемма 2. Если слова Л и У не содержат отрицательных степеней букв, то в кратчайшем выводе, переводящем Л в / » буквы і 1 и ОС: , появившиеся в результате вставки, не могут участвовать в преобразованиях типа (4 ).
Один пример группы с неразрешимой проблемой равенства
Пример группы ("точнее говоря специальной полутруппы, являющейся группой,) с неразрешимой проблемой равенства слов, все определяющие соотношения которой имеют вид /\ - { . Отметим, что, как доказал СИ. Адян [/ 3J » в случае, когда все определяющие слова имеют вид А = і » где ГЪ - достаточно велико, проблема равенства слов разрешима. Итак, пусть /} = «,, , ..., .; ЛL = 4, « - rrL» -группа с неразрешимой проблемой равенства слов. Рассмотрим группу Pz с образующими и определяющими соотношениями Ьі-l , i .2, -, ҐК, (і) где каждое слово L L получается из слова Л і заменой каждого вхождения букв OLj на слова м С,- . Очевидно, что группа Ii изоморфно вкладывается в группу Jz » поэтому в Гг проблема равенства слов также неразрешима. Рассмотрим теперь группу /3 с теми же образующими, что и I и с определяющими соотношениями bL-i , i = ,-, ҐУЬ Лемма I. Группа П, изоморфно вкладывается в группу /3 и в / J проблема равенства слов неразрешима. Доказательство. Поставим в соответствие каждому слову д из Гі слово в алфавите группы /3 , получающееся заменой каждого вхождения буквы OL- на слово $; С- , как мы делали при построе «J 0 0 нии системы (i) . Очевидно, что такое отображение будет гомо - 61 морфизмом. Слова, являющиеся образами слов из / будем называть правильными. Докажем, что если правильные слова X и / равны в группе Iг , то они равны и в / Введем для слов, выводимых из правильных в [Z , понятие разбиения на правильные и неправильные участки индукцией по длине вывода. Если длина вывода, переводящего правильное слово X в слово Z равна 0 , то Z Л и мы будем говорить, что все слово представляет собой один правильный участок. Пусть слово Z выводится из слова д за /1-і шагов и для него задано разбиение на правильные и неправильные участки, то есть слово Z представлено в виде 2Е 2Л 1г ... Zt, где каждое Z - правильный или неправильный участок и из двух соседних участков всегда один правильный, а другой - нет. Пусть слово Z получается из Z одним элементарным преобразованием.
Возможны 4 случая: I/ это преобразование - вставка нетривиального соотношения; 2) это преобразование - сокращение нетривиального соотношения; 3) это преобразование - вставка ОІ ; 4) это преобразование - сокращение а- . В первом случае если вставка произведена в неправильный участок, то вставленное слово присоединяется к этому неправильному участку. Если вставка произведена в правильное слово лили рядом с правильным, то если оно осталось правильным, то принимается за новый правильный участок, если же вставленное слово /л; разделяет некоторый правильный участок Zs на два слова ъ и Zs , то А- - объявляется новым неправильным участком, а Д и Zs - 62 новыми правильными участками. Все остальные участки не меняются. Во втором случае А ; может быть сокращено С по индукционному предположению) только в одном из участков. Если от этого участка остается непустое слово, то оно и объявляется новым участком таким же, как до сокращения /\t- , если же сокращается целиком участок (он, конечно, может быть только правильным) , два соседних с ним неправильных участка объединяются в один. В третьем случае поступаем так же как и в первом, а в четвертом - как во втором, кроме случая, когда сокращается одна буква из правильного участка. Тогда соседняя с ней буква присоединяется к неправильному участку. Рассмотрим теперь вывод, переводящий правильное слово X в правильное слово / . Если в нем во всех словах вычеркнуть все неправильные участки, то этот вывод легко преобразовать в вывод, состоящий только из правильных слов и переводящий Л в У в группе / 4 , Лемма 2 доказана.
Итак, мы построили группу с неразрешимой проблемой равенства слов, в которой все образующие имеют порядок 2. Нам не понадобится в дальнейшем различать буквы ь и С- , поэтому мы будем обозначать все образующие группы /3 через ОІ . Таким образом, мы имеем группу в которой проблема равенства слов неразрешима. Рассмотрим теперь группу Р с теми же образующими и соотношениями 7 d.Sr-ЬЫ, j--U..., (з) - 63 Лемма 2. Два слова X и У равны в полугруппе / я тогда и только тогда, когда существует слово Zr б В В » гДе В; 8 6- - попарно различные определяющие слова из (l) , fc-y ) Li.) — f Iff такое, что ZX равно У в группе Гч . Доказательство. В одну сторону утверждение леммы очевидно, так как все соотношения группы / ч выполнены ив I $ и, кроме того, все слова Z: равны 1 в группе / ъ . Пусть теперь слово А равно слову У в группе 3 Дока зательство будет вестись индукцией по числу нетривиальных преобра зований в выводе, переводящем определяющие соотноше ния Otj= мы будем называть тривиальными).
