markov_teorija_algorifmov (522344), страница 18
Текст из файла (страница 18)
В самом деле, при этих условиях М([ха [6 !8.6.8], и потому существует начало 1' слова Х, удовлетворяющее условию (1) [2.1]. Так как М < [Х", имеем р" < [Ха и потому, согласно определению собственного начала, Р ~[Х и, следовательно, )',в Х. Таким образом, )' — собственное начало Х, что и оставалось доказать. У, Докажем 2.3. Если Ха«)'Х2, то )'мл и Лмл. Пусть Х к )'ХЯ.
Тогда [Хв~[ [Ха[2 Р.З] .Т Х [Х Р" [Ев [6 18,10 1 Ц, ' . откуда последовательно Р" [2» ХЛ [6 П.5.2], р" хл [6 п.б.з], [2»ХЛ [~ 17,6,3], )'л Л Р.б], галл р.б]. )гл. и семиотИКА вз Имеем далее 2.4. Если Х,,гЛ, то Х1 не есть начало У [2.31. 3. Проекцией слова Р в алфавите А на алфавит Б мы будем называть слово, получаемое нз Р выбрасыванием всех букв, не являющихся буквами алфавита Б. Проекцию слова Р на алфавит Б мы будем обозначать символом [Рв Более точно: [Лв ) [Рв$, если $ — буква алфавита Б, [РРс а ( [Р", если $ не есть буква алфавита Б. Эги равенства и будут служить индуктивным определением *) проекции слова на алфавит. С нх помощью легко доказываются два следующих высказывания: 3.1. Проекция слова в алфавите А на алфавит Б есть слово в проекции алфавита А *") на алфавит Б.
3.2. [Рдв Х[Рв [он. 4. Длина проекции слова Р на алфавит Б выражается следующим образом: [[рва При любом Р значение этого выражения может быть найдено. Имеем высказывания: 4.1. [[РЯваХ[[Рва[[(~ве (1.2, 3.2). 4.2. Если Ям. гсР5, то [[Рза([[теза [4.11. 4.3. Если 8 — буква алфавита Б, то [[бивак[. 4 4 [[Лва'дбЛ 4.5. Если алфавиты А и Б не имеют общих букв, то [Рв хЛ для всякого слова Р в алфавите А [3.1). 9 20. Умножение слова на натуральное число 1, Определим индуктивно а) произведение (Рх Л)) слова Р в алфавите А на натуральное число Ф с помощью равенств (1) (Р хЛ) — Л, (2) (Рхй)[) (Рхй)) Р.
е) См. замечание в 1 )7.3.2 (с. 89 — 70). е*) Алфавит А ирн этом рассматривается как слово (см, ! 2.7). Проекция его иа алфавит 6 снова является алфавитом. творвмл О ИАимвиьшвлт числя 89 Легко доказываются следующие высказывания. 1.1. (РХ Лг) есть слово в рассматриваемом алфавите А [индукция по й) при фиксированном Р1. !.2. (РхМЛг) Х(РхМ) (Рхй)) [(!), (2), индукцня по Ж при фиксированных Р и М). 1.3.
(Мй)хЕ) ~б(Мхй)(ФхЕ) [(1), (2), ~ 18. 10.11, индукция по Ь при фиксированных М и й)1. 1.4. ((Р х М) х Ж) Х(Р х (М х й))) [(1), (2), 1. 2, и иду кция по й) при фиксированных Р и М1. 1.5. (ЛхЖ)ХЛ [индукция по Ф, (1),(2)1. 1.6. ([хйг) ХЖ [индукция по й), (1),(2)1. 1.7. [($ х й))а Х й) [(2), ~ 19. 1(2), и иду кция по А)). 1.8. (М х ))7) 38 (А) х М) [индукция по А) при фиксированном М, 1.5, (2), 1.6, 1,31. 2. В дальнейшем вместо ($хй)), где 9 — буква, а й)— натуральное число, мы часто будем употреблять запись $н. $21. Теорема о наименьшем числе 1.
Докажем следующую лемму: 1.1. Всякое слово в алфавите 0[ имеет вид Я5, где Я— слово в алфавите О, а 5 либо пусто, либо имеет началом черточку (, Пусть й7 — слово в алфавите 0 [, Построим слово У, определив его следующим образом: (1) У =- (О х [()7» ). У есть слово в однобуквенном алфавите 0 [3 20.1.11, При этом (2) [УаХ[Я7а [(!) ~ 20 1 71 Согласно теореме 9 18.5.6 построим слова П, 5 и Т в алфавите О[ такие, что ,'' (3) ))7 лсЯ5, (4) Улс ЯТ и что 5 и Т взаимно просты слева. Так как У вЂ” слово в алфавите О, Я и Т также суть слова в этом алфавите [(4)!.
Имеем [)!а [5ьм Яь~[Ть [(2)— (4), 9 19.1,2), откуда (5) [5а ц [Та Ц 17,5.21. Если ТмЛ, то 5ХЛ [9 19.1.6,(5)! и осуществляется первая из возможностей, предусмотренных в лемме 1.1. »зп ТЕОРЕМА О НАИМЕНЬШЕМ ЧИСЛЕ 91 1гл. г! СЕМИОТИКА Если же Т ~ЕЛ, то Зф'Л [9 19,1,6,(5),] В этом случае не- пустое слово Т в алфавите О имеет началом букву О, а не- пустое слово Я в алфавите О[ имеет началом букву, отличную от О, ввиду взаимной простоты слева слов Ъ и Т [2 18.5.4].
Таким образом, в данном случае 3 имеет началом букву [ и осуществляется вторая из возможностей, указанных в лемме 1.1. Ввиду (3) и того, что )с есть слово в О, лемма 1.1 доказана. 2. Пусть Р— одноместный арифметический предикат, М вЂ” натуральное число. Будем говорить, что М есть наименьшее шсло, удавлетворяюшре Р, если М удовлетворяет Р, а всякое натуральное число, меньшее М, не удовлетворяет Р. Докажем следующую теорему о наименьшем числе: 2.1.
Каковы бы ни были разрешимый одномеспшый арифметический предикат Р и удовлепгворяюг«1ее ему натуральное число, может быть указано наименыиее число, удовлепгворяюи)ее Р. Пусть Р— разрешимый одноместный арифметический предикат, и пусть натуральное число )гг' удовлетворяет Р. Построим характеристический оператор предиката Р, определив его следующими равенствами: [, если М удовлетворяет Р, (1) ГМх —- О, если М не удовлетворяет Р. Здесь [Мх означает результат применения е) характеристического оператора предиката Р к числу М. Построим далее развертку предикппга Р, определив ее следующими рекурсивными равенствами ае): (2) [Л'=Л, (3) [М [е — [Ме [Мх Здесь [М' означает результат применения развертки предиката Р к натуральному числу М, Характеристический оператор предиката Р, очевидно, применим ко всякому натуральному числу и перерабатывает его в букву алфавита О[. Развертка предиката Р также применима ко всякому натуральному числу и перерабатывает его в слово в алфавите О[.
*) Разрешимость предкката г позволяет прв заданном М пай«к значение »того результата. ч') Снова см. замечание в 1 !7.3.2 (с. 69 — 70). Учитывая опыт, приобретенный читателем, мы в дальнейшем ограккчкм число ссылок па ато замечавке. Методом арифметической индукции легко доказывается равенство (4) [[Меа ХМ. Докажем, что для всякого натурального М и всякого начала Т слова [М' имеет место равенство (5) [[Т ° ~ Т. На время доказательства будем говорить, что натуральное число М правильно, если равенство (5) имеет место для всякого начала Т слова [М'.
Предикат «М правильно», оче' видно, разрешим. Докажем, что всякое натуральное число правильно. Пустое слово Л правильно [9 18.2.3, 4 19.1(1),(2)]. Допустим, что слово М правильно, и докажем, что тогда и слово М [ правильно. Пусть Т вЂ как-нибудь начало слова [М [', т. е. слова [М'[Мх. Так как слово [Мх однобуквенно, слово Т либо является началом слова [М', либо совпадает с [М'[М" [9 18.1.2]. В первом случае равенство (5) имеет место, так как М правильно. Во втором случае это равенство также : имеет место, так как в этом случае [Т' л:[[М г[[Мх> Ц 19,1.2] хМ) [(4) (1)] и потому [[Тге чг [М [е ~ [М [Мх [(3)] я. Т. Применяя метод арифметической индукции, заключаем, что всякое натуральное число правильно.
Завершим теперь доказательство теоремы 2.1. Так как [Лг[' есть слово в алфавите О[, к нему применима лемма 1.1„в силу которой существуют слова )с и 5 такие, что (6) [г)) [е чг )'>Я причем )с есть слово в алфавите О, а Ь' либо пусто, либо имеет началом букву [. Покажем, что длина слова )с есть искомое наименьшее число, удовлетворяющее предикату Р. Так как Ф удовлет- 92 самиотикА 1гл. и воряет предикату Р, имеем (7) [А(х.в ! Значит, (8) )гЯ лГ[Лее [Фх [(6),(3)] й [Фе! [(7)]. Следовательно, 115 не есть слово в алфавите 0 в отличие от )г, Поэтому 5КЛ и, согласно альтернативе для Я (5 л.Л или 5 имеет началом !), 5 имеет началом ], т. е.
существует слово и такое, что (9) Ях! и. Имеем поэтому [57! х й ! и [(6), (9)]. Таким образом, Р ! есть начало [М!'. По доказанному выше отсюда следует, что (10) [[Хе (де о,~;> (, С другой стороны, [Р! ' И'!' Б 19.1.2] (11) - [[)~ [[Р [(3)]. Таким образом, (12) г(ЮГ[[5"[Рзх [(10), (11)]. Здесь [[)гех — однобуквенное слово.
Следовательно, [[)саха ! [9 17.4.Ц, а это означает, что натуральное число [)г~ удовлетворяет предикату Р [(1)]. Остается доказать, что никакое меньшее число не удовлетворяет Р. Пусть натуральное число Е таково, что Е ([Рз. Тогда существует собственное начало 1' слова Р такое, что (13) [1"' 72Е [4 !9.2.2]. Существует Т такое, что (14) )с л УТ, 4 22! ПАРЫ СЛОВ 93 7' ~Г Л, так как 1' ~Г )с. 1' и Т суть слова в алфавите О, так как )с †сло в этом алфавите.
Так как Т ~ГЛ, существует слово и такое, что (15) т2:ои. Имеем [й) (е а рЯ [(6)] х УТЯ [(14)] ~г уОиЯ [(15)] Таким образом, г'0 есть начало слова [М!'. Поэтому 1ОХ[[~ Осе ."2[[1" !' [э 19.1(2)] .г [[)еае [[ ах [(3)] Здесь [[)'ех — однобуквенное слово.
Следовательно, [[ хО Ц 17.4 1], т. е. [Ех Х О [(13)]. Это означает, что Е не удовлетворяет предикату Р, что и требовалось доказать. $22. Пары слов 1. В этом параграфе мы будем по-прежнему считать фиксированным алфавит А и, если не оговорено противное, будем подразумевать под «словами» слова в алфавите А. Кроме того, мы фиксируем букву а — произвольную букву, не являющуюся буквой алфавита А. Буквы Р, Я, 21 и 5 мы будем применять как вербальные переменные в алфавите А, а буквы Х и У вЂ” как вербальные переменные в алфавите Аа. Докажем высказывание 1.1.
Если РаХл.Яау', то Рл.Я и Х2с1'. Пусть РаХ л. 9а)'. Тогда Ра н Д суть начала одного и того же слова, и потому Ра есть начало Я или Я есть начало Р [9 18.4.6]. Но Ра ие есть начало Я, так как Я, будучи словом в алфавите А, ие содержит букву а. Таким образом, 9 есть начало Р. Аналогично усматриваем, что Р есть началом. Следовательно, Р о Я. Отсюда далее следует, что Х 2 1' [$ 17.5.2]. Аналогично доказывается 1.2. Если Ха)с хе УеьЯ, то )с ~5 и Ха) . !гл.
и семиотикк 94 ВХОЖДЕНИЯ 95 $23! Из высказывания 1.1 следует высказывание 1.3. Если РоЯ Х !гс<Я, то Р 3: !Е и Д Х Я, 2. Слово Рс<й в алфавите Аа мы будем называть парой слов Р и )7 в алфавите А. Слово Р будем называть первым элемента»< пары Ра!«, а слово 2( — вторым элементом этой пары. В силу 1.3 и определения пары имеем 2.1. Две пары слов совпадают тогда и только тогда, когда совпадают их первые элементы и совпадают их вторые элементы. 3, В нашем определении пары слов буква а играет роль «знака препинания», отделяющего первый элемент пары от второго.
Разумеется, эту роль можно поручить и какой- нибудь другой букве е, лишь бы она не входила в алфавит А. Поступая таким образом, мы будем специально подчеркивать выделенный характер е и говорить ие просто о парах, а об е-парах слов в алфавите А. $23. Вхождения 1. Мы говорим, что слово Р входит в слово !е, если существует пара слов такая, что )7--первый элемент этой пары, Я вЂ” второй и что Я й.КРЯ. Мы говорим тогда также, что слово !г содержит слово Р. 1.1, Двуместный вербальный предикат (1) «Р входит в 1~» полуразрешим.
Это очевидно из определения данного предиката. Ввиду 1.1 импликации с посылками вида (1) могут быть рассматриваемы как усиленные. Докажем усиленную импликацию 1.2. Если Р входит в !г, то существует У такое, что Р есть начало У, а У вЂ” конец Фиксируем Р и !г. В развернутом виде импликация 1.2 выглядит следующим образом: 1.2.1. Если суи(ествуе2п пара слов )7аЯ такая, что (ем<«РЯ, то суи!ествует У такое, что Р есть начало У, а У— конец (с.
В силу нашего соглашения о понимании усиленных импликаций высказывание 1.2.1 означает то же, что и высказывание 1.2.2. Какова бы ни была пара слов )<с<Я, если СЕ72.24РЯ, то существует У ~пакое, что Р— начало У, а У вЂ” конец Высказывание 1.2.2 нам и надо доказать. Для этого нам надо уметь для любой пары слов !«аЯ устанавливать истинность материальной импликации <если !е о )7РЯ, то существует У такое, что Р— начало У, а У вЂ кон !е».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
