markov_teorija_algorifmov (522344), страница 67
Текст из файла (страница 67)
Следовательно, пр,РП)-прг гРп (1 < ! < lг — 1) [(27), (28)], ББ! НЕРАЗРЕШИМОЕ АССОЦИАТИВНОЕ ИСЧИСЛЕНИЕ н потому пр,РП )- прд,Рп под РП [(27)], 359 откуда следует доказываемое, 1.14. Если Р— слово в А и Й: Р ], то (29) прРП ! — ПОРП. В самом деле, в этом случае ни одно нз слов У; (1<! <1у) не входит в Р, и потому пр,РП! Пан+!Рп, что совпадает с (29), так как р,л.р, ОА+!3:о, 1.15. Если Й: Р (- (г, то (30) прРп ! Прдгп. В самом деле, пусть Й: Р! — г",!.
Тогда на первом шаге работы алгорифма Й в применении к слову Р действует одна из обычных формул схемы (2). Пусть это будет фор- мула (31) Уд "д. Тогда слова У! (1<1< й — 1) не входят в Р и 1'д есть слово в алфавите А. При этом Р есть слово в А, так как Й вЂ” алгорнфм в А. Применима, следовательно, лемма 1.13, согласно которой (32) рРп~ АР . В силу применимости формулы (3!) к слову Р ее левая часть Уд входит в Р. Пусть Я ФУдчгЯ вЂ” первое вхождение У„в Р. Тогда (зз) Р Х НIАЗ, (34) 9 х %где. Если Уд~ Л, то (35) пр ЯУАЗп ~ и!ТрдУАЕП [применяются — при непустом 'гс — соотношения, принадле- жащие 1-й группе системы (3)] и, значит, (36) пр,Рп )= ПРрдУАЯп [(35), (ЗЗ)].
Если же УдйЛ, то 7!ХЛ, 87АР, и потому пр Рпй хпггрдУАЯп, откуда следует (36). Таким образом, (36) имеет место во всех случаях. пговлемА тождестВА для полэггэпп 1гл, щн $ ее1 НЕРАЗРЕШИМОЕ АССОЦИАТИВНОЕ ИСЧИСЛЕНИЕ 361 З6О Соотношение рь(7А+.>а,1'А принадлежит З-й группе системы (3), так как формула (31) простая. Поэтому (37) лЯр (7„5л» вЂ” пЯО,УА5л. Пользуясь далее соотношениями б-й группы системы (3), получаем лЯО,У 5п ~ лагЯУА5л (38) Х ла, Ял [(34)]. Наконец, соотношения 5-й группы системы (3) дают (39) па Рл» вЂ” лрАРл, (40) лагЯл ' — лргЯл. Таким образом, лр,Рл» лаАРл »- лреРл ~ лЯр„(7А5п »- лЯа,УА5л ~= лагЯл »- лргЯл [(32)] [(39)] [(36)] [(37)] [(38)] [(40)] что и доказывает собственную преобразуемость (30), так как р, к р.
1.16. Если Й: Р»- Я, то (41) прРл ~ лаЯл. рь(7 +-+ О,УА где УА есть такое слово, что У к Уь'. Равенство (33) имеет место по-прежнему, тогда как вместо (34) имеем теперь (43) Я о ЯУ;5. Так как соотношение (42) принадлежит системе (3), имеем (44) лЯр„(7А5л» вЂ” лЯа „У~5п. Рассуждая, как в предыдущем доказательстве, получаем (32), (39) и (36), где й, Я и 5 имеют прежний смысл. В отличие от предыдущего доказательства, формула (31) теперь заключительная и потому 4-я группа соотношений системы (3) содержит соотношение (42) Соотношения б-й группы системы (3) дают, наконец, (45) лЯаег~гУА5л ~= пан,.ЯУ'5л Ас па,+гЯл [(43)]. Таким~'образом, лр,Рл»- лЯрАУА5л [(32), (39), (36)] » — лЯО „,У'5л [(44)] ~ ЛОА,+гЯЛ [(45)], что и доказывает собственную преобразуемость (41), так как р,Хр, а„„,хСа.
1.17. Если Й: Р»= Я, то прРл~лрЯл. Это следует из 1.15. 1.18. Если Й (Р) ХЯ, то имеет место эквивалентность (1). Пусть, в самом деле, Й(Р)АсЯ. Тогда имеет место одно из двух". Й: Р»= Я» или Й: Р»= Я., В первом случае лрРл ~= лрЯл [1.17], лрЯл» лаЯл [1, 14], откуда (46) лрРгг ~ лаЯл, Следовательно, (1) имеет место [1.10]. Во втором случае имеется такое слово Я, что Й: Р»=Я» — Я. Для него имеем лрРЛ»= лрЯл [1.17], лрЯл ~ паЯл [1.16], откуда также следует (46) и (1). Для завершения доказательства теоремы 1.1 нам, очевидно, остается доказать следующее утверждение, обратное лемме 1.18, 1,19. Если имеет место эквивалентность (1), еде Р и Я вЂ” слова в А, то Й(Р)'аЯ.
Докажем его. Пусть эквивалентность (1) имеет место для слов Р и Я в алфавите А. Тогда прРл'ь паЯл [1.9], т. е. может быть построен 2)-ряд 5, соединяющий лрРл с паЯл. При применении алгорифма е1 к слову Р возможны три случая: Й: Р», Й: Р» — Р, для некоторого Р„Й: Р» — Я для некоторого Я.
362 ПРОБЛЕМА ТОЖДЕСТВА ДЛЯ ПОЛУГРУПП [ГЛ. ЧП1 Если Й: Р~1, то в силу 1.14 имеет место собственная преобразуемость ярРп ~ иоРи, и, значит, существует правильный В-ряд 5„соединяющий ирРп с поРя. В силу 1.11 5, является началом 5, так что 5Л.5!В7, где уя7 — правильный В-ряд. Нетрудно видеть, что В7 ХЛ, так как в противном случае правильный В-ряд 5 имел бы вид 5!7 РпуЮ!у.
аЯ что очевидным образом невозможно 11.81. Следовательно, 5х5„ а значит, паЯя Х паРи, и потому Я Х Р. Кроме того, 6(Р)Л.Р, так как й: Р~). Следовательно, й (Р)Х Я, что и утверждается. Если Й: Р )- )т для некоторого )т, то ирРп 1- пайп, н, значит, существует правильный В-ряд 5„соединяющий прРи с па)тп. Как и в предыдущем случае, в силу 1.11 5, является началом 5, так что 5Х5!й7, где уя7 — правиль- ный В-ряд. Снова 17~Л в силу тех же самых причин, и, значит, откуда Я хЯ.
Кроме того, 6(Р) Л.Тт, так как й: Р ~= )т. Следовательно, й (Р) Р Я, что и утверждается. Пусть, наконец, 6: Р )- Р, для некоторого слова Р,. Тогда в силу 1.18 имеем прРи ~ ирР,я, и, значит, существует такой правильный В-ряд 5„соеди- няющий ирРП с прР,я, что (5,'.=: 2. В силу 1.11 5, является началом 5, так что 5Х5!йт, где уй7 — правильнйй В-ряд. 5 соединяет прРп с яоЯя, а 5,— ирРя с ирР,я. Поэтому 5 .:Р уярРпуХупаЯиу, 5, Х уирРИТХ!ТпрР!пу В вв1 ИЕРАЗРЕШИМОЕ АССОЦИАТИВНОЕ ИСЧИСЛЕНИЕ З6З для некоторых Е и Е!.
Предположив, что В7Л.Л, т. е. что 5х51, мы получаем„что рха, между тем как р~':а по выбору этих букв. Следовательно, В7:!ГЛ и, значит, объем В-ряда уй7, т. е. число его членов, больше нуля. Последний член ряда у((7 представляет собой последний член ряда 5, т. е. слово паЯя. Таким образом, для некоторого В7! Й: Р,)- Р„ и правильный В-ряд Т„соединяющий слово прР,я со словом яоЯя и такой, что ~ТО < 1ТО Это последовательное построение слов Р! и правильных В-рядов Тв должно не позже чем через 15Π— 1 шагов оборваться на некотором слове Рв, для которого 6(Р ) ХЯ. Имеем тогда Й; Р)=РА й (Р) х Я, и, значит, что и требовалось доказать. 5 вАуярРиуй!ТярР!пуР7!ТяаЯиу, и потому В-ряд Т ..— упрРвп) "Р7вупаЯяу соединяет слово ирР,и со словом паЯи.
Легко видеть, что объем этого ряда строго меньше объема ряда 5. К этому ряду и к слову Р, применимо рассуждение, только что проведенное для ряда 5 и слова Р. Мы заклю- чаем из этого утверждения, что возможно лишь одно из двух: либо 6(Р,)ХЯ, либо имеются слово Р, такое, что Й: Р!)-Р„ и правильный В-ряд Т„соединяющий слово ярР,п со сло- вом паЯя и такой, что Г <Т В первом случае Й (Р) тг Я, так как Й: Р ) — Р, и й (Р!)ТгЯ. Во втором случае, рассуждая аналогично предыдущему, убеждаемся в том, что либо й (Р,) ХЯ, либо имеются слово Р, такое, что $ 58! НЕРАЗРЕШИМОЕ АССОЦИАТИВНОЕ ИСЧИСЛЕНИЕ ЗВЧ !Гл. чп! Зб4 ПРОБЛЕМА ТОЖДЕСТВА ДЛЯ ПОЛУГРУПП Теорема 1.1, таким образом, доказана.
2. Пусть, как обычно, А, означает алфавит аЬ, а А, означает алфавит абебе. Пользуясь теоремой 1.1, докажем следующую теорему: 2,1. Может быть построено ассоциативное исчисление В над алфавитом А„удовлетворяюи(ее следующему условию: невозможен нормальный алгорифм над алфавитом А„перерабатывающий в пустое слово те и только те слова Р в А„ для которых эквивалентность (1) В: ЙСРй$ с(ес( не имеет месит. Построим, в самом деле, нормальный алгорифм Ы! в алфавите А, согласно й 51.3.2, т. е. так, чтобы удовлетворялось условие: невозможен нормальный алгорифм над А„ аннулирующий, т. е. перерабатывающий в пустое слово, те и только те слова в А„которые $8, не аннулирует. Применим к алгорифму Я., теорему 1.1, полагая АХ А,, рхс, пХс(, ОХе.
Согласно этой теореме построим ассоциативное исчисление 6 над алфавитом А,сйе, т. е. над А„удовлетворяющее условию: равенство ЕВч(Р) х. 1е имеет место для слов Р и Я в А, тогда и только тогда, когда В: йсРс( 'й йенни. Это исчисление и является искомым. Действительно, согласно построению, 28, аннулирует те и только те слова Р в А„для которых имеет место (1).
Если теперь какой-нибудь нормальный алгорифм над А, аннулирует те и только те слова в А„для которых (1) не имеет места, то он аннулирует те и только те слова в А„которые В), не аннулирует. Такой нормальный алгорифм над А„ однако, невозможен по построению Я,. Невозможен, следовательно, нормальный алгорифм над А„перерабатывающий в пустое слово те и только те слова в А„для которых эквивалентность (1) не имеет места, что и требовалось доказать. Пользуясь аналогичным образом теоремой ~ 51,3.4 вместо теоремы 3 51.3.2, получаем следующий результат: 2.2.
Может бь!ть построено ассоциативное исчисление В над алфавитом А„удовлетворяющее следующем у условию: невозможен нормальный алгорифм над А„применимый ко всякому слову в А, и перерабатывающий в пустое слово те и только те слова Р в А„для которых имеет место эквивалентность (1). 3. Исходя из 2.1, докажем следующую теорему: 3.1. Может быть построено ассоциативное исчисление 6 над алфавитом йе, удовлетворяющее следующему условию: невозможен нормальньи! алгорифм над алфавитом исчисления В, перерабатывающий в пустое слово те и только те слова в этом алфавипче, которые не эквивалентны в В слову йей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
