markov_teorija_algorifmov (522344), страница 38
Текст из файла (страница 38)
11ринимая во внимание, что правые н левые части формул схемы ч) суть слова в алфавите А, убеждаемся и справедливости сггедугощих утверждений: 2.9. Все формулы сислгелгы 2>1(Р, ггрггсгпые. 2.10. Левая часть лсякои форлгулгя сисгпемы Т~ есть двойник левой части соответствующеи формульс схемы йг или равна а. Последнее имеет лгесто тогда и только тогда, когда левая чггг'пгь соответствующей формулы схемы й) пуста. 2.11. Правая часть всякои формулы системы ВВ, соответствующей простой формуле Р схелгы лг', есть двойник правой части формулы Р или получается из этого двойника приписываниелг слгво а.
Последнее илпеет лпгсгпо тогда и только тогда, когда левая чаыпь формулы Р пуста. 2.12. Правая часть всякой формулы системы Э"„, соответствующей заклгочитепьнои формуле Р схемы хс, получается из двойника правой' части формулы Р пргтисыванием слева слова г> или слова аг>. Второе имеет место пюгда и только тогда, когда левая часть формулы Р пуста. Имеем далее следующую лемму: 2.13.
Левая часть всякой форлгулы снспгемы Ргэа„содержит букву алфавигпа Аа. Это непосредственно следует из 2.10. гп(ы выясним теперь, что в применении к какому-нибудь слову Р в алфавите А алгорифм (л работает следующим образом; 1-й этан. чп. работает „за алгорифм Я'". Выполняются последовательно все преобразования, требуемые алгорифмом й. При этом применяются формулы системы Й". Этап заканчивается, если алгорифм Й применим к Р, причем, однако, в результате имеем не Й(Р), а слово, получаемое из Й(Р) посредством вставки буквы я, „выскакивающей" на последнем шаге 1-го этапа. 2-й этап.
Буква а „бежит" влево к началу слова. Применяются формулы, представляемые 1-й строкой схемы (3). В результате получается аэ! (Р). 3-й этап. Буква сг „переводит" соседнюю с ней первую букву слова Й (Р) в двойник этой буквы. Применяется 202 сОчетлния ИОРмАльных АЛГОРиФмОВ 1гл. ш одна из формул, представляемых 2-й строкой схемы (3) (Этап отпадает, если Й (Р) ~Л.) 4-й этап. Слева направо распространяется процесс замены букв алфавита А их двойниками. Применяются формулы, представляемые 3-й строкой схемы (3). В результате получается слово а [й (Р) (Этап отпадает, если [21(Р) <1.) 5-й этап.
6 работает „за алгорифм 9'", но в алфавите чвойников А и с буквой а, приставленной к преобразуемому слову слева. Применяются формулы системы Жз„. Этап заканчивается, если алгорифм х) применим к слову й(Р), причем в результате имеем слово, получаемое из [2) (й (Р)) путем вставки буквы (1 и присоединения слева буквы и. 6-й этап.
Буква [з „бежит" влево до буквы а. Применяются формулы, представляемые 4-й строкой схемы (3). В результате получается а(1 [х) (Й (Р)) 7-й эта и. Буква [) „переводит" соседнюю с ней первую букву слова [2)(й(Р)) в первую букву слова 1В(й(Р)). Применяется одна из формул, представляемых 5-й строкой схемы (3).
(Этап отпадает, если 2)(Й (Р)) цЛ ) 8-5 этап. Слева направо распространяется процесс замены двойников букв алфавита А самими этими буквами. Применяются формулы, представляемые 6-й строкой схемы (3). В результате получается слово а()В(й(Р)). (Этап отпадает, если [В(й(Р))л(1.) 9-й и последний этап. Слово а1 исчезает. Применяется 7-я строка схемы (3), являющаяся заключительной формулой. Весь процесс на этом заканчивается, и его результатом является слово 2) (Й (Р)). Из этого описания работы алгорифма 6 видно, в чем состоит смысл введения двойников букв алфавита А. Они понадобились для того, чтобы, переводя схему алгорифма 9' в алфавит двойников, получить возможность так объединить в одну схему схемы обоих данных алгорифмов, чтобы они при этом не мешали друг другу.
Последующие леммы составляют точное математическое оформление сделанного только что наглядного описания процесса применения алгорифма 6. 2.14. Если Й': Р )- Я, то 6: Р ) — Я. Пусть, в самом деле, Я':Р) — (). Левые части форм л подстановок алгорифма 6, представляемых первыми семью строками схемы (3), не входят в Р, так как каждая из них содержит букву алфавита Аа, Не входят в Р и левые зн КОМПОЗИЦИЯ АЛГОРИФМОВ 203 'части формул системы У„", также содержащие буквы этого 'алфавита [2.131. Ниже в схеме (3) стоят формулы системы Й", идущие в , том же порядке, что соответствующие формулы схемы алгорифма Я .
Рассмотрим формулу Р схемы й', активную ' на слове Р. Эта формула простая, так как Й': Р 1- 1,1. Со."гласно 2.3, Р встречается и в системе й как формула, соответствующая самой себе. Выше нее в схеме алгорнфма , й' стоят формулы, левые части которых не входят в Р. . Согласно 2,4 отсюда следует, что и в системе 01" левые , части формул, стоящих выше Р, не входят в Р. Принимая , ': во внимание, что левая часть формулы Р входит в Р, тогда . как левые части формул подстановок алгорифма 6, представленных первыми восемью строками схемы (3), не вхо' дят в Р, заключаем, что Р есть первая формула подста- : новки алгорифма 6 с левой частью, входящей в Р.
Алгорифм 6 в применении к слову Р предписывает поэтому ' подставить правую часть формулы Р вместо первого вхождения ее левой части в Р, т. е. он предписывает то же самое, что и алгорифм Я'. Следовательно, 6; Р )- Я, что и требовалось доказать. 2.15. Если 9Г: Р)- 9, то суи(ествуют такие слова )с но, что (6) 9~Ю, (7) 6: Р ',— Рао. Пусть, в самом деле, Я': Р) — ° 9. Как в доказательстве предыдущей леммы, мы убеждаемся тогда, что левые части формул подстановок алгорифма 6, представленных первыми восемью строками схемы (3), не входят в Р.
Рассмотрим формулу Р схемы алгорифма Я', активную на слове Р. Эта формула заключительная. Она, следовательно, имеет вид У 1', где У и г' †сло в А. Пусть б означает соответствующую формулу системы й". Тогда б есть формула У вЂ” а'г'. Как в доказательстве предыдущей леммы, убеждаемся, что б есть первая формула подстановки алгорифма 6 с левой частью, входящей в Р. 204 ОЧЕтАНИя ноРМАльНых ЛЛГОРИФМОВ Пусть [ГЛ. ГР (8) Ржижт — первое вхождение (7 в Р. Алгорифм 6 в применении к Р предписывает подставить правую часть формулы 6, т. е. аУ, вместо этого вхождения.
Так как 0 — простая ф имеем — простая формула, 6: Р 1- 1гаУТ. писыва С другой стороны, алгорифм й' в примене Р ает подставить вместо вхождения (8) правую часть формулы Р, т. е. У. Так как й': Р 1 — ° Я, имеем Я ~гРУТ. Полагая 5 УТ, Т, будем, следовательно, иметь (6) и (7), что и требовалось доказать. 2.16. 6: )7а5 ~с«Ю шимся в 31 и 32. Здесь удобно воспользоваться приемом, уже приме рименяв- 22 32. Сначала левой индукцией по )с мы доказываем более общее утверждение 6: 1;1)ссь5)=СраЮ, а затем полагаем в нем !'!А Л.
2.17. Если й':Р )- Я, то 6: Р)=а9. В самом деле, пусть й'; Р )- Я. Тогда существуют слова )7 и 5, удовлетворяющие условиям (6) и (7) [2.161. А, так как й' — алгорифм в А и й': Р 1 — 9. По- 6: Р ) — Ра5 [(7)] )= аЮ [2.16] :к с«1е [(6)]. Следовательно, 6: Р1=а~, что ~, ~ы и требовалось доказать. Доказывается индукцией по шагам работы алгорифма ' с использованием леммы 2.14. 2.19, если й': Р ~= Я, то 6: РР— -а«г. В самом деле, п сть й': у Й': Р~= Я, Тогда существует такое (9) Й': Р)=Р«, (!О) й': Р)- Я. з«1 КОМПОЗИЦИЯ АЛГОРИФМО«' Имеем поэтому й: Р)=Р [(0), 2.18] 205 )= аД [(10), 2.17).
Таким образом, 6: Р— с«1;1, что и требовалось доказать. 2.20. Если Р и Я вЂ” такие слова в алфавите А, что г6;Р) — 1,'1, то Й': Р) — 1,1. 2." В самом деле, пусть Р н 1,"« — слова в А, и пусть '(11) 6: Р) — Я. В силу замкнутости алгорифма й' [2 36,2.1), существует такое слово Т, что й'; Р) — Т илн й: Р'„- Т.
Во втором случае имелись бы, однако, слова )7 и 5 такие, что ф (12) 6: Р )- )7а5 [2,16]. Мы имели бы тогда 92А)га5 [(11), (12)], что невозможно, так как 9 — слово в А. Таким образом, ": (13) Й': Р(-Т, (14) 6; Р)- Т [(13), 2.14], (16) Т а д [(и), (14)], Й: Р)- д [(13), (16)], что и требовалось доказать.
2.2!. Если Р— слово в Л, то 6 просто переводит Р в некоторое слово. В самом деле, пусть Р— слово в А. Рассуждая, как в доказательстве предыдущей леммы, убеждаемся в существовании такого слова Т, что й': Р ) — Т или й': Р 1 — ° Т. В обоих случаях 6 просто переводит Р в некоторое слово [2.14, 2,16]. 2.22.
Если алгорифм 6 примснйм к слову Р в А, то алгорифм Й' также применйм к Р. В самом деле, пусть алгорнфм 6 применим к слову Р, и пусть 6(Р)м-(7. Тогда в силу замкнутости алгорифма б [2.7) имеем 6: Р(= (7 [2 36.1.3]. Поэтому существует слово У такое, что 6; Р)=У) — ° (7, и, значит, существует переводная система Х схемы алгорифма 6, соединяющая Р с У. Легко видеть, что У не является словом в А так как 6: У)- ° У [2,21]. Таким образом, первый член системы Х является словом в алфавите А, а последний ее член им не является. Арифметический предикат «член системы Х с номером Ф не является словом в АА очевидно разрешим. Поэтому на основании теоремы о наименьшем числе [2 21.2.1] 206 ООчетлиия ПОРА!Альных АЛГОРиФмОь ггл.
!ч существует член (Р' системы Х такой, что Ф' не есть слово в А, а все члены Х с меньшими номерами суть слова в А. Тогда система Х имеет внд У'йгс, где 1' †переводн система схемы алгорифма 0„ все члены которой суть слова в А. Первым членом )' является слово Р. Обозначим последний член )' посредством !7, Тогда 6; !4 »- )17. Ясно, что )' является переводной системой и для схемы алгорнфма 31' [2.20]. Поэтому !71': Р~О. Существует такое )7, что е(': ге'~ — )г' или Я': О»- ° )г. Первый случай, однако, невозможен, так как тогда было бы 6; ()»-)7 [2.14] и )гя.Ж'. Между тем )7 — слово в А, а Иг им не является.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
