markov_teorija_algorifmov (522344), страница 70
Текст из файла (страница 70)
Итак, пусть (57) (58) К о К (59) тогда как для всякого ! такого, что 1 < ! <т, соблюдаются условия б). При этом и есть некоторое число такое, что 1<т<й. $59! ПРОВЛЕМА ЭКВИВАЛЕНТНОСТИ ПУСТОМУ СЛОВУ Зтэ Имеем тогда )7сх й1 (60) х Я (1 (1 < т) [(24)], 3! ХЗ (61) ХЯ (1'(1(т) [(59), (25)], (62) ф Х РаКф5 (1(1 < и) [(28), (60), (61)]. Положим (63) Р, 1т„3, (64) Р,. — Я„аКфЯ (1(1<т) и примем за Я ряд такой, что его !-й член есть (1! при 1(!<1, Р!, при 1(!<и+1 и ()! при т+1(1(Ф. Так как 1 > 1 и т< И(л1, ряд Я соединяет те же слова, что А1, т. е. соединяет у' с Ф'.
Имеем (65) ч): 9! ) Я!+! (1(! <1 — 1), (66) ц!: Р, 1 (1 +„А): $1 $+! (и+1(1(в~1 — 1), так как А! есть Й-ряд н Р„,х() [(64), (58), (61), (28)]. Имеем далее !в; К,, 1 К, (1 < ! < т), откуда (67) Й: К! ! ) К! (1 < 1 < и), (68) ~; Р!, ~ Р, (1 < ! < т) [(64), (67), $ 57.5.3]. Имеем также (69) Р Ав)т аС~ЗЯ [(64), (23)], (70) Р.
Р,, ( Р,. [(63), (69)]. Наконец, имеем (71) вз,; )с) )г„[(57), (60)], (72) д): р( ] 11„[(71)], (73) ~; Р~, ) Р, [(72), (!9), (63), 5 57.5.3]. Смежности (65), (73), (70), (68), и (66) показывают, что Я есть В-ряд, пговлемА тождествА для полугпупп !ГЛ. У!П 990 ПРОБЛЕМА ЭКВИВАЛЕНТНОСТИ ПУСТОМУ СЛОВУ зв! Имеем далее (74) [)7» ~ [)7» [Р!- Т!-* (75) < 1! [Рв [ив 76 й [(22)1 [(74), (63), (19)] [(15)], (! (! < т) [(74), (64), (62)] ( ) [(18)1.
Из сравнения рядов % и ~~ видно, что % получается из Я' в результате замены слов (Е! (1<9(т) словами Р, (! — 1(9 < т — 1), Так как слова (;!! (!( !' т) имеют высоту Й [(18)1, а из слов Р, (! — 1(9(т — 1) первое слово имеет высоту, меньшую !т [(75)], а остальные — вы- соту Ь [(76)], имеем неравенство (39), причем в случае равенства (40) имеем [Яп [Я1» 1 < [ав Таким образом, и теперь построенный ряд Я обладает всеми требуемыми свойствами, Доказательство леммы 1.2 этим завершено. 1.3. При соблюдении условий леммы 1,2 может быть построен у ряд Я, соединяющий У с Ф' и удовлетворяющий условшо (9).
Пусть, в самом деле, соблюдены условия леммы 1.2. Строим тогда, согласно этой лемме, Й-ряд Я„соединяющий У с )у' н удовлетворяющий либо условию (77) [Яв < [Я)в либо паре условий (78) [1)(в [Е)в (79) [Яп < [~» Если соблюдено условие (77), то полагаем Я = %,; ряд Я, очевидно, обладает требуемыми свойствами. Е ели же соблюдены условия (78) и (79), то применяем лемму 1.2 к словам У, йх и ряду %, (в роли Я'). Это воз- можно, так как [Ув < [Я~ [(7) (78)1 [)Р" < [%» [(8), (78)1.
Строим, согласно 1.2, х!-ряд Я,, соединяющий У с Ж н удовлетворякнций либо условию (80) [Яв < [Яв либо условиям (81) (82) [Яв [Яв [Я,п < [%". Если соблюдено условие (80), то полагаем Ж вЂ” Я;, если же соблюдены условия (81) и (82), то применяем еще раз лемму 1,2, Продолжая таким образом действовать дальше, будем последовательно получать !г!-ряды, соединяющие У с Г и такие, что высоты их равны, тогда как протяжения строго убывают. Этот процесс, очевидно, должен оборваться (не более ЧЕМ ПОСЛЕ [А)п ШаГОВ), а ОбОрВатЬСя ОН МОжЕт ЛИШЬ тОГда, когда получится А!-ряд, соединяющий У с Вй и имеющий высоту, меньшую высоты ряда А!.
Такой З-ряд, следовательно, может быть построен, что и требовалось доказать. 1.4. Если З: У][ Ч!, то может быть построен ~Ю-ряд %, соединяющий У с %' и удовлетворяющий хотя бы одному из неравенств (83) [У' ~[%' (84) [Я7') [Я'. В самом деле, пусть Й: У][ 1(г. Тогда существует Й-ряд Г'., соединяющий 1" с ((Г, Если он удовлетворяет условиям (7) и (8), то строим, согласно 1,3, Й-ряд 9л„соединяющий У с йг и такой, что [0в! < [Св.
Если < [9ЛВ [рхв < [~в то строим, согласно 1.3, Й-ряд Ю„соединяющий У с 1(й н такой, что [А1; < 9л;. Этот процесс последовательного построения З-рядов, соединяющих У с )(Г и имеющих строго убывающие высоты, должен, очевидно, оборваться (ие более чем после [А)п шагов), а это, согласно 1.3, произойдет лишь тогда, когда получится л)-ряд Г'!„, соединяющий У с )(У и такой, что хотя бы одно из неравенств [Ув < [~~в [цхв < [~~в не соблюдается. Этот ряд А „, очевидно, и может быть взят в качестве Я.
)п(ы можем теперь закончить доказательствотеоремы 1.1, ПРОБЛЕМА ТОЖДЕСТВА ДЛЯ ПОЛУГРУПП !ГЛ. Ч!и 6691 пРОБЛЕмА ЭКВИВАлЕНтНОСти пУСтОМУ СЛОВУ 333 Допустим, что эквивалентность (3) Й: 66Р(1 )[ Л имеет место для слова Р в алфавите Г. Покажем, что тогда имеет место эквивалентность (2) В:Р С. Х Так как (85) [аР()в = 1 и [Л' О, может быть построен, согласно 1.4, я.-ряд А1 соединяющий аР11 с Л и удовлетворяющий условию [~~в ( 1 т..е. условию (86) [()в<1 (1«= <)У), где 1Е1 — 1-й член ряда А1, а Ф вЂ” его объем. Имеем (87) Х сьР~, (88) ()и ~Л, (89) Яй =0 [(88)~.
П 9=0. В усть 1 означает наименьшее из чисел 1, для которых [1Е1 = . силу (89) такие числа существуют и 1 < й(. В силу (85) и (87) 1 ) 1, Рассмотрим члены 1Е1 (1 (1 - 1) Й-ряда А1. По определению числа / имеем (90) [1;1;- 1 (1 < 1' </) [(86)1, (91) [ив.=О, Ра ассуждая далее, как в доказательстве леммы 1.2, убеж- даемся, что каждое слово Я1 (1(1<1) может быть одно- значно представлено в виде Р1аК11)О1, где (92) К1~Р, где )с1, Кв и 51 суть слова в Г н где при всяком 1 (1 < <1<1) имеем либо 6: К;, ! Кв, либо К тгК.
Имеем этому меем по- (93) аК,ЛК/ 1, С другой стороны, имеем 66К1- Рэ Ф:()1-;1 ();, откуда в силу (90) и (91) следует, что (94) Кг,~с. В силу (92) — (94) имеет место эквивалентность (2), что и требовалось доказать. 2. Теоремы 3 58.3.! и 1.1 дают возможность установить следующий результат (А. А. М а р к о в !61): 2.1. Может быть построена ассоциативное исчисление л1, удовлетворяюи(ее следуюи1ему условию: невозможен нормальный алгорифм над алфавитом исчисления Ь, перерабапичваю1ций в пустое слово те и только те слова в этом алфавите, которые не эквивалентны в З пустому слову.
Построим, в самом деле, ассоциативное исчисление 5 над алфавитом йе согласно 3 58,3.1. Применим к еэ теорему 1.1. Роль (В пусть играет при этом 2), роль à — алфавит исчисления В, роль С вЂ сло йеа в этом алфавите, роли 66 и р †как-нибудь две буквы, не принадлежащие Г. Построим согласно 1.1 ассоциативное исчисление лэ в алфавите Д, равном Гор, таким образом, что эквивалентность 16:Р )[ С тогда и только тогда будет иметь место для какого-нибудь слова Р в Г, когда будет иметь место эквивалентность В:аР!) 1[ Л. Исчисление 3О будет тогда удовлетворять условию, сформулированному в теореме 2.1.
Допустим, в самом деле, что 9 есть нормальный алгорифм над Д, аннулирующий те и только те слова в Д, которые не эквивалентны в л1 пустому слову. Построим нормальный алгорифм (й в алфавите Д со схемой где $ пробегает алфавит Г. Ясно, что для любого слова Р в Г имеет место графическое равенство 1в (Р) у. аРР. ПРОБЛЕМА ТОЖДЕСТВА ДЛЯ ПОЛ УГРУПП !ГЛ.
ЧП! э 60! 888 МЕТОД ВЫЧИСЛИМЫХ ИНВАРИАНТОВ Построим алгорифм м.' как нормальную композицию алгорифмов 6 и 9: (2) а — (е О6). м есть нормальный алгорифм над Г 1(2)1, причем для лю- бого слова Р в Г У((Р) — Ф (6 (Р)) ~(2)] $ (аР)») 1(1)1. Следовательно, м' тогда и только тогда аннулирует слово Р в Г, когда й аннулирует слово аР1), т.
е. когда аР(» не эквивалентно пустому слову в 1т1. Но, согласно построению исчисления ц1, эквивалентность лэ: аРр )) Л тогда и только тогда не имеет места, когда слово Р не эквивалентно йей в исчислении 6. Таким образом, гс аннулирует те и только те слова в Г, которые не эквивалентны сей в 6. Такой нормальный алгорифм й над Г, однако, невозможен, согласно построению исчисления В. Следовательно, невозможен и нормальный алгорифм ф над Д, аннулирующий те и только те слова в Д, которые не эквивалентны в 1Гэ пустому слову. Аналогично, с помощью теорем 3 58.3.2 и 1.1, устанавливается 2.2. Может быть построено ассоциативное исчисление л1, удовлетворяющее следующему условшо: невозможен нормальный алгорифм над алфавитом исчисления лэ, применимый ко всякому слову в этом алфавите и перерабатывающий в пустое елово те и только те слова в нем, которые эквивалентны в !ь пустому слову.
3. Аналогично тому, как проблему эквивалентности в данном ассоциативном исчислении Й можно истолковать как проблему тождества в порождаемой нм К-системе 13 57.9), проблему эквивалентности данному слову в исчислении Й можно истолковать как проблему тождественности данному элементу этой К-системы. В частности, проблему эквивалентности пустому слову в исчислении Й можно истолковать как проблему тождественности единичному элементу К-системы, порождаемой исчислением Й, т.
е. как проблему построения нормального алгорифма, распознающего элементы, тождественные единичному элементу этой К-системы, по словам, представляющим эти элементы. Доказанную только что тео- рему 2.2 можно в соответствии с этим рассматривать как установление возможности построения К-системы с неразрешимой проблемой тождественности единичному элементу. $60. Метод вычислимых инвариантов Мы закончим эту главу изложением одного предложенного А.
А. Марковым (см. (14), (15)) общего метода установления неразрешимости массовых алгорифмических проблем, находящего в рассматриваемой нами проблематике очень естественное применение. 1. Зафиксируем какой-либо алфавит А и будем рассматривать бинарные отношения между словами в нем. Под этим мы, как обычно, будем подразумевать двуместные вербальные предикаты, свободные переменные которых принимают в качестве значений слова в алфавите А. В целях краткости мы будем иногда опускать указания на алфавит и говорить просто о «бинарных отношениях».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
