markov_teorija_algorifmov (522344), страница 40
Текст из файла (страница 40)
2,34. Если лс: Р 1 — ° (е, то (з: а[Р ',=аРЯ Доказательство опирается на леммы 2.32 и 2.33. Оио проводится аналогично доказательству леммы 2.17. 2.35. если Ю': Р~=(), то (5: а[Р ~= а[(е Доказывается с помощью леммы 2.31 нндукцией по шагам работы алгорифма ЯД'. 2.36. Если л)': Р! — ° Я, то 9:: а[Р ~=а6[Я Доказательство опирается на леммы 2.35 и 2.34.
Оно проводится аналогично доказательству леммы 2.19, Следующие три леммы касаются одного алгорифма 1з. 2.37. Если Ц вЂ” слово в А, то (5: аЯ )=а[(с ''.Д Для доказательства замечаем сначала, что (29) хэ: я3)7)- я9х ' (39) Ю 65)7 (- В пя)х 2!в СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИФМОВ !ГЛ. !Ч (эти утверждения получаются непосредственно из рассмот- рения схемы (3)). Затем с помощью (29) и (30) правой индукцией по Я доказываем, что (31) б: аЩ )=а[1,! 7х, после чего, положив в (31) )с ХЛ, получаем требуемое. 2.38.
Если Π— слово в А, то 6: а[) [!е )=а)з!е. Доказательство аналогично доказательству леммы 2.37. Сначала рассмотрением схемы (3) убеждаемся, что (32) 6: аЯ [7А7 [ — а(7ч [7х7 (ЗЗ) 6: ар(Г7)С [)х 7- ар!Е7!С [!с Затем с помощью (32) и (ЗЗ) правой индукцией по !е по- казываем, что (34) 6: а[1 [!зй '— аР!е [!с после чего, положив в (34) !7хсЛ, получаем требуемое. 2,39. Если !е — слово в А, то 6: а!4!е ! — ° !е. Получается непосредственным рассмотрением схемы (3).
Активной в данной ситуации формулой является формула ар— единственная заключительная формула алгорифма 6. 2.40. Если 3': Р~= 7Е, то 6: аР'1= 7,!. В самом деле, пусть 2)': Р[= !7. Тогда 6: аР 7=а [Р [2.371 [=- а1) Я [2.361 ~=а(1 !е [2.381 [=. 1;! [2,391 и, следовательно, 6: аР~= !З, что и требовалось доказать. 2.41. Если Р и А1 — такие елово в алфавите А, что 6: а[Р 1- а[!;!, то !В': Р 1- ().
Пусть, в самом деле, (35) 6: а[Р )- а[!г где Р и !г — слова в А. Так как алгорифм 4)' замкнут [9 36.2.Ц, слово Р поддается ему [3 36.1.Ц. Поэтому суще- ствует такое слово )7, что имеет место одно из следующих двух утверждений: (36) 6': Р(-)7 37! КОМПОЗИЦИЯ АЛГОРИФА7ОВ 2!3 или Если бы имело место второе из них, то, согласно 2.32, существовали бы такие слова 3 и Т, что (37) б: а[Р (- а[В 6 [Т ' и мы имели бы , (38) а[!г ма[Я [)[Т [(35),(37)1, й-=.[~-~[Т- [(38)1, что невозможно, так как () не входит в [Ц-. Следовательно, имеет место (36) и , (39) 6: а[Р 1 — а[)7 [(36),2.3Ц, ",' (40) а [!г л.
а [)7 [(35), (39)1, '. (41) [73- ~ [)7- [(40)], ' (42) !',! м )7 [(41), 2.81, Е: Р(- д [(36),(42)1, что н требовалось доказать, Условимся теперь слова вида а[Р , где Р†сло в А, называть специальными. Системы, все члены которых суть специальные слова, мы также будем называть специальными. Для специальных систем Х мы введем следующую операцию [Х~: [ус =у [Ха [Р 7'~ = — [Х Ру. . (Здесь Х вЂ” специальная система, а Р— слово в А.) Ясно, что если Х вЂ специальн система, то [Х вЂ си- '7 стема слов в А, причем Х соединяет а[Р с а[() тогда и только тогда, когда [Х соединяет Р с !е. 2.42. Всякое специальное слово алгорифм б просто переводит в некоторое слово.
В самом деле, пусть а[Р†специальн слово. Рассмотрим слово Р. В силу замкнутости нормального алгорифма В' в алфавите А [3 36.2. Ц, этот алгорифм просто или заключительно переводит Р в некоторое слово [3 36.1. Ц. Согласно леммам 2.31 и 2.32 как в первом, так и во втором случае 6 просто переводит а[Р в некоторое слово, что и требовалось доказать. 2!4 СОЧЕТАНИЯ НОРМАЛЬНЫХ АЗГОРИФМОВ ИГЛ. 1Р 2.43. Если слово Р в А таково, что алгориф.ч 6 примеьйм к а[Р, то алгорифм В применйм к Р. В самом деле, пусть Р— ~акое слово в А, что алгорифм 6 хрименим к Р, и пусть 6(а[Р )м(7. Тогда в силу замки)тости алгорифма 6 [2.7) имеем 6: а[Р )= (7. Поэтому существует слово У такое, что 6: а[Р ~=У( — ° У, и, значит, существует переводная система Х схемы алгорифма 6, соединяющая специальное слово а[Р со словом У.
Легко видеть, что У не является специальным словом, так как 6: У !- (7 [2.42]. Таким образом, первый член системы Х является специальным словом, а последний ее член таким словом не является. Арифметический преднкат «член системы Х с номером У не является специальным словом», очезидно, разрешим. Поэтому на основании теоремы о наименьшем числе [4 21.2.Ц существует член )Р' системы Х такой, что )Р' не является специальным словом, а все члены Х с меньшими номерами являются специальными словами.
Система Х имеет вид У)РА, где У вЂ” специальная переводная система схемы алгорифма 6. Первым членом У является слово и [Р-, Пусть слово Р таково, что а [РЕ является последним членом У. Тогда 6: а[ЕЕ 1- (Р'. ~ истема [У'7 является переводной системой алгорифма В' 2,4Ц. Она соединяет слово Р со словом Рт, Поэтому В: Р)=Е. Существует слово 6 такое, что В': Й 1- Я или В': )7 ! — !~. Пусть В': )7 ! — 1;!. Тогда 6: а[)7 1 — а[Я [2.3Ц и )Р'ма[(), что невозможно в силу выбора )Р'. Таким образом, В': Й1- !г и В': Р)= 1г, т. е.
В применим к Р, что и требовалось доказать. 2.44. Если слово Р в алфавите А таково, что алгорифм 6 применим к ир, то алгорифм В применим к Р. В самом деле, пусть алгорифм 6 применим к ар. Тогда алгорифм 6 применим к а[Р [2.37], откуда следует, что алгорифм В' применим к Р [2.43]. 2.45. Если имеет смысл выражение В(Й(Р)), то алгорифм 6 применим к слову Р и 6(Р) хВ(й (Р)). В самом деле, пусть выражение В(Й(Р)) осмысленно.
Тогда алгорифм й применим к слову Р, а алгорифм  — к слову Я (Р). Положим (43) 1') Й (Р), (44) )7 = В (Й (Р)). КОМПОЗИЦИЯ АЛ4'ОРИФМОЗ Имеем (45) 46) (47) (48) (49) [(51), ~ 36.2.1Ц [(54), ~ 36.2.1Ц [(55), (56)]. Й (Р) м !г В(!',!) ~Р4 В(21(Р)) о Рс Следовательно, В(Я (Р)) имеет смысл, что и требовалось доказать. '.В ((г) ~)7 [(43), (44)1 Я'(р) в р [(43), 4 36.2.!4], В' Я)Х)7 [(45), ф 36.2,14], Я'; РР=.Р [(46), ~ 36,2,1, 5 36,1,3], В' д~=.)7 [(47), 4 36,2,1, % 36.1.3), 6: РЧ=а0 [(48), 2 19] [(49), 2.40].
Следовательно, , (50) 6; р)=.)2, 6 (р) х Р [(50)] Х В (Й (Р)) [(44)) что и требовалось доказать. Для завершения доказательства теоремы нам остается ' теперь доказать, что выражение В (Я (Р)) имеет смысл для ' слова Р в алфавите А, коль скоро имеет смысл 6(Р), т. е, . коль скоро алгорифм 6 применим к слову Р. 2.46. Если алгорифм 6 применйм к слову Р в алфавите А, то имеет смысл выражение В(Й (Р)). В самом деле, пусть алгорифм 6 применим к слову Р в А, Тогда алгорнфм Я' применим к Р [2.22).
Положим (51) 1;! .—.= Я' (Р). Тогда 9 есть слово в А, так как Й' — алгорифм в А. ' Имеем, далее, , (52) Й'; Р)= ° !! [(51), ~ 36.2,1, ~ 36.1.3], . (53) 6: Р~=аД [(52), 2.!9]. , Так как, согласно предположению, алгорифм 6 применим к Р, он применим и к аег [(53)]. Отсюда следует, что алгорифм В' применим к слову (7 [2.44]. Положим ; (54) )е = — В' (ф. Тогда ', (55) " (56) 216 сОчетАниЯ нОРмАльных АлгОРиФмОВ 1гл тч Доказательство последней леммы завершает доказательство теоремы 2.1. 3. Докажем теперь теорему композиции в общей форме.
Пусть й и  — произвольные нормальные алгорнфмы. Пусть Б и В означают соответственно их алфавиты, и пусть (1) А — Б() В. А является расширением каждого из алфавитов Б и Б. 11оэтому существуют формальные распространения алгорифмов й и В на алфавит А 13 35.5.31. Пусть й, означает формальное распространение й на А, В,— формальное распространение В на А. й, и В, суть нормальные алгорифмы в А [й 35.5.11. К нпм применима доказанная теорема 2.1, согласно которой может быть построен такой нормальный алгорифм 6 над А, что (2) 6(Р) В,(й,(Р)) (Р— слово в А).
Покажем, что так построенный нормальный алгорифм 6 над А удовлетворяет условию 1(1). В самом деле, так как й, и В, суть соответственно фор« мальные распространения нормальных алгорифмов Й и В, имеем, согласно 2 35,5.4, (3) й, (Р) й (Р), (4) В (~Р) — В(()) Следовательно, для слов Р в А 6(Р) — В(й (Р)) Е(2), (4)) = В(й (Р)) 1(3)1, и, таким образом, условие ! (1) выполнено, что и требовалось доказать. 4. Проведенное только что !2, 3) построение дает для любых двух данных нормальных алгорифмов Й и В нормальный алгорифм 6 над объединением А их алфавитов, удовлетворяющий условию 1(1). Единственный и, очевидно, несущественный элемент произвола в этом построении — это „новые" буквы, т.
е. буквы, принадлежащие алфавиту алгорифма 6, но не принадлежащие А. Эти буквы, т. е. буквы, играющие роль и, р и двойников, могут быть выбраны произвольно, лишь бы они были отличны друг от друга и не принадлежали алфавиту А. Роль же их в построении алгорифма 6 вполне определяется схемой 2(3), где только роль Й и В играют формальные распространения Й, и В, этих алгорнфмов. АОМПОЗИЦИЯ АЛГОРИФМОВ ,37] 2!7 Нормальный алгорифм 6, построенный как только что описано и в существенном однозначно определяемый нор- мальными алгорифмами Й и В, мы будем называть нормаль- ной композицией алгорифмов Й и В.
Нормальную компози- цию алгорифмов Й и В мы будем обозначать символом («той), В соответствии с этим равенство (В Х (Вой) будет означать, что 6 есть нормальная композиция алгорифмов Й и В. Следующие утверждения резюмируют предыдущее: 4 4.1. Для любых двух нормальных алгорифмов й и В су- ' ществует нормальная композиция (Вой). 4.2. Нормальная композиция нормальных алгорифмов Й в и В есть нормальный алгорифм над объединением алфавитов этих алгорифмов, определенный в сущеспыенном однозначно. 4.3. Для любых двух нормальных илгорифмов й и В (Вой) (Р) В (й (Р)) (Р— слово в А), ° где А означает объединение алфавитов алгорифмов й и В.
5. Приведенное доказательство теоремы 1.1 представляет собой типичный пример конструктивного доказательства: утверждая существование нормального алгорифма 6, определенным образом связанного с заданными нормальными алгорифмами й и В, мы указали способ *), позволяющий потенциально осуществить этот алгорифм, коль скоро заданы исходные алгорифмы й и В. Типичным примером неконструктивного доказательства этой теоремы было бы доказательство по следующей схеме: предположив, что каким-нибудь образом доказано несуществование искомого алгорифма 6, привести это предпо- ,",„.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
