markov_teorija_algorifmov (522344), страница 69
Текст из файла (страница 69)
Аналогичная задача для случая одного соотношения общего вида до сих пор остается нерешенной. 7. Ассоциативное исчисление Й называется групповым, если может быть построен нормальный алгорифм 6 над алфавитом А исчисления Й такой, что для любого слова Р в алфавите А 6 (Р) определено и является словом в этом же самом алфавите, причем имеют место эквивалентности Й: Р6(Р)[[ А и Й: 6(Р) Р$ А. Это понятие дает конструктивизацию понятия конечно определенной группы, т. е. группы, заданной конечным числом образующих элементов и определяющих соотношений. Фигурирующий в определении алгорифм 6 играет роль обратной операции.
П. С. Н о в и к о в Ш, [2! построил первый пример группового ассоциативного исчисления с неразрешимой проблемой эквивалентности. Тем самым была решена знаменитая проблема тождества для групп, сформулированная еще в 1912 г. М. Д з н о м [!). Впоследствии аналогичные примеры были построены В. В. Б у н о м [1), Дж.
Л. Б р и т т о н о м П) и другими. Рекордный в отношении числа соотношений результат принадлежит В. В. Б ор и с о в у [1). 9 59. Проблема эквивалентности пустому слову 1. Частным случаем проблемы эквивалентности данному слову в данном ассоциативном исчислении 19 58.41 является проблема эквивалентности пустому слову в этом исчислении, Построим ассоциативное исчисление В в алфавите Ц, определяя гго системой соотношений, получаемой путем присоединения к определяющей системе исчисления 6 соотношения (1) аСр А-Р. Тогда для всякого слова Р в алфавите Г эквивалентность (2) 6: Р~~.С равносильна эквивалентности (3) Ь: арр [[ Л. Прежде всегочлегко усмотреть, что эквивалентность (3) имеет место для слова Р в Г, коль скоро для него имеет место эквивалентность (2).
В самом деле, так как все соотношения определяющей системы исчисления 6 принадлежат определякицей системе исчисления В, имеем (4) (5) Й: Р[[С, л): аР~ьЯ аСр 1(4), 9 57.6.51, а так как соотношение (1) принадлежит определяющей си- стеме исчисления А1, имеем (6) В силу (5) и (6) имеем (3) 19 57.6.4]. формулируемая так: построить для данного ассоциативного исчисления Й.нормальный алгорифм, применимый ко всякому слону в алфавите исчисления и перерабатывающий в пустое слово те и только те слова в этом алфавите, которые эквивалентны в Й пустому слову.
Мы увидим, что ассоциативное исчисление Й может быть построено таким образом, что эта проблема окажется неразрешимой. Чтобы установить этот результат, мы покажем, что всякая проблема эквивалентности какому-либо данному слову С в каком-либо данном ассоциативном исчислении 6 всегда может быть определенным образом сведена к проблеме эквивалентности пустому слову в некотором другом ассоциативном исчислении. Мы докажем следующую теорему: 1.1.
Пусть 6 — ассоциалшвног исчисление в алфавите Г, С вЂ” слово в этом алфавите, а и р — отличныг друг от друга буквы, не принадлежащие Г, Д Га[). $ ЗМ ПРОБЛЕМА ЭКВИВАЛЕНТНОСТИ ПУСТОМУ СЛОВУ 373 ПРОБЛЕМА ТОЖДЕСТВА ДЛЯ ПОЛУГРУПП !ГЛ У!П 372 Остается доказать обратное, т, е.
что (2) имеет место для слова Р в Г, коль скоро имеет место (3). Для этого введем некоторые вспомогательные понятия н обозначения. Условимся называть высотной слова Я число вхождений буквы а в это слово, высотой З-ряда Ал — наибольшую из высот членов этого ряда. Высоту слова Я будем обозначать символом Яв; высоту ряда !.в — символом [0н. Условимся называть протяжением ряда ~ число тех членов (((' этого ряда, для которых [Я7н [Я)н Протяжение ряда слов О будем обозначать символом [О". Очевидно, что высота всякого ряда слов есть натуральное число, а протяжение всякого ряда слов — положительное натуральное число. В следующей лемме мы пользуемся терминологией, введенной в 3 57.6. !.2.
Если О есть З-ряд, соединяющий У с В7, и (7) [Ун ( [Я)в (8) [)Р В ( [!)н то может быть построен такой ~2-ряд 81, соединяющий У с (У, что либо (9) [ в8 и ( [ либо [4!и =[Я',в и [8!п ( [Я~п В самом деле, пусть ц!-ряд Я1 соединяет У с Р7 и удов- летворяет условиям (7) и (8), Пусть !У вЂ” объем ряда О, т. е. число его членов. Обозначим посредством Я! (1 < !< У) !-й член*) ряда ~'. Тогда (10) Явя У, (11) ЯА,Х Я7, так как !! соединяет У с му.
Положим (12) По определению высоты ряда найдутся такие числа !, что Я!* й. Все они отличны от единицы и от )У, так как [Ц; < й [(7), (10), (!2)1, [И<й [(8) (11) (12)1 (13) в) См. 4 24.8. Пусть ! означает наименьшее из этих чисел. Тогда 1<!<Ф и, так как (14) [Я;<й (1 < !'< Аг) [(12Ц, имеем (15) в то время как (16) Яв й В силу (!3) имеются числа ! такие, что ! < ! < А! и что [Я; < й. Пусть й означает наименьшее из этих чисел. Тогда ! <й<й!, (17) [Я < й, (18) Я;=й (! <! <й) [(14), (16)1, Имеем 2:Яув(Я,, так как А! есть !В-ряд.
Это означает, что Я! может быть получено из Яу ! в результате подстановки правой или левой части одного нз соотношений определяющей системы исчисления З вместо некоторого вхождения другой части того же соотношения. Так как Ю(- <Ю! [(15) (16Н А так как подстановка правой илн левой части соотношения (1) вместо вхождения левой или соответственно правой части этого соотношения изменяет высоту, Я, получается это соотношение не может принадлежать определяющей системе исчисления !В, и действием, переводящим ЯА ! в !е, является подстановка левой части аС[! соотношения (1) вместо вхождения правой части этого соотношения, т.
е. вместо пустого слова. Таким образом, для некоторых слов )с и 5 в алфавите Д (19) Яу,х)75, (20) Я Х)саСРЯ. Слова !Е! (!<! <й — 1), имеющие одинаковую высоту й [(!8)1, являются членами л.'-ряда ! !. Имеем (21) л): Я! !' ( !',в! (! < ! < й), Я!- Я! О < е(й). 374 ПРОБЛЕМА ТОЖДЕСТВА ДЛЯ ПОЛУГРУПП !ГЛ. УП! из 0~, в результате действия, соответствующего одному нз соотношений определяющей системы исчисления 6 (1 <1< л).
Покажем индукцией по 1, что каждое нз слов Я, (1 < ~1< Й) может быть представлено в виде Я,аКфЯО где К~ — слово в Г, Н; и Бг — слова в Д, причем (22) [Яв [Яв Для 1 ° 1 зто вытекает из (20): следует положить (23) (24) Р~ — Р, (25) 5( — 8. Допустим, что для некоторого 1, удовлетворяющего условиям 1 (1( й — 1, имеем (25) Я,,Ась;,аК; в)157 „ где К;,— слово в Г, Я~, и 5~,— слова в Д, причем (27) Я в [яв Покажем, что тогда (28) Я, Зь Я,аК~~ЯН где К~ — слово в Г, )('; и Я; — слова в Д, причем имеет место равенство (22). Я~ получается из ф, в результате подстановки правой нли левой части )' одного нз соотношений определяющей системы исчисления 6 вместо некоторого вхождения другой части Х того же соотношения. Х есть слово в алфавите Г, и потому буквы а и р не входят в Х.
Ввиду (25) Я, имеет один нз видов (29) ТОК,,РЗ(, ~<- ' К~-вГвГ (Т вЂ” результат подстановки У вместо вхождения слова Х в 3,,). (Т вЂ результ в Й;,), (30) (Т вЂ” результат в К,,), (31) подстановки )' вместо вхождения слова Х Й;,аТ[)5~, подстановки 1' вместо вхождения слова Х $59! ПРОБЛЕМА ЭКВИВАЛЕНТНОСТИ ПУСТОМУ СЛОВУ 373 Положим (32) К,=т, К,=К; „3,=5; „ если Я; имеет вид (29); (ЗЗ) м;=)т'; „К;= — Г, Я,=Я,, если Я; имеет вид (30), и (34) Я,.=Я, „К,=К,, Я,— Т, если Я; имеет вид (31).
Тогда во всех случаях будем иметь равенство (28). В этом равенстве К, либо равно К;,„лнбо есть результат подстановки )' вместо вхождения слова Х в К, [(32) — (34), (30)]. Так как 1' есть слово в Г, К, есть, как и К; „слово в Г. Аналогичным образом усматриваем, что Рп 3; суть, как и )т,. „Я; „слова в Д, причем рв ров = [)св [(27)], Тем самым доказано наше утверждение о виде слов Я; (1'(1< Л).
В этом виде каждое из слов Я; (1'<1(е), очевидно, представляется лишь единственным образом, причем прове- денное рассуждение показывает, что прн всяком 1, удовлет- воряющем условиям ) <1( е, имеет место одно из трех: а) 6,: Я;, ) Рп К,,ХКО З,,ХЯ,:, где 6,— ассоциативное исчисление в алфавите Д, опреде- ляемое той же системой соотношений, что и 6. Допустим сначала, что для всякого 1, удовлетворяющего условиям / < 1< е, имеет место случай б). Тогда )г,.л.
Ят (35) ~К (1<1< й) [(24)], 5,ХЯ (35) л. О (1 < 1 < й) [(25)], (37) Г1 ХКОК$3 (1(1 < й) [(28), (35), (35)]. Имеем Г: Юв,.).ЯА, так как А1 есть х:-ряд. Прн этом ИЕ < [0А- [(17), (18)]. 376 ПРОБЛЕМА ТОЖДЕСТВА ДЛЯ ПОЛУГРУПП ~ГЛ. ЧП! Это означает, что Я» получается из Я» 1 в результате подстановки правой части соотношения (3), т. е. пустого слова, вместо некоторого вхождения левой части этого соот- ношения. Ввиду того, что а:1~р и ни а, ни () не входят ни в слово К», в алфавите Г, ни в слово С в этом алфавите, Я» имеет один из видов ТОК» 1[18 (Т вЂ” результат подстановки Л вместо вхождения слова аСр в )7), Ю, Рг»К,ГаТ (Т вЂ” результат подстановки Л вместо вхождения слова аС() в 3).
Если (38) Я» л. )со, то Я»ХЯ7 1 [(38), (19)], Пусть 791УХУа, 17 — начальный отрезок ряда е., соединяющий Я1 с Я7 „а 71а»в17~ 71аЛУ вЂ” концевой отрезок этого ряда, соединяющий ~»+1 с Ям. Тогда ряд ,д,уХТОА,ТО„,ТУТО у, есть, как и А1, 1Т1-ряд, соединяющий те же слова, что и АА, т. е. соединяющий У с ЙР. Этот ряд мы и примем за Я. Ясно, что (39) [9)(в ( [.С1н И ЧТО ПРИ (40) [яв [9на имеем (41) [Я = [~„(й )) [(18) (42) [Я" < [Ю [(41)], Таким образом, в этом случае ряд Я обладает всеми тре- буемыми свойствами.
Лопустим теперь, что (43) Я»лйТиК» 1)1О, 9»М пРОБлемА экВиз»лентности пустОму слОВу 377 где Т есть результат подстановки пустого слова вместо некоторого вхождения слова с»Ср в )с. Положим тогда (44) Т3, (45) Р; — ТаК1Г»3 (1(~1< й). Пусть ЧА — система слов объема й — 1+1 такая, что ее 1-й член есть слово Р, 1, Примем за Я ряд 7()17ХЯ/-1%()»+~7УЯлу. Так как 1> 1 и (46) Р,, ~ ()» [(45), (43)], ряд Я соединяет (даже при 1=79') те же слова, что и А1, т.
е. он соединяет У с В7. Имеем далее (47) 2: Я, 1 ()„+1 (1<7<) — 2); (48) В: Р, ) Я»+1, 2: Яа 1~,на (й+1<з<й( — 1), так как А) есть В-ряд и имеет место равенетво (46); (49) й: )с ( Т, так как Т есть результат подстановки правой части соотношения (1) вместо вхождения в )с его левой части; ~.'1 Ят, 1 Р,, [(49), (19), (44), 6 57.5,3], Имеем также, па предположению, Е: К,, 1 К» (1 <1< й), откуда (51) й: К», 1 К, (1<1< й), (52) В; Р», 1 Р, (1 <1< й) [(51), (45), 5 57.5.3].
Наконец, имеем Р АА ТаСр8 [(45), (23)], откуда, согласно (44), (53) ц1:Рг, ) Р. Смежности (47), (50), (53), (52), (48) показывают, что Я есть Ь-ряд. Сравнивая слова Я1 и Р, при 1'<1 < й и замечая, что (54) ' [ < [й", Зтз ПРОБЛЕМА ТОЖДЕСТВА ДЛЯ ПОЛУГРУПП !ГЛ УИ! усматриваем, что [Р; < [()1 [(45), (37), (54)], откуда (55) [Р! < И О (' < й) [(18)] Имеем также [Р!, < [1)1- [(44), (19) (54 56 <И (15) .
)] ( ) 1 Таким образом, высоты всех членов ряда ф меньше И, т. е. меньше высоты ряда ф. Следовательно, [яв ([г1в Так как переход от А! к Я состоит, согласно (46), в замене й — 1 слов !1! (](!(И вЂ” 1) высоты И [(18)] словами Р, (1 — 1( (г( И вЂ” 2) меньшей высоты [(55), (56)], имеем при [81в =[А1' неравенство (42). Это показывает, что ряд Я обладает всеми требуемыми свойствами. Совершенно аналогичным образом строится искомый ряд Я в том случае, когда Ю,~йаКА в6Т, где Т есть результат подстановки пустого слова вместо не- которого вхождения слова аС6 в О.
Мы завершили, таким образом, рассмотрение того случая, когда условия б) соблюдаются для всякого ! такого, что 1<1<И Допустим теперь, что для некоторых таких ! Эти условия не все соблюдаются, и обозначим через т наименьшее нз этих !. Тогда, согласно доказанному выше, для в=т соблюдаются либо условия а), либо условия в), в то время как для всякого ! такого, что 1<!<т, соблюдаются условия б). Случай, когда при !=т соблюдаются условия а), и случай, когда при 1=т соблюдаются условия в), рассматриваются совершенно анало- гичным образом. Будет поэтому достаточно провести построе- ние искомого ряда )7 для первого из этих случаев.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
