markov_teorija_algorifmov (522344), страница 37
Текст из файла (страница 37)
Если алгорифм й применим к слову Р, то алгом б также применим к Р и й(Р)т6(Р) [4.91. 4.11. Если Р- -слово в А и 6: Р ~= !е, то й: Р ~ !е [4.4, 4.12. Если Р— слово в А и б: Р)=!е 1, то й: Р)=!! ) , 4.61. 4.13. Если Р— слово в А и б (Р) н 1~, то й (Р) о (г [4,11, 21. 4.14.
Если алгорифм б применим к слову Р в алфавите то алгорифм й также прил~еним к Р и 91(Р)~6(Р) 31. Из лемм 4.10 и 4.14 вытекает условное равенство 5'(2) й(Р) 6(Р) (Р— слово в А), означающее, что 6 есть распространение й на Б. Попробуем, с другой стороны, применить алгорифм 6 к какому-нибудь слову Р в алфавите Б, не являющемуся : словом в алфавите А, т.
е, содержащему вхождения букв ;алфавита Б ', А. В Р входит по крайней мере одна из ле''вых частей формул (!), стоящих вверху схемы алгорифма 6. : Пусть '. (3) Т! Ч вЂ” первая из тех формул (!), левые части которых входят в Р. Тогда (3) будет, очевидно, и первой формулой под.. становки алгорифма б, действу.ющей на Р. Алгорифм 6 в применении к слову Р предписывает подставить правую ".„часть этой формулы вместо первого вхождения ее левой ','. части в Р, что, разумеется, дает опять Р.
Так как примененная формула простая, имеем 6:Р! — Р, ', ' откуда следует невозможность окончания процесса применения алгорифма 6 к слону Р. Следовательно, этот алгорифм неприменим к Р. Мы видим, таким образом, что наше распространение алгорифма представляет собой своего рода „формальную отписку": алгорифм 6 применим к тем и только тем словам, к которым применим алгорифм й. В условном равенстве (2) можно поэтому отбросить дополнительное условие: Р†сло в А.
В самом деле, если Р не есть слово в А, то ни символ й (Р), ни символ 6(Р) не имеют смысла. 5. Распространение нормального алгорифма й на алфа- вит Б, получаемое как только что было описано, мы бу- 196 сОчетАния нОРмАльных АлГОРиФмов 1гл. ш дем называть формальным распространением этого алгорифма на Б. В том случае, когда алфавит Б' А содержит более одной буквы, фиксируя тот или иной порядок выписывания формул (1), мы будем получать различные формальные распространения й на Б. Однако различие их будет носить чисто внешний характер: результаты работы различных формальных распространений при одном н том же исходном слове всегда будут совпадать. Следующие утверждения резюмируют предыдущее: 5.1. Всякое формальное распространение нормального алгорифма есть нормальныи алгори4м. 5.2.
Схема всякого формального распространения нормального алгорифма Й получается из схемы этого алгорифма путем присоединения сверху формул подстановок вида 4 (1), где ~ь пробегает буквы алфавита формального распространения, не принадлежащие алфавиту алгорифма Я. 5.3. Каковы бы ни были нормальный алгорифм й в алфавите А и расширение Б этого ал4авита, существует формальное распространение алгорифма Я на алфавит Б.
5.4. Для всякого формального распространения 6 нормального илгорифма Й имеет место условное равенство й (Р) б (Р). Изложенная методика в известном смысле позволяет „приводить к общему алфавиту" два любых нормальных алгорифма, В самом деле, пусть Й и л) — нормальные алгорнфмы в алфавитах А и Б соответственно. Строим алфавит А() Б, являющийся расширением обоих алфавитов А и Б, и формально распространяем алгорифмы Й и В с алфавитов А и Б соответственно на алфавит А() Б. Получаемые при этом алгорифмы суть алгорифмы в одном и том же алфавите А() Б. Что же касается результатов их работы, то в этом отношении полученные алгорифмы ничем не отличаются от исходных.
2 36. Замыкание алгорифма 1. Будем говорить о нормальном алгорифме, что он замкнут, если его схема содержит формулу с пустой левой частью. 1.1. Если нормальный алгорифм Й в алфавите А замкнут, то й действует на всякое слово в А. В самом деле, схема замкнутого алгорифма содержит формулу с пустой левой частью, действующую на всякое слово в алфавите алгорифма. ,Азв1 ЗАМЫКАНИЕ АЛГОРИФМА 197 1.2. Если нормальный алгори4м й замкнут, то невоз" можен естественный обрыв процесса применения алгорифмай. Это следует из предыдущей леммы.
1.3. Если нормальный алгорифм Й замкнут, то Й (Р) х 1г '.'; тогда и только тогда, когда Й:Р~= 1е. В самом деле, если нормальный алгорифм Й замкнут, и то, согласно 1.2, й не может естественно преобразовывать Р в 9. Согласно 9 25,7 отсюда следует 1.3. 2.
Пусть Я вЂ” нормальный алгорифм в алфавите А. Нормальный алгорифм в А со схемой будем называть замыканием алгори4ма Й, Здесь и в дальнейшем мы применяем следующую символику: символ нормального алгорифма (в данном случае Й), написанный после фигурной скобки, означает схему этого алгорифма, написанную без своей фигурной скобки. Схема замыкания алгорифма Й получается, таким образом, из схемы й путем присоединения формулы снизу. 2.1.
Замыкание всякого нормального алгори4ма замкнуто. Это очевидно из определений. Замыкание нормального алгорифма й мы будем обознд- чать через Й'. Из сравнения схем алгорнфма Я и его замыкания легко усматривается справедливость следующих лемм: 2.2. Если й: Р)- Я, то Я': Р 1 — 1~. 2.3. Если Й:Р) — 1~, то Й':Р( — 1~. 2.4. Если Й:Р ~, то Й':Р) — Р.
Из них вытекают следующие леммы: 2.5. Если й': Р )- О, то 6: Р )- 1г )2.2, 2,3, 2.4, 9 25.4.71, 2.6. Если Й': Р)- 1',1, то либо й: Р 1 — Я, либо Й:Р ) и Р-~(~ 12,2, 2.3, 2.4, 9 25,4,71. Индукцией по шагам работы алгорнфма й с использова- нием леммы 2.2 получается 2.7. Если Я: РР=1г, то й': РР=4. Индукцией по шагам работы алгорифма Я с использо- ванием леммы 2.5 получается 2.8, Если Й':Р)=(~, то Й:Р~=Я. КОМПОЗИПИЯ АЛГОРИФМОВ ' Т! !99 3 37.
Композиция алгорифмов (3) Р98 СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИФМОЗ !ГЛ, !У Далее имеем 2.9. Если Я:Р)= 1~, то Я':Р)=.(7 [2.7, 2,31. 2.10. Если Й: Р)=А1 ~, то Й': Р)=.<~ [2,7, 2.41. 2.11. Если Й':Р)= (г, то Я:Р~= (1 или Й:Р)=() ) [2.8, 2,6~ 2.12. Если Я(Р)~гЯ, то Й'(Р) — с~ [2.9, 2,10, ~ 25.7~ 2.13. Если 9('(Р) ~ф, то Я(Р)~Я [2,11„1,3, 2.1, 825,7(, 2.14. Й(Р) Я'(Р) [2,12, 2,13), Мы доказали, таким образом, следующую теорему: 2.15.
Вслкии' нормальныи алгорифм вполне эквивалентен своему замыканию относительно своего алфавита. В силу теорем 2.15 и 2.1 рассмотрение произвольных алгорифмов сводится по существу к рассмотрению замкнутых алгорнфмов, что во многих случаях оказывается удобным ввиду теоремы 1.3. 1. Два алгорифма часто приходится сочетать следующим образом. Предписывается, исходя из произвольных начальных данных, сначала применить первый алгорифм, а затем к результату его работы — второй. Это предписание составляет новый алгорифм — «композицию> двух данных алгорифмов. Естественно спросить, является ли композиция нормализуемых алгорифмов также нормализуемым алгорифмом? Принцип нормализации подсказывает утвердительный ответ на этот вопрос, и, действительно, в этом параграфе мы докажем следующую теорему: 1.1. Теорема композиции.
Каковы бы ни были нормальныв алгорифмы Й и зВ, может быть построен такой нормальный алгорифм (а над объединением А их алфавитов, что длл любого слова Р в А имеет место условное равен ство (1) 6 (Р) 6 (Я (Р)) Доказательство этой теоремы ') н составляет главное содержание настоящего параграфа. 2. Мы начнем с того частного случая теоремы композиции, когда оба данных алгорнфма Я и 21 суть нормальные алгорнфмы в одном и том же алфавите А. Будем доказывать следующую теорему: *) См.
комментарий к доказательству в и. З. 4 2.!. Каковы бьс ни были нормальные алгорифмьс Я и 2) в алфавите А, может быть построен нормальный алгорифм аЪ над А, удовлепсворяюи(ий условию 1(1). Пусть, в самом деле, Й и  — нормальные алгорифмы ,в алфавите А. Поставим в соответствие каждой букве й этого алфавита новую букву, причелс разным буквам алфавита А— ,разные новые буквы. Букву, поставленную в соответствие букве Е, будем называть двойником этой буквьс и обозна, чать символом Е Двойники букв алфавита А составляют алфавит двойников А, содержащий столько же букв, сколько : А, и не имеющий с А общих букв. Пусть, далее, сс и р означают две дальнейшие новые буквы, отличные друг от друга, от букв алфавита А и их '.двойников. Составим алфавит БдААсар. Построим систему формул Й" путем замены в схеме алгорифма Й' всех точек буквами а.
Построим систему формул Юа путем замены в схеме ' алгорифма 6' всех букв алфавита А их двойниками, всех точек — буквами р с последующей заменой всех формул ; вида (1) — В ' формулами (2) а иВ Т1 с теми же В $; Зададим нормальный алгорифм к( в алфавите Б сокращенно записанной схемой ( и» вЂ” сс$ и$ — а5 $т! — БЧ 1(1- ()д ~ (15 — (15 $з) - $>1 а()в Вз„ [ 2(а где 5 и з) пробегают алфавит А. Покажем, что он удовлетворяет условию 1(1), 200 сОчетАния нОрмллг ггых АлгорнФНОВ ггл !ч Для этого заметим прежде всего, что между схемой алгорифма Й' и системой формул Я" имеется естественное взаимно однозначное соответствие, при котором формула системы Я", соответствующая данной формуле Р схемы Я', получается из Р тем же путем, каким вся система Й по- лучается из схемы Й' — заменой точек буквами а.
Прини- мая во внимание, что простые формулы вовсе не содержат гг>чек, а заключительные содержат ровно по одному вхож- дению точки — между стрелкой и правой частью,— убежда- емся в справедливости следующих утверждений: 2.2. Все формулы сисгтгемы Я' простые. 2.3. Всякая форлгула системы Я", соответствующая простой формуле схелгы Й', совпадает с этой формулой. 2.4. Левая часть всякой формулы системы ЙФ сов>га- дает с левой частью соответствукгщей формулы схемы 2Г, 2.3.
Правая часть всякой формулы системы Й'", соот- ветствующей заключительной формуле Р схемы Й, получа- ется из правой части формулы Р приписыванием слева буквьг и. Учитывая, что схема алгорифма Й' содержит формулу в — ° ъ, получаем 2.6. Систелга Й'" содержит формулу с пустой' левой частью. Принимая, далее, во внимание схему (3) алгорифма (ь., заключаем отсюда, что 2.7. Алгорифм чт замкнут.
Условимся, далее, называть двойником слова Р в алфа- вите А слово, получаемое из Р заменой каждой буквы ее лвойником. Двойник слова Р будем обозначать символом [Р Это есть слово в алфавите А. Очевидно, что (4) [л — — л, ($ гЕ, (5) [Рпд — ~ [Р— [г~— для любых слов Р н Я в А и для любой буквы ~~ этого алфавита. Очевидна также следующая лемма: 2.8. Всякое слово в алфавите А есть двойник одного и только одного слова в А. Заметим теперь, что между схемой алгорифиа гг и шк- темой формул РР>а также имеется естественное взаимно од- зт! КОМПОЗ>пцггя АЛГОРНФМОВ 20! ллоаначное соответствие. Формула системы РЭв, соответствующая данной формуле Р схемы 6', получается из Р заменой точек буквами [1, букв алфавита А их двойниками и, наконец,— если при этом получается формула вида (1) — за- ! г Рг меной ее формулой (2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
