markov_teorija_algorifmov (522344), страница 25
Текст из файла (страница 25)
Теорема доказана. 8. Докажем следующее высказывание: 8.1. Если 2: Р)=~, то существует единственная переводная система Х схемы 2, соединяющая Р с 9 и такая, что Х есть начало любой переводной системы схемы 2, соединяющей Р с 9. Действительно, пусть Л: Р)=Я. Тогда существует переводная система схемы 2, соединяющая Р с 9 (6]. Предикат «Х есть переводная система схемы 2, соединяющая Р с Я» разрешим. Поэтому в силу теоремы о наименьшем числе 5 А.
А. Марков, И, М. Нагораю« !зо СЕМИОТИКА [ГЛ. И [ь' ! ущ ствует переводная система Х схемы Е, соед- 8 212Ц с е щ г!, с наименьшей длиной. Пусть теперь У— , соедипроизвольная переводная система схемы Я, соединяющ Р ая есть начало У или У есть начало Х [5.4]. В силу выбора Х У не может быть собственным началом Х. Поэто Х ляется началом У оэтому явПусть Е: Р' !;!. чалом У, что и требовалось доказать. рится в 8.1, мы б ~=!;!. Переводную систему Х, о которой говоы будем называть естественной переводной системой, соединяющей Р с Я. Докажем 8.2.
Если 72 Р~=О 1 сое иняю Р с и Х вЂ” переводная система схемы 2 щая 9, то Х вЂ” естественная переводная си- 1 стема схемы 2, соединяюща Р с !г. Действительно, пусть Е: Р)=1;! ~, и пусть Х вЂ” переводная система схемы 2, соединяющая Р с ~~. Т я с ~~.
огда, в част)=1,) и, значит, можно построить естественную переводную систему У схемы 3, соеднняющ ю Р с ~~ [8.Ц. Покажем, что Х~У. щую с ~ц В самом деле, У соединяет Р с ~, и, значит, УАГУу!",!у для некоторого У. Кроме того, У' — начало Х, и потому что ~л'Л. Тогда, так как Х вЂ” система, последней буквой У является у, и, значит, у входит в У. Пусть Я Жу!К)Р— первое вхождение у в У. Тогда Я вЂ” слово в А и УлгЕ ЯГ.
— и у д Уу(гуйу)Р, и, значит, вХвходит слово 1~ )г, Я вЂ сло в А. Так как Х вЂ переводн система довательно, Уя.Л и ХХ схемы 2, 2: Я )-)т [51, что противоречит 2: Я ) [4.7!. С ч: .. ле- Х ~ У, что и требовалось доказать, налогично 8.2 может быть доказано выск азывание л~: )=)г )- ~ иХ вЂ” переводнаясистемасхем~Я, сое иняющая Р с Я, то Х вЂ” естественная переводная систе Мы будем говорить, что схема 2 просто преобразуе Р агав, если 2: Р)=1;! и объем естественной переводной системы, соединяющей Р с Я, равен л!1. Мы будем говорить, что схема 2 естественно и об азует Р в Я за !т' шагов, если 2: Р)= !г' ) н Я п осто п еобразует Р в !г за А! шагов.
Мы 6 ем го уд зорить, что схема г заключительно и еобразует Р в !г' ва У 'шагов, если Е: Р'= !г' и 2 шаг и осто и е р преобразует Р в то единственное [7.Ц слов и за (Лà — 1) для которого Е: РМЕ)- Я. слово 5 25! схемы !3! Мы будем говорить, что схема Я перерабатывает Р в Я за А! шагов, если 2 естественно преобразует Р в !е за Ж шагов или Я заключительно преобразует Р в Я за Ф шагов. Легко могут быть доказаны следующие четыре утверждения: 8.4.
Если Я: Р)= Я, то число й7 такое, что Я просто преобразует Р в (г за А! шагов, единственно [8.Ц. 8.6. Если Я: Р != !г 1, то число !У такое, что Е естественно преобразует Р в (г, единственно [8.4). 8.6. Если Я: Р~ Я, то число А! такое, что Е заключительно преобразует Р в !г за А! шагов, единственно [7.1, 8.41. 8.7. Если Е: РО0, то число )У такое, что Я перерабатывает Р в Я за Ж шагов, единственно [7.1, 7.3, 8.5, 8.61. Пусть Я(Р).
Символом (2:Р) мы будем обозначать то однозначно определенное натуральное число !Ч, за которое 2 перерабатывает Р в некоторое слово Я, Число (с: Р) мы будем называть числом шагов работы схемы с над словом Р. Докажем следующие два высказывания: 8.8. Если г: Р~), то Е перерабатывает Р в Р за нуль шагов. Действительно, пусть Х вЂ” переводная система схемы с, соединяющая Р с каким-либо словом Р. Тогда Я я Р н Х м уРу [5,61, Х вЂ” естественная переводная система схемы Е, соединяющая Р с Р, и объем Х равен единице.
Так как г: Р !, Я естественно преобразует и, значит, перерабатывает Р в Р за нуль шагов, что н требовалось доказать. 8.9. Если 2: Р )- Я и Е: !г~)7, то 2: Р~й и (2: Р) АГ х(2: а. Действительно, пусть выполнена посылка этой импликации. Тогда, в частности, Я: Р)=!!. Кроме того, Я: !г=орс. Следовательно, с: Я)= Я '! или г: Я Р= )т. В первом случае Е: Р ~= Я "!, причем если Х вЂ переводн система схемы Е, соединяющая (г с Я, то уРХ вЂ” переводная система 3, соединяющая Р с Е. Системы Х и уРХ суть естественные переводные системы, соединяющие Я и Р соответственно с Е [8.2~.
Поэтому (г!Р) х[урх ~[[х х((г:®х(2:а~. Случай Я: (г~= )с' трактуется аналогично со ссылкой на 8.3. Утверждение 8.9 доказано. 9, Мы будем иногда применять следующий метод индукции по переводной системе. Пусть Š— схема и Р— некоторый одноместный вербальный предикат в алфавите Ау. Чтобы 5А !зз СЕМИОТИКА 1гл и доказать, что всякая переводная система Х схемы 2 удовлетворяет предикату Р, мы доказываем, что: 1 ) всякая переводная система схемы Л, имеющая вид ТРТ, удовлетворяет Р; 2) для всякой переводной системы Х схемы Я и всякого слова О имеет место следующая импликация: «если Х удовлетворяет Р, Р— последний член Х и 2: Р) — Я, то система ХЯТ удовлетворяет Р».
Тогда всякая переводная система Х схемы Е, отличная от 7~ В самом деле, пусть нам даны схема Я и предикат Г. Пусть выполняются посылки 1) и 2). Построим одноместный вербальный предикат 6 в алфавите Ау: «всякое начало Х слова У, являющееся переводной системой схемы Л и отличное от у, удовлетворяет Р». Докажем, что всякое слово 1' в алфавите АТ удовлетворяет б. Для этого мы воспользуемся методом правой индукции по построению слова 1'. П всякое начало режде всего, пустое слово Л удовлетворяет 6 е , так как ло Х пустого слова не является переводной системой.
Пусть затем слово 1' удовлетворяет б, а $— у лфавита АТ. Покажем, что 1'$ тоже удовлет, а — какаяво ной воряет 6. Пусть Х вЂ” начало слова 1'5, являющееся п дной системой 2, и пусть Х е.у. Тогда ХХ Х ОЛ, где Х, я пере- является переводной системой, а Я вЂ” слово в А. удовлетворяет Р. Если Х, о у, то это вытекает из посылки 1) метода индукции по переводной системе. Пусть Х л у. д, Х»РТ, где Х, само является переводной системой. Далее, Х есть начало 1'$.
Значит Х есть начало У $. ели Х есть начало г', то Х удовлетворяет Р, так как г' удовлетворяет б. Рассмотрим случай, когда Х У5. Тогда Хаум. У$. Отсюда 5 хсу и ХД есть начало 1'. Поэтом Х есть у, начало 1'. Х, есть переводная система, во яет Р. Х~ отличная от Т. Так как 1' удовлетворяет б Х , то , удовлет- Р . ХХХ»Рфу и Х вЂ” переводная система. Значит, «.: Р )-Я. В силу посылки 2) слово ХДТ также удовлетвоуд влетворяет Р. Тем самым 1'$ удовлетворяет 6.
Следовательно, любое 1' удовлетворяет О. Теперь уже нетрудно показать, что имеет место утверждение, сформулированное в заключении описываемого нами метода индукции по переводной системе. В самом деле, пусть Х— переводная система схемы Л, отличная от у. Тогда Х удовле- схемы 1зз творяет б н, следовательно, всякое отличное от у начало Х, являющееся переводной системой схемы 2, удовлетворяет Р. В частности, в качестве этого начала можно взять и само слово Х. Таким образом, изложенный нами метод обоснован. 1О.
Другой вариант индукции, который в дальнейшем будет нам полезен,— это метод индукции по шагам работы схемы Я. Он заключается в следующем. Пусть Л вЂ” схема, Р— некоторый одноместный вербальный предикат в алфавите А и Р— слово в алфавите А. Мы доказываем„что: 1') Р удовлетворяет Р; 2') для любых двух слов )« и 5 в алфавите А таких, что Я: Р )=)«' и Я: )1 )- 5, имеет место импликацня «если Я удовлетворяет Р, то и 5 удовлетворяет Р». Тогда всякое слово )« такое, что Л: Р ~= Я, удовлетворяет Р. В самом деле, пусть заданы Л, Р и Р, для которых выполняются посылки 1') и 2'). Построим следующий одноместный вербальный предикат О со свободной переменной Х для слов в алфавите Ау: «если Х вЂ переводн система схемы 2, начинающаяся словом ТРТ н оканчивающаяся словом Т5Т, где 5— слово в алфавите А, то 5 удовлетворяет Р».
Мы докажем, что всякая переводная система Х схемы 2, отличная от у, удовлетворяет 6. С этой целью воспользуемся методом индукции, изложенным в п. 9. Если Х имеет вид ТРТ, то Х удовлетворяет О, так как Р удовлетворяет Р в силу условия Г). Далее, если Х ~ Х»ТКТ, Х удовлетворяет б и Л: Я 1- 5, то Х5Т удовлетворяет б.
Действительно, если Х начинается словом ТРу, то Я удовлетворяет Р, так как Х удовлетворяет б. А тогда 5 удовлетворяет Р в силу 2'). Это и означает, что Х5Т удовлетворяет б. Теперь докажем утверждение, сформулированное в заключении описываемого нами метода индукции по шагам работы схемы. Пусть х.: Р)=Я. Тогда существует переводная система Х схемы 2, соединяющая Р с К. Х начинается словом ТРТ и оканчивается словом ТКТ. Так как Х удовлетворяет 6, то )«удовлетворяет Р. 11.
Рассмотрим простой пример. Пусть Я вЂ” какое-нибудь слово в алфавите А. Слово Я является тогда заключительной формулой подстановки с пустой левой частью и с правой частью О. ура является системой с единственным членом Щ, т. е. схемой. Пусть Р— какое- нибудь слово в алфавите А. Формула ))б действует на Р, так как пустое слово входит в Р. Результатом действия рЯ на Р семиОтикА 134 ГЛАВА Н1 является результат подстановки слова !е вместо первого вхождения пустого слова в Р, т. е. слово ЦР. Поэтому уК~ Р)-:Е и, следовательно, 11.!.
уЩу: Р~ ОР. (Здесь Р и !Š— любые слова в алфавите А.) Аналогично, слово аЯ является простой формулой подста- новки с пустой левой частью и с правой частью !е. уаЯу являет- ся схемой. Пусть снова Р— слово в алфавите А. Формула де ствует на Р, так как пустое слово входит в Р. Результатом й аа действия н на этот раз является слово ЯР. Но теперь 11.2. уаЯу: Р) — 1;1Р, так как формула аЯ является — в отличие от р9 — простой.
Докажем 11.3. Если уаС1у: Р~=Я, то существует натуральное число У такое, что )«л1(ЯхЖ) Р. В оспользуемся методом индукции по шагам работы схемы [10]. В качестве Р возьмем разрешимый предикат «существует натуральное число А! такое, что 14 ~ (Я Х 14) Р», Легко видеть, что Р удовлетворяет Р (при 1»'~Л). Пчсть, далее, уаЯу: Р'!=Гт, уаЯу: )т 1-5 н )АА'х(!ехм)Р. Тогда 5 Х 9 14 [11.2], и, значит, 5 ~ !1 (!4 х М) Р м. (Я х М 1) Р [3 20], т. е. 5 также удовлетворяет Р, что и требовалось доказать. 11.4. Схема уаЯу не применима чи к какому слову Р в алфавите А. 1 Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
