markov_teorija_algorifmov (522344), страница 35
Текст из файла (страница 35)
5. Построим теперь два несколько более сложных нормальных алгорифма. Первый нз ннх — алгорифм отьюканил наибольшего общего дглипзгля — будет перерабатывать всякую пару натуральных чисел в наибольший общий делитель этих чисел; второй — алгорифм умножения — будет перерабатывать всякую пару натуральных чисел в произведение этих чисел. Оба алгорифма будут алгорнфмами над алфавитом ~зк, но не в этом алфавите. Зададим нормальный алгорифм й, в алфавите (дч аЬс схемой )а- а) ) Ф1 — алч жЬ Ь— а — с с— Покажем, что Й, перерабатывает всякую пару чисел УФМ в наибольший общий делитель этих чисел.
Следующие леммы непосредственно получаются из рас- смотрения схемы (1): 5.1. Й,: аоУаМ Фзт )- аО(У вЂ” 1) а(М+1) Яч У (У > 0). 5.2. Й,: аоУ чч У 1- ао (У вЂ” 1) а Ф (Я вЂ” 1) (Л >0, У>0). 5.3. й,: аоУячЬя )-ао(У вЂ” 1)РЬн+1 (У> О), 5.4. й,: аоФУЬл )-аоФ(У+1)Ьн-' (У> О).
5.5. Й,: смао нч у )- см+ 'ао-' зК у (я > О), !гл. !и !84 НОРМАЛЬНЫЕ АЛГОРИФМЫ 5.6. й,: Ясм ЖИ) (1~-)-1)см 'ЖУ (М >0). 5.7. Й,: ЖУ!-У. 58.йь: И]. С их помощью далее могут быть доказаны следующие леммы: 5.9. Й,: ачИаж)7~по+'Ижй [5,1]. 5.10. й,: аоУЖЯ)= ао+'(У вЂ” 1) Ж()7 — 1) (У > О, й > 0) [5.2, 5.9]. 5.11 61: УЖЯ~=ая (И вЂ” Р) Ж (У >Я) [5.10].
5.12 Й,: Уж)к)=анжЯ вЂ” У) (И <)к) [5.10]. 5.13. Й,: ачИ Ж)= ао Ж Ьн [5,3] 5.14. Й,: аожЬн~=асжУ [5,4]. 5.15, Й,: аОЖИ)=сОЖУ [5.5]. 5.16. Й,: сежУ)=джУ [5.6]. 5.17. й,: Ужи~= уж(и — и) (и>у) [5.11, 5.13, 5.14, 5.15, 5.16]. 5 18. й,: УЖ)7~УЖ(И вЂ” У) (У < И) [5.12, 5.15, 5.16]. 5,19. й,: ЖУ )= У ~ [5.7, 5.8]. 5.20. й;. У Ж )= У ] [5.17, 5.19]. Условимся теперь говорить о парах натуральных чисел Уж!к и Мж!е, что они эквивалентны, если !всякий общий делитель чисел У и Я есть общий делитель] чисел М'и !1 и наоборот.
При И~)Я пара Иж)с, очевидно, эквивалентна наре я ж (у — я), а при у < )7 она эквивалентна паре УЖ(1к — У). Леммы 5.17 н 5.18 показывают поэтому, что всякая пара УЖИ отличных от нуля чисел просто преобразуется алгорифмом Й, в такую эквивалентную пару чисел Мж!е, что М+!! < У+)7. Отсюда следует далее, что всякая пара чисел просто преобразуется алеорифмом йе в эквивалентную пару чисел, содержащую нуль в качестве одного из элементов, т. е. в пару вида Ж Я или (е'Ж. Для пар этого вида число (~ является, очевидно, наибольшим общим делителем, т.
е. общим делителем, делящимся на всякий общий делитель. В силу эквивалентности исходной пары чисел и получаемой из нее пары этого вида, !е является также наибольшим общим делителем чисел исходной пары. С другой стороны, согласно 5.19 и 5.20, й, естественно преобразует всякую пару вида ЖЯ илк Я Ж в 9. Таким образом, Й, естественно преобразует исходную пару НЕКОТОРЫЕ АРИФМЕТИЧЕСКИЕ АЛГОРИФМЫ 185 чисел в наибольший общий делитель этих чисел. Следовательно, Й, перерабол!ывпет всякую пару чисел УЖИ в наибольший общий делитель этих чисел, что н требовалось доказать. Алгорифм Й, задается в алфавите [жаЬ схемой Ь[- !Ь а (- [Ьа а )ж — жа (2) ! ж( ж Ь Покажем, что й, перерабатывает всякую пару чисел Мжй в произведенйе этих чисел.
Справедливость следующих лемм непосредственно усма- тривается из схемы (2). 5.21. й,: МЖИЬо[Ь Р)- МжИЬ вЂ” ~1ЬЛ 'Р (Е > О, Р— слово в )жаь). 5.22. Й,: МЖУЬча)гь!э ~ — МЖУЬО!Ьа()к — 1)ЬЛ ()7 > О). 5.23. Й,: МЖИьоаьн 1- МЖУЬО "Я. 5.24. й,: МЖУЬО ! — (М вЂ” 1)» аИЬО (М >0).
5.25. Й,: «Уьо (- «(У вЂ” 1) Ьо (У > О), 5.26. й,: «Ь.~ Ьо. 5.27. й,: Р(Ьа~ (И+1)ЬО- (О>О), 5.28. Й,: У~1. Из них вытекают следующие леммы: 5.29. й,: М«УЬО(ЬР)= М» (У+1)ЬО"Р (Р— слово в «аЬ) [5,21]. 5 30. й,: М». УЬоае(ЬЕ)=м «(У+1) Ьо''а(И вЂ” 1)Ьэ ()7 > О). В самом деле, при 17 > 0 й,: М «Иьоа(кьз ~= М и- Иьо '!Ьа(У вЂ” 1) Ьэ [5.22] )= М «(У+ 1) Ьое'а (У вЂ” 1) Ьв [5.29]. 5.31. й,; М «Иьоайьэ~м «(И+!Т)Ье'лаЬэ [5.30]. 1гл.
Рп ГЛАВ А 1«' 186 5.24] [5.32] 5.23] НОРМАЛЬНЫЕ АЛГОРИФМЫ 5.32. й„: М» а)7Ьз'Р=М».КЬ"аЬз [5.31]. 5 ЗЗ. РХ: М» КЬз ~ (М вЂ” 1)» Х«ЬЛ+з (М > 0), В самом деле, при М > О й,: М» )7Ьз !- (М вЂ” 1)»а)7Ьв )= (М вЂ” 1)». КЬлаЬз 1 — (М вЂ” 1) 48 )7ЬЛ+' СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИФМОВ Й,: М »г~4417ьинха> )= ». Ь(мха> !- Ь1М ха> )=(МХЛ)1 В силу 5.37 й,(М»)7) ОМХ)7, что и требовалось доказать.
[5. 34] 5,35] [5.26] 5.36, 5.28]. 5.34 Й«: М»КЬз)=(М вЂ” Я)»,)фчха>+в (С>(М) В самом деле, лемма тривиальна при (г= О. Допустим, что она установлена при 1~ =Х>7, где А> <М, и докажем ее тогда при О А>+1. Имеем й.: М» КЬ (М вЂ” 87)». РЬ! (М У 1)» РЬл+>нхл>+в [5 33] в (М (й1 1 1)) ~.
)7Ь><н+»хи> «з откуда следует доказываемое. 5.35. й,: ЭЬ )«Ьз )= 4Е Ьз [5.25]. 5.36. Й,: Ьз~5 [5.27], 5.37. Й,: м к 17)=(М х)7) ~. В самом деле, В 88 35 — 4! указывается ряд конструкций, позволяющих строить новые нормальные алгорифмы, исходя из данных. Наличие таких конструкций показывает, что естественные способы сочетания алгорифмов — такие, как последовательное применение двух алгорифмов, повторное применение одного алгорифма вплоть до получения результата, известным образом „удовлетворяющего" другому алгорифму, и т.
в.,— ведут от нормализуемых алгорифмов к нормализуемым же алгорифмам, Составляя аппарат общей теории алгорифмов, результаты, изложенные в этих параграфах, служат также серьезным доводом в пользу принципа нормализации. > 3 35, Распространения алгорифма $ В дальнейшем мы часто будем пользоваться знаком условного равенства «». Ставя такой знак между двумя выражениями, мы тем самым будем утверждать, что выражения эти означают одно и то же слово, коль скоро хотя бы одно из ннх имеет смысл. Обычно в скобках мы будем при этом писать те или иные дополнительные условия, налагаемые на составные части рассматриваемых выражений.
В этих обозначениях полная эквивалентность алгорифмов й и В относительно алфавита А выражается так: й(Р) В(Р) (Р— слово в А). Условное равенство, очевидно, рефлексивно, симметрично и транзитивно. 1. Пусть й — алгорифм в алфавите А, Б — расширение этого алфавита. Условимся говорить об алгорифме В в алфавите Б, что он есть распространение алгорифма Й на алфавит Б, если (1) й (Р) В (Р) (Р†сло в А), т.
е. если В вполне эквивалентен й относительно А [8 26 6] Ясно, что алгорифм в алфавите А может, вообще говоря, иметь несколько распространений на алфавит Б, так 188 сОчетАния нОРИАльных АЛГОРиФмоа [гл. [у !89 РАСПРОСТРАНЕНИЯ АЛГОРИФМА ьь1 как условие (1) не налагает никаких ограничений на работу алгорифма 6 над словами в Б, не являющимися словами в А. Мы рассмотрим сейчас два специальных вида распространений нормальных алгорифмов.
2. Пусть 6( — нормальный алгорифм в алфавите А, Б— расширение этого алфавита. Зададим нормальный алгорифм 1В в Б, взяв в качестве его схемы схему алгорифма 6(, что, конечно, допустимо, так как всякое слово в А есть вместе с тем слово в Б. Тогда, как мы скоро увидим, имеет место условное равенство (1) 5(Рй) ~6((Р) й (Р— слово в А, й — слово в Б';А), из которого, в частности (при й1хЛ), следует 1(1).
Фиксируем прежде всего слово Р в А и слово й в Б' А и условимся называть образом вхождения (2) 5[ь Т% О в слово Р вхождение (3) 54[ Т4АУй. Докажем некоторые леммы. 2.1. Образ всякого вхождения слова Т в Р есть вхожде- ние Т в Рй. В самом деле, если (2) — вхождение в слово Р, то (4) 5Т(7Х Р, 5тий х Рй 1(4)1, откуда следует, что (3), т. е, образ вхождения (2), есть вхождение в слово Рй. 2.2. Всякое вхождение непустого слова Т в алфавите А в слово Рй. есть образ некоторого вхождения Т в Р. В самом деле, пусть Т вЂ” непустое слово в алфавите А, 5М. Т ЧЬ У вЂ” его вхождение в Рй. Тогда (5) 5ТУ з Рй.
Так как Т~' Л, Т можно представить в виде [Уй, где $ — буква алфавита А. Имеем (6) Тм67$, 5нтьУ к Рй 1(5), (6)1. Таким образом, $У и й суть концы одного и того же ©лова. Поэтому й оканчивается словом $У или У вЂ” словом й. ',:Первое невозможно, так как буква $ алфавита А не входит 'в слово й в Б",А. Следовательно, У оканчивается словом , т. е.
существует такое слово (7, что У д[ий (7) Имеем теперь ,:(8) 5Т0й м Рй 1(5), (7)1, 5ти дахр [(8)1, 5 уг Т 48 У м.5 Ь Т:я ий '[(7)1. Следовательно, (2) есть вхождение Т в Р, а рассматриваемое вхождение 5 м. Т х. У есть его образ. Этим лемма доказана. 2.3. Если У и УР— вхождения одного и того же слова ве в Р, то образ У тогда и только тогда предшествует образу ЯР, когда У предшествует 1[7. Согласно определению предшествования 18 23.51 это непосредственно следует из совпадения левых крыльев вхождений в Р с левыми крыльями образов этих вхождений. 2.4. Если Т входит в Р, то образ первого вхождения Т в Р есть первое вхождение Т в Рй.
В самом деле, пусть У вЂ” первое вхождение Т в Р, Ф'— образ У. Если ТХЛ, то УльвечЬР, откуда ЯГХ+Х-Рй. Следовательно, в этом случае Ф' есть первое вхождение Р Т в Рй. Пусть теперь Т,е Л. Рассмотрим какое-нибудь отличное от йГ вхождение 67, слова Т в Рй. Согласно 2.2 оно есть образ некоторого вхождения У, слова Т в Р. У,д' У, так как [У,~г [Р. Так как У есть первое вхождение Т в Р, У предшествует У,.
Поэтому В' предп[ествует йг, 12.31. Следовательно, Ю предшествует всякому отличному от него вхождению слова Т в Рй, т. е. является первым вхождением Т в Рй, что и требовалось доказать. 2.5. Слово Т в алфавите А тогда и только тогда входит в Р, когда оно входит в Рй. Это верно при Т хЛ, так как Л входит и в Р и в Рй; при Т ф'. Л это непосредственно следует из лемм 2.1 и 2.2. 2.6. Если У вЂ вхожден слова Т в Р, [е †результ подстановки слова Ф" вместо У, то [ей есть результат подстановки слова Ю вместо образа У. 190 СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИФМОЕ В самом деле, пусть (9) У~5 эь Т бе (7. 1гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
