markov_teorija_algorifmov (522344), страница 24
Текст из файла (страница 24)
Так как системы Х и У оканчиваются буквой у, слова У и У также оканчиваются ею [(15), (16), (!8), (19)]. Таким образом, буква у входит как в (7, так и в У. Поэтому имеются первые вхождения буквы у в слова (7 и У [3 23.6.3]. Пусть это будут вхождения ЙжуФà — первое вхождение буквы у в слово (7 и 6 ж у Ф Е вЂ” первое вхождение буквы у в слово У. Имеем (20) ауге(7 н (21) буЕ хг У Буква у не входит ни в 4], ни в 6, которые, таким обра- зом, являются словами в алфавите А. Имеем (22) Х Х Хул(]уГ [(15), (17), (20)], [(16), (17), (21)].
Здесь Л(] и Л6 суть слова в алфавите А. Если Х м.л, то имеем (24) уЛ х йУ [(17)], Х х улауг [(22)], У 'й- уЛ6Е [(23)] Отсюда ввиду того, что Лй и Л6 суть слова в алфавите А, следует, что Л(] есть первый член системы Х, тогда как Л6 есть первый член системы 1'. Но первые члены этих систем совпадают, в силу чего Лйл' Л6, и, следовательно, уЛ(лу является общим началом систем Х и У. Поэтому уль]у есть начало наибольшего общего начала Яу этих схимы 4 26] ]25 систем. Таким образом, в случае, когда Хя.л, улйу есть начало уЛ [(24)] и, следовательно, 1]у есть начало Л, что абсурдно. Пусть, наконец, Х 3~ Л. Так как у является первой буквой системы Х, эта же буква является первой буквой непустого слова Х [(22)], а потому и первой буквой слова Ху.
При этом, как мы знаем, Х является словом в алфавите Ау. Отсюда следует, что слово Ху является системой. При этом Ху.,а у, так как Х~'-Л. Система Ху .оканчивается атомом, т. е. существуют слово К в алфавите Ау н слово Я в алфавите А такие, что (25) Ху м. КЯу. Имеем (26) ХХКуцулауг [(22), (25)], (27) У ~ КуОулбуЕ [(23), (25)].
Таким образом, слово у]',]уЛ(]у входит в переводную систему Х схемы Х, а слово у]еуЛ6у входит в переводную систему У схемы Я. Здесь ]е, Ль] и Л6 †сло в алфавите А. Имеем поэтому Х; Е[-Ла 2: ]е)- Л6, откуда Лйм Л6 [4.7]. Следовательно, слово Кукул(]у является общим началом систем Х и У. Оно является поэтому началом их наибольшего общего начала Я~, т. е. слова КЯуЛ [(17), (25)]. Отсюда следует, что 4]у есть начало Л, что абсурдно.
Теорема доказана. Имеем 5.5. Всякая у-система в ал4авите А, входящая в переводную систему схемы Х, есть переводная система схемы Х [3 23.2.2], Докажем высказывание 5.6. Если Х вЂ” переводная система схемы Х, соединяющая ]е с Р, и Я: (е ], то Х ~Яу и Я я й. Пусть имеет место посылка материальной импликации 5.6. Тогда Я вЂ” первый член системы Х, а Я вЂ” ее последний член. уеду есть начало Х, т.
е. имеется слово (7 в алфавите Ау такое, что (28) Ххуф(7. !гл. и СЕМИОТИКА !26 у(7 есть конец системы Х [(28)], начинающийся буквой у и потому являющийся системой [3 24.1.2]. Если (7 ~ЕЛ, то у(7~:у и система у(7 имеет первый член Я 24,3.1], Пусть это будет слово 5 в алфавите А. Имеем (29) у(7 й у57У, где У вЂ” некоторое слово в алфавите Ау. Тогда Х о Яу5уУ [(28), (29)] и, таким образом, слово уС!75у, где Я и 5 — слова в алфа- вите А, входит в переводную систему Х схемы 2. Следо- вательно, 2: !!» — 5 вопреки нашему предположению о том, что 2:Я'] [4.7]. К этому противоречию мы пришли, предполагая, что (7 ~ЕЛ. Следовательно, (7 м. Л, и потому Х о Яу [(28)].
Отсюда следует, что Я вЂ” последний член системы Х. А так как единственным последним членом этой системы является )7 [3 24.3,1], имеем Я л.)7, что н оставалось доказать. Аналогично доказывается высказывание 5.7, Если Х вЂ” переводная система схемы Я, соединяющая с )с, и с: !е» вЂ” 'Р, то ХХуф7 !! ЯХР. 6. Мы будем говорить, что схема Я просто преобразует слово Р в слово Я, если существует переводная система схемы 2, соединяющая Р с Я. Запись (1) г: Р»=а будет означать, что схема 2 просто преобразует слово Р в слово !е. Как нетрудно видеть, высказывание (1) при любых данных 2, Р и Я является полуразрешимым. Имеют место следующие высказывания, в которых Я— схема, а Р и !7 †сло в алфавите А: 6.1. г: Р»=, [5,Ц, 6.2.
Если 3: Р» — 1~, то Я: Р»=Я [5,2]. 6.3. Если 2: Р»=«7 и Я: Я»=)г, то Я: Р»=)с [5.3, 3 14.3]. 6.4. Если Я: Р»=Я, то если 2: !)» — Я, то 2: Р»=)7 [6.2, 6.3]. 6.5. Если Х вЂ” переводная система схел!ы Я, соединяющая слово Р со словом 1;!, а 1' — переводная система схемы 2, соединяюи(ая слово Р со словом Р, то 2: !е ~= )с или 2: Я»=Я, »»»! схемы !27 Действительно, пусть Х вЂ” переводная система схемы Я, соединяющая слово Р со словом Д, н пусть 1' — переводная система, соединяющая слово Р со словом Р.
Тогда Р есть первый член как Х, так и 1', Я вЂ” последний член Х, а Р— последний член У'. Ввиду того, что первые члены переводных систем Х и У совпадают, Х есть начало У или У вЂ” начало Х [5.41. Допустим, что Х вЂ” начало У. Тогда ~ (2) УХХ(Х- У) [6 18.8,4]. у!еу есть конец Х, и потому , (3) ХХ(уеду- Х)Яу Ц 18.9,4], Имеем поэтому " (4) Ух(уеду Х)уеду(Х-У) [(2), (3)]. Таким образом, уеду(Х -У) есть конец У. у)«у также есть конец 1', так как )х — последний член У. Поэтому уеду есть конец уф (Х - У) или уеду(Х вЂ” У) есть конец Ру [617.4.10], Последнее, однако, невозможно, так как [[уеду(Х - У)тл )»», »; а [[Ру»вЯ.
Следовательно, уру — конец у!еу(Х - У). у есть конец слова у(Х - У) как при Хм У, так и при Х~ЕУ. Поэтому слово уеду(Х"-У) в алфавите Ау есть у-система в алфавите А. А так как зта система входит в переводную систему У схемы Я [(4)], она сама есть переводная система схемы Я. Ее первым членом является Я, а последним — лх, т. е. она соединяет Я с Я. Таким образом, имеем в данном случае 2; Я»= А!. Аналогично усматриваем, что в случае, когда У есть начало Х, будет 2: Я»=Я.
Таким образом, имеем 2: Д)=Р или 2: Р»=!'!, что и требовалось доказать. Используя обозначение (1), высказывание 6.5 можно сформулировать следующим образом: 6.6. Если 2: Р»=Я и 2: Р»=1«, то Я: Я~Я плп 2: Р~=Д. Имеем 6.7. Если Л: Ц»=)с, то если Я: Ц ~, то Я о Р. Это высказывание мы рассматриваем как усиленную имиликацию с полуразрешнмой посылкой «Я: Я»=)с» и разрешимым заключением. Раскрывая смысл этой усиленной импликации согласно 2 14.1, убеждаемся в ее истинности [5, 5].
Аналогичным образом имеем 6.8. Если 2: 1~~)7, то если 2: Я вЂ”.Р, то !е~~Р [3 14.1, 5.7]. 1гл. и . 5»з! СХ ЕМЫ 129 СЕМИОТИКА 128 7. Мы говорим, что Я естественно преобразует Р в Я, и пишем Я: Р!- Е 1, если Я: Р)=Я и 2: («а ]. Мы говорим, что Я заключительно преобразует Р в Я, и пишем 2: Р)= (е, если существует слово Я такое, что 2: Р~=К и Л: Я) — Я. 7.1. Если Л: Р ~ Я, то существует единственное слово )7 такое, что Я: Р)= а« и 2: 1(а! —.1Е. Действительно, пусть слова Я и Я таковы, что 2: Р г='и и Л: Я) — (е', а, с другой стороны, г: Р)=Е и г: Е)-.о.
Тогда 2: 1«)=Я или 2: Е)=Я [6,6]. Пусть, например, Я; Я)=5. Но по предположению также 2: Я )- ° Я, так что Я хЕ [6.8]. Случай 2: Е)=Я трактуется аналогично. Будем говорить, что Е есть предпоследнее слово для Р и ф, если Л: Р)=Я и Я: )та) — Я. Мы говорим, что Л перерабатывает Р в 1е, и пишем с: Р~Я, если Я: Р~=Я ] или Я: Р)= Я. 7.2. Если 2: Р)=Я ) и Я: Р)=Я, то Л: 1~~() ] [6.6, 6.7, 6.1].
Условимся писать Х: Р)=Я)- )7 вместо г: Р~() и г:Е1- ° )7 Докажем 7.3. Неверно, что (1) Х: Р~=Я1 и 2: Р~=.)7. Предположим, что оба высказывания (1) верны. Тогда верны следующие высказывания: (2) Я: Р~Р, (3) Я: Я~ и существует Е такое, что (4) г: Р)=Е и что (5) 72 Е)-.)7. Фиксируем такое 5, Имеем Л: Я)= Я или 2: 9 )= Е [(2), (4), 6.6]. Если 2: Я~=Я, то ввиду (5) ЗхЯ [6.8]. Если 2: Я~=Я, то ввиду (3) также Е'з'Я [6.7]. Итак, 8 о О.
Но тогда 2: Я ] и Я: Я ) — ° )т, что невозможно [4.7]. Теорема доказана. Мы будем говорить, что схема 2 праменима к слову Р, и писать ! 2(Р), если существует слово Я такое, что 2: Р=о «с. Докажем 7.4. Если !3(Р), ию существует единственное слово 9 такое, что Я: Р ~ Я. Существование 9 такого, что 2: Р=> Д, следует из определения !2(Р). Покажем, что такое Я единственно. Действительно, пусть Я: Р=>1~ "и 2: Р=>1«.
Тогда ввиду 7.3 2: Р)=Я ] и Я: Р)=Р, ] или 2: Р)= 1Е и 2: Р)= Я. В первом случае с: Р ~=Я и 2: Р~=Я. Следовательно, 2: 9)=)7 или 2: )7'„=Я [6.6]. Но Л: Я ! и 2: 1« 1, так что 0х)7 [6.7] Во втором случае 2: Р)=51- ° Я и 2: Р)=Т)- 1« для некоторыхЯИТ. Но тогда 2; Я~Т или 2: Т~= Я [6.6]. Если 2: Я)=Т, то, так как Я: Я 1- Я, 3 яТ [6.8]. То же самое равенство получается и тогда, когда Я: Т )= Я. Следовательно, 2: Я 1- Я и 2: Я )- Е. Но отсюда следует, что 1е'хат' [4.4].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
