markov_teorija_algorifmov (522344), страница 54
Текст из файла (страница 54)
Гогда 6: Парра,У )= П [Р'ара,У [инд. предпол.) )== Ц [РиаЬс-хра,У )- ЦР'аЬаарУ 5 йг П [РатарУ, т. е 6: Парра,У)= П [Ро,'арУ, что и оставалось доказать. 2.3. Пусп~ь 31 — нормальный алгорифм в а фавите А, У— слово в алфавите Асфуб. Тогда (3) арйи1,')= йи иарУ докхзлтельство теопемы 293 Доказывается индукцией вдоль схемы*) алгорифма й. В самом деле, для алгорифма й с «пустой» схемой [9 24.31 утверждение (3) верно: 6; аруУ 1- тарУ.
7 Пусть теперь утверждение (3) верно для алгорифма й при любом У, удовлетворяющем указанному в формули- ровке леммы условию. Покажем, что оно будет верно и для нормального алгорифма й, в алфавите А, схема которого получается из схемы алгорифма й присоединением еще одной формулы подстановки. Обозначим посредством Р, и Р, соответственно левую и правую части этой формулы.
Поло- жим, кроме того, в я.а, если эта формула простая, и вя р, если она заключительная. Тогда й",Х31"Р,вриу и, следова- тельно, 6: ар%",У м. арй ир,вриТУ )= Ь'иаррхвриуУ [инд. предпол.1 ~=й™ [Р;арвриТУ [2.21 21ии [РтварР „У 7 йхи [Рив[Р1арТУ [2 21 йхи [Ри [Ри рУ х й'иарУ, 12 т. е 6: а14(йУ)=й1 арУ что и оставалось доказать. 2.4. Пусть Гу' — слово в алфавите Ар, Π— слово в алфавите А,. Тогда (4) 6: %'лЫЩ=Ф'Ы лЯ. Доказывается индукцией по 1.
В самом деле, при 1' О утверждение (4) тривиально. Пусть теперь утверждение (4) верно для какого-либо 1 при любых Ф' и 1Е, удовлетворяющих перечисленным в формулировке леммы условиям. Тогда 6: ГулЫи'ф=27ЫлЬЯ [инд. предпол.1 )- Ф'Ы"'лЯ, з что и оставалось доказать.
«) То есть по поссроеыпю схемы. 1гл. У УНИВЕРСАЛЬНЫЙ АЛГОРИФМ 6: 1ГЬ44/а,2)= К'Ь4а„~Х. (5) <1> <2> <3> <4> <5> 6: л[Р'О Ь= РЙЯ. (б) [инд. предпол,) [2,41 [2.5), т. е. П. 2(,бр) Я.4994[РТ 2.5. Пусть иу — слово в алфавите Ар, Х вЂ” слово в алфавите А,п и / < а. Тогда Доказывается индукцней по 1'. В самом деле, при 1'=О утверждение (5) тривиально. Пусть теперь утверждение (5) верно для какого-либо / () < а — 1) при любых (У и 2, удовлетворяющих перечисленным в формулировке леммы условиям. Тогда 2 [инт предпол 1 )- (РЬ4а Т 2 что и оставалось доказать. 2.6. Пусть Р— слово в алфавите А, Я вЂ” с 2ово в алфавите А,.
Тогда Доказывается правой индукцией по Р. В самом деле, при Р~Л утверждение (б) тривиально. Пусть теперь утверждение (6) верно для какого-либо Р при любом 4г в А,. Пусть 1(1(и. Тогда и [РаЯ и и [РтаЬТаг> 1= — РпаЬта() )- РрпЬ! ТаР 49 1=РрЬЛ- паГ> )- РрЬт 4а„п() 2 / ь Н ~4~ )= РЬ" .4ра,п~ (- РЬи-у „и() 1 — — Раи п1~ что и оставалось доказать.
3. Закончим теперь доказательство теоремы 1,1, Утверждение б) этой теоремы непосредственно следует из леммы 2.6. Таким образом, оставалось доказать утверждение а). 9441 ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ 225 Если 21 — нормальный алгорифм в алфавите А, а Р— слово в алфавите А, то 6: арй(ибР)=Я' иорЬР [2. 31 Ят и~угарР в ХЯ 'иеарР )=Я тив[Ртар [2 21 )- 2( е[Р аЬРЬ 9 и(. 4 ив [Рт и 4. Завершим теперь доказательство теоремы об универсальном алгорифме.
Покажем, что условию этой теоремы удовлетворяет нормальный алгорифм П в алфавите АББввубгуроли41ь4 [Э 43.11 со схемой й Пусть й — нормальный алгорифм в алфавите А, Р— фавите А, У и У вЂ” слова в алфавите АА,абуберил и омл (т. е. в алфавите алгорифма 6). Все левые части форму подстановок из схемы алгорифма В 3 не являются словами ф АА и() берия [см.
2 43.11 и, значит, не входят в У4. Поэтому, если 6: 1', )- Уи, то 11: 1', )- „и, л д тельно, если б: У4~= У„ то П: У,'Н= Уи. Таким образом, П: ЯибР ( — ар21"ЬР '=-21'" "г [Р' [1.1 а)1 Е. и4 [Р.с з и потому П(21 ЬР) = П(2('"ы[Р') УНИВЕРСАЛЬНЫЙ АЛГОРИФМ [гл. у Кроме того, П. (Рт) Р ~ ) — ° Р, 11.1б)1 т. е. П (л~Рт) Х Р, так что П(л(Й(Р)') Я(Р).
Поэтому для доказательства теоремы об универсальном алгорифме теперь достаточно показать, что П(Я' "в)Р') П(л(Й(Р)'). Но так как в схеме алгорифма д) нет заключительных формул подстановок, имеем П(31'™гв~Р') П(6(Й'ем~Р')). Отсюда по теореме 3 43.2.1 П (Я'" тя(рт) П (лй'((Р')). Это завершает доказательство теоремы об универсальном алгорифме, так как по теореме о переводе Ц 41,5.221 Я' (1Р') ~ (Я (Р)т. 5.Пи р веденное доказательство теоремы об универсальном алгорифме основано на уже упоминавшейся в п.
3 3 31 методике В. Г Жарова. Основной тенденцией доказательства является стремление к зкономии: сложность схемы алгорифма П равна, как нетрудно подсчитать, ба+349; обоснование правильности схемы также представляется нам достаточно компактным. а . идонзменение теоремы об универсальном алгориф ~е а45. В 1. П и р пятый нами способ изображения нормальных алгорнфмов является простым и удобным, но требует введения новых букв. В дальнейшем нам понадобится иной способ изоб ажения нормальных алгорифмов, способ несколько более сложный, однако обходящийся лишь двумя буквами.
В тех случаях, когда исходный алфавит содержит более одной буквы, этот способ даст нам возможность записывать схемы нормальных алгорифмов в исходном алфавите в виде слов в этом же алфа. вите, что имеет существенное значение, как мы увидим ниже. 2, Наряду с алфавитом Лару, используемым нами для построения изображений нормальных алгорнфмов в А, мы 4 л! ВИДОИЗМЕНЕНИЕ ТЕОРЕМЫ 297 рассмотрим двухбуквенный алфавит А, Х аЬ и определим, как в Э 41.3 — 4, операцию перевода слов в алфавите Лару , таким образом, чтобы все буквы этого алфавита переводи- лись Л-литероидами, т. е.
словами вида аВа, где  — не. пустое слово в однобуквенном алфавите Ь. (Следовательно, роль алфавита А из ~ 41.3 у нас играет пустой алфавит Л, а роль алфавита Б — алфавит Лару.) Мы при этом не предполагаем, что буквы алфавита А, отличны от букв алфавита Аа11у, Может быть построен нормальный алгорифм Х над ал- , фавитом А, 0 Аи()у, перерабатывающий всякое слово в алфавите Лару в перевод этого слова 1Ц 331.
Легко также построить нормальный алгорифм г, над Л,0Ла1)у, перера- батывающий перевод всякого слова в Асфу в само это слово. Этими алгорифмами мы будем пользоваться в даль- нейшем. 3. Будем теперь рассматривать нормальные алгорифмы в алфавите А и их изображения. Перевод изображения нор- мального алгорифма в алфавите А мы будем называть записью этого алгорифма. Зались алгорифма Я мы будем обозначать символом Й'. По определению записи Я' ~г $ (Й"), (1) 3(и х; ~ (Яз) для всякого нормального алгорифма й в алфавите А.
3.1. Запись всякого нормального алгорифма в алфавите А есть слово в алфавите А,. 3.2. Всякий нормальный алгорифм в алфавите А вполне определяется своей записью. В самом деле, если дана запись Й' нормального алгорифма Я в алфавите Л, то изображение Я" этого алгорифма может быть получено в результате применения к Я* алгорифма Х„а алгорифм Я однозначно определяется его изображением. 4. Особенно интересен тот случай, когда буквы а и Ь принадлежат алфавиту А. Тогда запись всякого нормального алгорифма в алфавите А есть слово в том же алфавите. Эта возможность записывать схемы нормальных алгорифмов в алфавите А в виде слов в том же алфавите, очевидно, связана не с тем, что А содержит именно буквы а и Ь, а только с тем, что этот алфавит содержит не менее двух букв.
Тогда можно выбрать произвольным образом какие-нибудь две из букв алфави- эниввгслльнын ллгогифм [гл. ч та А и определить запись нормального ал?орифма в А, за- ставляя эти буквы играть роли а и Ь. 5. Мы докажем теперь теорему, аналогичную теореме 3 42.1.1, в которой роль изображения Я" алгорифма Я бу- дет играть его запись Я'. Эта «видоизмененная теорема об универсальном алгорифме» понадобится нам в даль- нейшем, 6.1. Пусть буква 6 не принадлежит алфавиту А 0 А,.
Тогда может быть построен такой норлшльный алгорифм д?? над алфавитом А(? А, (? 6, что (1) оп (я»бр),~, я (р) для любык слов Р в А и нормальных алгорифмов Я в А. В самом деле, пользуясь какими-нибудь буквами а, (1 н у, не принадлежащими алфавиту Аб, построим универ- сальный алгорифм П над алфавитом Аабуб согласно 9 42.1.1 таким образом, чтобы имело место условное равенство й 42.1 (2).
Построим отсекающие нормальные алгорифмы Вг. ь и Йг, ь [з 29.41, где Г = — Л, ц Аа!37. Построим нормальный алгорифм ?)1 как нормальную композицию ($,ойг,ь) алгорифмов Зг,ь и Тп И есть нор- мальный алгорифм над алфавитом ГЬ. Построим нормальный алгорифм ?ю над алфавитом ГЬ согласно теореме объедине- ния [Ц 38.1.11 таким образом, чтобы для любого слова (г в Г6 выполнялось условное равенство (2) с(()) =3((()) Ьаг,ь(()). Искомый алгорифм 2В построим как нормальную компози- цию (П о о) алгорифмов Ь и П, 2В есть нормальный алгорнфм над алфавитом ГЬ и, следовательно, над А,(? АЬ. Покажем, что для него имеет место условное равенство (1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
