markov_teorija_algorifmov (522344), страница 44
Текст из файла (страница 44)
Алгорифм 6 замкнут. 3.4. Если ег': Р»- 9, то Э: Р» — ге. 3.5. Если й: Р»- Я, то существуют такие слова 14 и Е, что 9 я Ю и 6: Р»- )гаЯ. 3.6. Если Л и Я вЂ” слова в А, то Э: Пал'н=аМ. Отсюда, как в доказательстве теоремы 4 37.2.1, получаем 3,7. Если 3(': РН= (е, то 6: Р»=аД (см. 2 37,2.19). ч) См.
$24.8. 401 повторение лггоРИФмА 2ЗЗ 3.8. Если Р— слово в А и алгорифм 6 применим к Р, о алгорифм Й' также прилгеним к Р (см. 2 37, . ). ,2.22 . Рассматривая схему (1), убеждаемся в справедливост и следующих двух лемм: 3.9. Если (е — слово в А, начинающееся буквой (), то : а9» — 9. 3.10. Если Я вЂ” слово в А„не начинающееся буквой р, то 1 6: аЯ»-Д. Докажем, далее, 3.11. Если Я (Р) лс гч и ге начинается буквой »г, то Пусть, в самом деле, 9((Р)я.Я, где Я начинается ук- я бкг вой ]1. Тогда 91'(Р) о Я [2 36.2.10] и потому Я': Р р= Я (2 36.2,1, $ 36.1.3].
Поэтому (2) 6; Р»=аЯ [3.7], Я является при этом словом в алфавите А, так как а (Р) ль г,'1 и й — алгорифм в А. Так как Я начинается буквой (1, имеем (3) 9; аЯ» — Я [3,9], 6: Р»= 0 [(2), (3)], что и требовалось доказать. 3.12. Если й (Р)я гг и (1 не начинается буквой и, то 9: Р'г=ге с ществует такая переводная система Х схемы гХО~ 3 алгорифма 6, соединяющая Р с г',1, что [ В самом деле, как и в случае предыдущей леммы, ч(': Р»= ° Я, и потому 6: Р~=а9 [3.7]. Кроме того, Э: а(е»- (г [3.10]. Следовательно, существует переводная система У схемы алгорифма Э, соединяющая Р Л. слово в А, а а не является буквой этого алфавита, [У') Система Х вЂ” УЯТ соединяет Р с Я и, кроме того, [Х" = =[У' + 1, т. е.
[Х" )~ 3, что и требовалось доказать. 3.13. Пусть 3 — многочленная итерационная цепь алгорифма, со ф 9( оединяющая слово Р со словом Я и такая, что с квай . П спгь всякий ее внутренний член не начинается буква" Р. у ге начинается буквой»1. Тогда 9(Р) л-'ге. В . еле, пусть соблюдены условия леммы. Тогда самом деле, п ь начало 5, Р и Я являются словами в А, причем ТРТ есть а ТЯТ вЂ” конец Я. Существует у-система Т в алфавите А такая, что (4) Е -~ Тртду. ма ггг. Из 2.1 след ет, что Т есть итерационная цепь алгорифма гг. Всякий член системы Т является внутр з . следует, что т енним членом Я и 234 СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИФМОЬ [ГЛ.
!Ъ «ь! потому не начинается буквой р. Рассмотрим случай, когда У вЂ” пе ~~у. Тогда Т имеет первый и последний члены. Пусть — первый член Т, а Р' — ее последний член. У и К суть слова в А. Существуют слова Х и г' в алфавите Ау такие, что (5) Т ХуУуХ и (6) Т7~Ь'Р~. Имеем Ю~. уру(77ХЯу [(4), (5)] и Π— уру"РЯу [(4), (8)]. П оэтому в О слово Р соседствует слева с У, а слово У вЂ” с (е. Покажем, что 9: Р) — — )Р' для всякого члена )Р' системы Т. Имеем Я(Р) л' У, так как 3 — итерационная цепь Я. У не 3.12 . начинается буквой р, так как У вЂ” член Т.
Поэтому 6: Р)= У ~. Пусть теперь для члена )р' системы Т установлено, что: Р ~ Ф', и пусть Ж' соседствует слева с Р в Т. Тогда Я ()Р') м )г, так как Т вЂ” итерационная цепь Я. )г есть член Т 3.12 ипт и потому не начинается буквой )1. Следовательно 9: 1«')=1« [ .
], и потому 6: Р~)х. Применяя метод индукции вдоль 1 системы [3 24.1,6], видим, что каждый член )Р" у-системы Т удовлетворяет условию 9: Р)= )Р'. В частностй ему удовлетворяет последний член Т, т. е. имеем (7) 9: Р[=У. С другой стороны, Я ()т) я. 1е, так как 5 — итерационная цепь Я. А так как 1г начинается буквой ~), то (8) 6; У)=.о [3.!!]. Поэтому 6: Р~= м [(7) (8)], и, следовательно, 9 (Р) ~ 1г. Итак, мы убедились, что если Т д у, то 6(Р)Х«е. Если же Ттху, то ~ — уРЯу [(4)] и Р соседствует слева с Я в О'. Поэтому Я(Р) ~«е и так как Д начинается буквой р, имеем 9: Р~ Д [3.1!], откуда опять следует, что 9(Р) я.(1, Лемма 3.13 доказана, ПОВТОРЕНИЕ АЛГОРИФМА 3.14. Пусть М вЂ” натуральное число, Р— слово в алфаите А. Пусть также ) !6 (Р) и (10) ,Тогда 6(Р) — слово в А, начинающееся буквой р, и существует многочленная итерационная цепь О' алгорифма %, соединяющая Р с 9(Р) и такая, что всякий ее внутренний член не начинается буквой 8, а объем не превосходит М+1.
Доказательство будем вести методом арифметической индукции. С этой целью обозначим буквой Р следующий одноместный арифметический предикат со свободной натуральной переменной М: «Каково бы ни было слово Р в А, если оно удовлетворяет условиям (9) и (10), то 9 (Р) †сло в А, начинающееся буквой р, и существует многочленная итерационная цепь 3 алгорифма Я, соединяющая Р с 9(Р), такая, что [5' М+1 и что никакой внутренний член 3 не начинается буквой р». Лемма 3.14 будет доказана, если мы докажем, что всякое натуральное число удовлетворяет Р. Число 0 тривиальным образом удовлетворяет Р.
В самом . деле, если слово Р в алфавите А удовлетворяет условию (О), ' то в силу замкнутостиалгорифма6[3.3] имеем6: Р)= 9(Р), и потому (9:Р) ) О, что при М=О противоречит условию (10). Таким образом, при М=О не существует слов Р в алфавите А, удовлетворяющих условиям (9) и (10), а потому 3 0.2] верно всякое общее высказывание о таких словах. том числе для всякого такого слова Р верно высказывание «6(Р) есть слово в А, начинающееся буквой р, и существует многочлеиная итерационная цепь Я алгорифма Я, соединяющая Р с 9(Р), такая, что [8'(! и что никакой внутренний член О не начинается буквой ~)». Пусть теперь для какого-нибудь М мы убедились, что оно удовлетворяет предикату Р. Покажем, что М+1 также удовлетворяет Р.
Пусть Р— слово в алфавите А, удовлетворяющее условию (9) и условию (11) (6:Р) ( М+1. 6: Р)= 9 (Р) [(18) (18)АТ 9 ()к) яг 6 (Р), и, значит, (17) причем (18) (9: гс) ~ (6:Р) — 2 < )у. Воспользуемся теперь тем, что ту Р. Т ак как слово К в алфавите А р, что й( удовлетворяет предикаловиям (17) и (18) то 9ТР есть с , то ( ) есть слово в А, на инающееся , и существует многочленная ите ационная алгорифма Я, соединяющая Я с 9(Р) с ( ), такая, что никакой 23б с ОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИФМОВ Из (9) следует, что 1Е(Р) [3.8). Значит, существует славой (12) Я (Р) т: К. Выясним, начинается ли чая: а) К начинается б Й буквой 8. Возможны два слуа) Й начинается б кво" я буквой 8; б) Р не начинается буквой 8.
1 буквой 8. В этом случае 6: и потому 9(Р)~И. Следовательно, имеем (13) 9 (Р) х 8( Р» [(12)1 и 9 (Р) есть сло (14 слово в А, начинающееся букв " й. П ой 8. оложим ) 5 =ТРТ9(Р) у. Так как Р и 6 6(Р) суть слова в алфавите А, 5 е стема в алфавите А сое есть у-си- Е , соединяющая слово Р со словом 9(Р).
ели какое-нибудь слово Х сосе ств е буд У' 5 Х следует, что Й (Х)м )'[(13)1. Следовательно 5 есть тельно, всякий вн т ен квой р. Многочленна, так как [5' = 2. Отсю а, О не начинается буквой 8. В этом случае с- ияю ая ющая Р с )т и такая, что [У') 3 [3.121. Имеем поэтому 9: Р~Я, и так как в силу замкнутости 6 [3.31 (16) 9: Р~= 6(Р), то 'у 4ь2 ПОВТОРЕНИЕ АЛГОРИФМА 231 ее внутренний член не начинается буквой р и что (19) [т" ~ А(+1. Положим (20) 5 ТР7' и покажем, что 5 есть многочленная итерационная цепь алгорифма е(, соединяющая Р с 9(Р), такая, что никакой ее внутренний член не начинается буквой 8 и что (21) [5' ( А(+ 2.
Этим лемма 3.14 будет доказана. Так как Р— слово в алфавите А, а Т вЂ” 7-система в А, : 5 есть Т-система в А. Р является первым членом 5. Так как Т соединяет )к с 6(Р), последним членом Т является 9(Р), Последним членом 5 также является 9 (Р). Таким ': образом, 5 соединяет Р с 9 (Р). Число вхождений буквы у в 5 очевидно больше двух, т. е. система 5 многочленна. Так как у не входит в слово Р в алфавите А, число вхождений у в 5 на единицу больше числа вхождений у в Т [(20Я, и потому (22) [5 =[т+1.
Следовательно, имеет место (21) [(22), (19)1. Если Х вЂ” внутренний член системы 5, то Х есть либо первый, либо внутренний член системы Т. Первым членом системы Т является слово Я, не начинающееся буквой 8. Никакой внутренний член системы 7' также не начинается буквой (). Таким образом, никакой внутренний член системы 5 не начинается буквой 8. Остается доказать, что 5 есть итерационная цепь алгорифма й. Пусть слово Х соседствует слева со словом 1' в системе 5. Тогда имеем одно из двух: б,) ХЛ.Р и Гя.(с; б,) Х соседствует слева с У в Т. В случае б,) Й(Х) я)' [(12)1.
В случае б,) также имеем 6 (Х) я У, так как Т вЂ” итерационная цепь алгорифма 81. Таким образом, 81 (Х) Аь)л всякий раз, когда Х соседствует слева с )л в 5, т. е. 5 есть итерационная цепь алгорифма Й, что и оставалось доказать. 3.18. Пусть Р— слово в алфавите А, и пусть !6(Р). Тогда 9(Р) — слово в А, начинающееся буквой р, и суи1ествует многочленная итерационная цепь алгорифма 8(, соеди- 238 сОчетАния нОРмАльных АлГОРНФИОВ [гл. 1у няющая Р с 6(Р) и ( ) такая, что никакой ее внутренний член не начинается буквой р. Это следует из леммы 3.14, Из лемм 3.13 и 3.15 следует, что нормальный алгорифм Е удовлетворяет условию, поставленному в лемме 3.2.
Лемма 3.2, таким образом, доказана. Рассм Докажем теперь теорему 3.1. ассмотрим сначала тот случай, когда й и 6 суть но- Пусть р — буква, не входящая в А; 6 — нормальный ал- горнфм в алфавите А() со схемой феогласно 3 39.2.2 та Построим нормальный алгорифм ~ над алфа А() ал авитом дующие условия: таким образом, что будут соблюдены с е- ле1 . Алга нфм $ р ф хв прнменйм к тем и только к тем словам 2'. 9(Х х Х в алфавите А, к которым применйм алгориф 6. 6(Х) хЛ. ) р для всякого слова Х в А такого что ифм Ф для всякого слова Х в А такого, что 6 перерабатывает Х в непустое слово, Пусть зз яой).
алфавита Д. П Пусть Д вЂ” алфавит алгорифма Ж, Ясно что р б Э есть уква витом с ф Д. остроим нормальный алгорифм Е над ф- Д огласно 3.2 таким образом, что будет соб алфа- условие: равенство т с людено Е(Р) з:Я, где Р— какое-нибудь слово в алфавите Д, имеет место тогда , когда 4е — слово в Д, начинающееся бук- вои р, и существует многочленная итерацнонн О ая цепь ал- енннй р ф З, соединяющая Р с Д, такая, что р " член не начинается буквой 1).
Пусть о всякий ее вн т- (25) 6=(6 Е). 6 есть но мал что 4л) удовлетво яет ело рмальный алгорифм над алфавитом А. Д окажем, ряет условию, сформулированному в теоме . редварительно докажем некоторые леммы. . 6. Пусть Р и 4Š— слова в алфавите А. Пусть(ВЯ)Л.Л и пусть О' — многочленняя и е соединяю Р с итерационная цепь алгорифма й, ющал с 4Е и такая, что 6 перерабатывает в не- 4 401 ПОВТОРЕНИЕ АЛГОРИФМА пустое слово всякий внутренний член Я.
Тогда имеет место равенство 4О' (Р) я. Я. В самом деле, так как Я есть итерационная цепь алго- рифма й в алфавите А, то 8 есть у-система в алфавите А. Так как О' многочленна и соединяет Р с Ц, то существует у-система Т в алфавите А такая, что (26) З.-и ТРТОТ. Т есть итерационная цепь алгорифма й "12.1]. (е есть (как и Р) слово в алфавите А. Положим (27) УУ= у РТУУЗ, Так как у, Р, Т и 4Е суть слова в алфавите Ау, )Р есть слово в алфавите А1)у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
