markov_teorija_algorifmov (522344), страница 23
Текст из файла (страница 23)
По теореме о наименьшем числе может быть указано наименьшее число, удовлетворяющее 6. Пусть это будет М. Так как М удовлетворяет 6, М является номером некоторого элемента 2 схемы Х, действующего на Р. Покажем, что 2 предшествует всякому другому элементу схемы Х, действующему на Р. В самом деле, пусть ((5' — элемент схемы Х, действующий на Р, и пусть й1' 1Г2. Имеем [й5'А,е [2А [5«24.5.41, т. е. [((Гьл1':М. [%'А ЕСТЬ НОМЕР ЭЛЕМЕНта СХЕМЫ Х, дЕйетнуЮ- щего на Р, т. е, [(»'А удовлетворяет предикату 6. А так как М есть наименьшее число, удовлетворяющее 6, и [)«'А:1г М, имеем М < [Я1«А, т. е.
[оь < [В'ь. Следовательно, 2 предшествует В' [9 24,6.31. Таким образом, 2 предшествует всякому другому элементу схемы Х, действующему на Р. 1 251 схемы 119 Единственность элемента схемы Х, действующего на Р н предшествующего всякому другому элементу схемы Х, действующему на Р, вытекает из высказывания 9 24.6.5. Мы будем говорить, что элемент 1' активен на слове Р в схеме Х, если )л — элемент схемы Х, 1' действует на Р и предшествует всякому другому элементу схемы Х, действующему на Р.
Следующее высказывание является перефразировкой высказывания 4.1: 4.2. Если схема Х действует на слово.Р, то имеется единственный элемент, активный на Р в Х. Результатом действия схемы Х на слово Р мы будем считать результат действия на Р элемента, активного на Р в Х. Легко доказывается высказывание 4.3. Результат дейсп5вия схемы Х на слово Р определен тогда и пюлько тогда, когда Х действует на Р.
Он тогда является словом в алфавите Л. Мы будем говорить, что схема Х переводит слово Р в слово 1г, если 1г есть результатдействия схемы Х на слово Р. В дальнейшем запись (1) Х: Р))-(г будет означать, что Х есть схема и Х переводит слово Р в слово Я. Как нетрудно видеть, трехместный вербальный предикат (1) разрешим. Очевидно следующее высказывание: 4.4. Если Х: Р й- 1~ и Х: Р ))- Р, то Я х)«. Мы будем говорить, что схема Х просто переводит слово Р в слово Я, если Х переводит Р в Я и ядро элемента, активного на Р в Х„есть простая формула подстановки; мы будем говорить, что схема Х з ключительно переводит слово Р в слово 1г, если Х переводит Р в Я и ядро элемента, активного на Р в Х, есть заключительная формула подстановки.
В дальнейшем Х: Р) — Я будет означать, что Х просто переводит Р в 1',1; Х: Р)- ° 1~ будет означать, что Х заключительно переводит Р в Ввиду того, что ядро всякого элемента схемы Х есть ее член и, следовательно, является формулой подстановки, имеем 120 1гл. и СЕМИОТИКА 1 2»1 схемы 4.5. Если Х; Р й- 1е, то Х: Р 1- 1'! или Х; Р 1- ° (~ [2,11. Имеем также 4.6. Если Х: Р 1- (е', то неверно, что Х: Р) — 1е, [2,21. В дальнейшем запись (2) Х: Р-) будет означать, что схема Х не действует на слово Р. 4.7.
Каковы бы ни были схема Х и слово Р, имеет место одно и только одно из следующих трек утверждений: а) существует единственное слово 1е такое, что Х: Р! — !',1; б) существует единственное слово Д такое, что Х: Р1 — Я; в) Х: Р). Имеем далее 4.8. Если У вЂ” единственный действующий на Р член схемы Х, то 1' активен на Р в Х. 5. Будем говорить о у-системе Х в алфавите А, что она есть переводная система схемы Я, если для любых Р и Я имеет место материальная импликация «если уРуОу входит в Х, то о: Р)- 1Е». Нетрудно видеть, что предикат «Х — переводная система схемы Я» разрешим.
Тривиально верно высказывание 5.1. уРу является переводной системой схемы Я, соединяющей Р с Р [3 24.31. Легко доказывается 5.2. Если о: Р) — Я, то уРуОу — переводная система скемы Я, соединяющая Р с 1е. Докажем теорему 5.3. Если переводная система Х схемы 2 соединяет Р с !',1, а переводная система У схемы о соединяет (Е с )«, то переводная система (1) Х) уеду(уОу- У) схемы с соединяет Р с Я.
Действительно, пусть соблюдены условия теоремы. Тогда Р есть первый член Х, 1;! — последний член Х и первый член У, 11 — последний член У. Это означает, что уру есть начало Х, у1Ер — конец Х и начало У, уйу — конец 1'. Ввиду этого осмыслены начальное дополнение (уЯу Х) и концевое дополнение (Яу -У), Они, как и системы Х н У, являются словами в алфавите Ау. Кроме того, имеем (2) (у1',1у- Х)у!',1уХХ Ц 18.9.4~, . (3) Жу(у()у-1')~У [% 18841 в силу чего Х есть начало, а У вЂ” конец слова (1), Поэтому слово уРу есть начало слова (1), а слово уйу — конец слова (1).
Отсюда следует, что буква у есть как начало, так и конец слова (1). Следовательно, слово (1) является у-системой в алфавите А, Р есть первый член этой у-системы„а Я вЂ” ее последний член. Иначе говоря, р-система (1) соединяет Р с )с. Остается доказать, что эта система является переводной системой схемы с, т. е. что для всяких слов Я и Т в алфавите А таких, что слово уЗуТу входит в слово (!), имеем с: Я! — Т.
Итак, пусть уЕуТу входит в слово (1), причем Я и Т суть слова в алфавите А. Имеем (уЬу-х) Руту У) .йиуеутуУ, 1де У и У вЂ” слова в алфавите Ау. Слова иуЯуТу и Х суть начала одного и того же слова [(2)1. Поэтому иуЯуТу есть начало Х или Х есть собственное начало иуЯуТу [8 17.4.51. В первом случае Х хиуЯуТуУ', где У' — слово в Ау. Но тогда уЯуТу входит в переводную систему Х схемы с, и потому с: Я 1- Т. Во втором случае иуЯуТу ль ХУ", где У' — непустое слово в Ау.
Следовательно, слова Х и иуЕу суть начала одного и того же слова, и потому Х есть начало иуоу илн иуду есть собственное начало Х. Кроме того, в этом случае У" я У'"у, где У'" — некоторое слово в Ар, и, значит, Урвут.и ХУ'". Допустим, что ифу есть собственное начало Х. Тогда Х Х иуЕуи', где У' — непустое слово в Ау. Так как последней буквой системы Х является у, то У я.и"у, где и"— слово в Ау. Таким образом, Х я иуЯуи"у, и потому иубуТ я. Уу5уи"уУ"'. Отсюда Т м У уУ'", что невозможно, так как Т вЂ сло в А.
Следовательно, Х есть начало иуЯу, и потому (4) иузух Хйг для некоторого Ф'. Следовательно, иуорТуУ я Х)УТуУ. Но ирЯрТуУ есть наша система (!). Значит, (у(~у- Х) у~у (у()у - У) и ХУРТуУ. !гл, и 1зг $251 семиотика СХЕМЫ 12З Ввиду (2) это равенство может быть записано следующим образом: х(уоу- У) — хрутуУ, и потому (5) (у(7у - У) х РУТуУ [4 17,5.21.
у5у и )У суть концы одного и того же слова [(4)1. Поэтому у5у есть конец Я7 или %' — конец 5у. В первом случае имеется слово 11 в алфавите Ау такое, что (8) ЧУ Х 1175у. Имеем тогда 1 —. уоуУРТуУ [(3), (5)1 л. ЯЯу5уТуУ [(б)1 и, таким образом, у5уТу входит в переводную систему У схемы л. Поэтому имеем в данном случае Я: 51 — Т. Рассмотрим второй случай, когда Ю' — конец 5у. Если %' ь Л, то (7) х х иу5у [(4)1 (8) (уф — У) л. ТуУ [(5)~. Поэтому имеем (0) иу5ух(у()у- х) уоу [(7), (2)1, и потому 5л 1',1 [(0), ~К17.5.1, 8 22.\,21. Имеем, следовательно, У л.у5у (Яу У) [(3), (1О)] — у5утуУ [(8)1. Таким образом, в данном случае слово у5уТу входит в переводную систему У схемы Л, в силу чего л: 5 ) — Т.
Пусть теперь %':ф Л. Тогда ввиду (4) у есть последняя буква слова %', т. е. имеется слово 6 в алфавите Ау такое, что (11) Ю' х6у. Имеем (12) иу5х Х6 [(4), (11)1 х(у х) у6 [Р 18.0.41, ввиду чего уО есть конец 5 или 5 есть конец 6 [Ц 18.4.10]. Но у6 не есть конец слова 5 в алфавите А. Таким образом, 5 есть конец О, т. е. имеется слово Г в алфавите Ау такое, что (13) 6 ХГ5. Имеем иу —. хг [(12), (13), % 17,5.11, в силу чего слово Г пусто или имеет последнюю букву у. Имеем далее (уеду — У) У'. 6уТуУ [(5), (11)1 :. Г5утуУ [(13)1 и, следовательно, 114) У к удуГ5 утуУ [(3)1.
В силу равенства (14) слово у5уТу входит в У в обоих возможных здесь случаях: когда Гл.Л и когда у — послед- няя буква слова Г. Следовательно, Л: 5) — Т и в данном случае. Теорема 5.3 доказана. Докажем теорему 5.4. Если первые члены переводных систем Х и У схемы Я существуют и совпадают, то Х есть начало У или 1' — на- чало Х, Пусть выполнено условие теоремы, и пусть Р— общий пер- вый член переводных систем Х н У схемы Х.
Тогда уРу есть общее начало систем Х и У. Пусть )У вЂ” единственное наиболь- шее общее начало систем Х и У, которое существует согласно Э 18.5.9. Пусть и н У вЂ” взаимно простые слева слова в алфа- вите Ау такие, что (15) х:. )уи и (16) УХ )УУ.
Они существуют согласно э 18.5.8 и определению наибольшего общего начала. Слово уРу есть начало 14' Ц 18.5.10~, у входит в (У, и потому существует последнее вхождение у в )4'. Пусть это будет вхождение Х2КуФЛ, где Г. и Л— ]Вв семиотикл ]гл. и слова в алфавите Ау. Имеем (17) Хул лг Ф'. При этом у не входит в Л, так как Хжужл — последнее вхождение буквы у в слово Ф'.
Следовательно, Л есть слово в алфавите А. Если (7ХЛ, то Х есть начало 1' [(15), (16)] и доказы- вать больше нечего; если УХЛ, то У есть начало Х [(15, (16)]. Остается предположить, что (18) (] ~Л и (19) Ух-л, Однако это предположение мы приведем к абсурду.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
