markov_teorija_algorifmov (522344), страница 60
Текст из файла (страница 60)
Изображения нормальных алгорифмов в алфавите А, суть слова в семибуквенном алфавите. Поэтому для любого такого алгорифма Й [Язв~9 [Й"з, т. е, [Й'з(9совр! (Я). Пусть теперь Я вЂ” нормальный алгорифм в А, такой, что - р! (Я) < ~ — ", ~ '). 9 совр! (Я) к ' Ж, Тогда н, значит [я(аа -. А1 Тогда: 1) 6(Я') определено и 2) 6(Я')мЛ тогда и только тогда, когда Я самоприменим. Следовательно, совр! (6) ) — ° ! — ~ —— ! Л'! 62 4 [Э~ 4 и потому сагир! (6) ) — ° ( — — 1) —— 36.
Ф вЂ” 222 что и требовалось доказать. 6. Таким образом, действительно, если бы проблема распознавания применимости алгорифма (6 к словам в ал'! Каакратные скобки означают здесь целую часть заключенного и ннх числа. и только тогда, когда определено Й (Я'), т. е. когда Й самоприменим. Покажем теперь, что справедливо следукяцее утверждение; 6.1.
Пусть г! — произвольное натуральное число. Каков бы ни был норма ьный алгорифм 6 в алфавите А„решающий 1ч' -ограниченную проблему распознавания применимости алгорифма 6 к словам в алфавите А„ совр! (6) ) — Тч — 22 — . 1 1 36 2' ' фавите А, была разрешимой, она решалась бы при помощи ' некоторого нормального алгорифма над алфавитом А,. А тогда, согласно теореме приведения [2 41.7.11, нашелся бы решаю- щий ее нормальный алгорифм 6 в А,. Сложность этого алгорифма, согласно 5.1, была бы больше любого из чисел зб' ~Ч вЂ” 222, что очевидным образом невозможно. 3 а м е ч а н и е.
Функция 1(Ж) =- — ° Л! — 22 — является, ! 1 36 2 таким образом, „нижней оценкой" сложности проблемы распознавания применимости алгорифма Е. Интересен вопрос о „верхней оценке" сложности этой проблемы для произвольного нормального алгорифма. Характер ее усматривается из следующего предложения: 6.1. Каков бы ни был нормальный алгорифм 8 надалфавитом А„может быть указано такое натуральное число С, что для всякого натурального Ф можно привести к противоречию предположение о несуществовании норл1ального алгорифма 6 в алфавите А„решающего !ч'-ограниченную проблему распознавания применилзости Е к словам в алфавите А, и такого, зто совр1(6) (Л!+С.
По поводу доказательства этого утверждения см. Я. М. Барздинь [11 и Н. В. Петри [11. $ 53. Непополнимый алгорифм 1. Пусть А — какой-либо алфавит. Нормальный алгорифм Й над алфавитом А мы будем называть полным относительно А, если он применим ко всякому слову в А. Пусть Я и з — два нормальных алгорифма над А. В мы будем называть пополнением й относительно А, если: 1) к) полн относительно А и 2) всякий раз, когда Я применим к какому-либо слову Р в А, имеет место графическое равенство 6 (Р) Х й (Р).
Нормальный алгорифм Я над А мы будем называть пололнимым относительно А, если существует его пополнение относительно А. Рассмотрим следующие два примера: 1'. Пусть Я вЂ нормальн алгорнфм над А, не применимый ни к какому слову в А (нначе говоря, алгорифм, не 324 основныа ткопвмы нввозможностн длгопиамов (гл. ьч принимающий на словах в А ни одного значения). Легко видеть, что т)( пополним относительно А: его пополнением является любой полный относительно А нормальный алгорифм над А. 2'. Пусть  †нормальн алгорифм над А, принимающий на словах в А в точности одно значение, т. е. такой, что всякий раз, когда В применим к какому-либо слову Р в А, В(Р) 3: (;), где (г — некоторое фиксированное слово в А. Легко видеть, что В также пополним относительно А: его пополнением является всякий нормальный алгорифм над А, перерабатывающий любое слово Р в А в слово (г (такой «алгорифм-константу» нетрудно построить; см.
3 29.3). Естественно возникает вопрос: сколь долго будет сохраняться описанная в этих примерах ситуация? Ответ на него дает приводимая ниже теорема 1.1: оказывается, что уже среди алгорифмов, принимающих всего лишь два различных значения, имеются непополнимые. Итак, 1.1 *). Может бьопь построен такой нормальный алгорифм 6 над алфавитом А„что: 1) всякий раз, когда 6 применим к какому-либо слову Р в А„6 (Р) Х а или 6 (Р) ь Ь и 2) 6 непополним относительно А,. Доказательство. Построим, как это уже делалось в 9 52.5, нормальный алгорифм 0- над алфавитом А, так, чтобы для любого нормального алгорифма й в Ат выполнялось условное равенство (1) со» («озтз) и«( (О«(з) Пусть Ф вЂ” алфавит алгорифма $.
Легко видеть, что а и Ь являются буквами Ф. Обозначим символом 6, разветвляющий нормальный алгорифм йо,ма » Ц 30.1]. Согласно построению (2) 6,(а)ха (3) 6« (Р) Х Ь для любого слова Р в Ф, отличного от а. Искомый алгорифм 6 мы определим как нормальную композицию алгорифмов $ и 6,: (4) 6 (6 о$).
«) См. коммептзрпй в и. 3, з «3! напополнимый Алгопифм 323 От — нормальный алгорифм над Ф и тем самым над А„и для любого Р в А, имеет место условное равенство (5) 6 (Р) =6 (6 (Р)) [(4)] так что, действительно, если 6(Р) определено, то 6 (Р) Ха или 6(Р)~Ь [(5), (2), (3)]. Покажем теперь, что алгорифм 6 непополним относи- тельно А,.
В самом деле, предположим, что 6 пополним относительно А„ и пусть 2 †пополнен 6 относительно А,, Тогда 2 †нормальн алгорифм над А,, полный относи- тельно А, н такой, что если для какого-либо Р в А, 6 (Р) оп ределейо, то В (Р) Х 6 (Р). Пусть Л вЂ” алфавит алгорифма 2. Буквы а и Ь входят в Л. Обозначим символом 6« разветвляющий алгорифм 2(л, ь, [3 30.1]. Согласно построению (5) 6»(а)~Ь и (7) 6,(Р) о а для любого слова Р в Л, отличного от а.
Построим нормальный алгорифм Я, определив его как нормальную композицию алгорифмов В и 6,: (8) Я.. (6 одз), Я вЂ” нормальный алгорифм над Л и, значит, над А„н по- тому для любого слова Р в А, имеет место условное ра- венство (9) Я(Р)=6 (В(Р)) [(8)] Так как В полн относительно А„а 6, применим к любому слову в Л, условное равенство в (9) может быть заменено графическим: (10) Я(Р) 3С6,(В(Р)), так что алгорифм Я также полн относительно А,. В силу (10), (6) и (7) его значениями являются слова а и Ь, так что может быть построен вполне эквивалентный ему отно- сительно А, нормальный алгорифм Я, в алфавите А,.
Рас- смотрим слово Я; и покажем, что (11) 6 (яз) -~ о (яз) «) «) Напоминаем, зто графическое разлпчпе выражений предполагает пк осмысленность. НЕПОПОЛНИМЫИ АЛГОРИФМ 327 3РВ ОснОВные теОРемы неВОзможности АлГОРиФмОВ Пл. Тч Тем самым будет опровергнуто предположение о том, что В является пополнением Ю. В самом деле, В(Я,') определено, так как Я; — слово в алфавите А„ а В, по предположению, полн относительно А,. Кроме того, (12) В (!!11) . 6з (6 (%ТИ [(Ч вЂ” 6» (Яз (Яз)) [(1)1 Е(Я;)хЬ Е (Яз) зт 6 (Е (яз)) Но это равенство невозможно ни при Е(%,')л.а [61, ни при 6 (8Ц) Х Ь [(7)1. Следовательно, имеем (11), [(17), (18)1, что и оставалось доказать. 2. Теорема 1,1 выражает существенно более сильный факт теории алгорифмов, чем теорема 2 48.2.4.
Именно, имеет место следующее утверждение: и, по построению Я„ (13) Я (81з),~, % (Яз) так что (14) (М (Я;) = 6, (Я (811)) [(12), (! 3)1. Как уже отмечалось, % (%,') определено, причем Я (Я;) л а или %(Яз)зьЬ. Таким образом, в (14) знак «ж» может быть заменен знаком <л» и, кроме того, в силу (2) и (3) (15) 6, (Я (Я',)) х Я (Я,'), так что имеем (16) Е (Я') ~ Я (Яз) [(14), (15)1 и, значит, (17) Е (%,') Ха или (18) Но (19) Я (91,') ~ 6, (В (Я;)) [(10)1, и потому (20) Е (Я;) л.
6з (В (%;)) [(16), (19)1. Пусть теперь (21) 8 (Я,') ль В (Я;). Тогда 2,1. Пусть Й вЂ” нормальный алгорифм над алфавитом А такой, что проблема распознавания применимости Й к сло- вам в А разрешима. Тогда й пополнйм относительно А. В самом деле, пусть выполнены условия нашего утверж- дения. Тогда может быть указан такой нормальный алго- рифм В над алфавитом А, что для любого слова Р в Л будут выполняться условия (1) 56 (Р) и (2) 6(Р)ХЛ тогда и только тогда, когда !Й(Р). Возьмем какой-либо такой нормальный алгорифм 21 над А, что для любого Р в А будет (3) !6 (Р), и по теореме о разветвлении построим нормальный алгорифм (Й'Т'л)! 6), который обозначим буквой 2, л! является нормальным алго- рифмом над А и для любого Р в А (4) л)(Р) Й (Р), если 6(Р)ХЛ, и (5) ;ы (Р) 2) (Р), если 6(Р) фЛ. Заметим, что если Р— слово в А и 6(Р) йЛ, то (Б) тд (Р) й Й(Р).
Действительно, в этом случае 1й (Р) [(2)1, и потому, в силу (4), имеет место (6). Покажем, что л: полн относительно А. В самом деле, пусть Р— произвольное слово в Л. Тогда в силу (1) !6(Р). Если 6(Р)ХЛ, то !л. (Р) в силу (6). Если же 6(Р) е-Л, то !л1(Р) в силу (5) и (3). Покажем теперь, что если Р в А и Ьй (Р), то л. (Р) м. Й (Р). В самом деле, пусть Р в А и !Й(Р). Тогда, согласно (2), 6(Р) ХЛ, а тогда имеет место (6). Таким образом, алгорифм аз является пополнением й относительно А, что и доказывает 2,1. Отсюда следует 2.2.
Если нормальный алгорифм й над алфавитом А непополним относительно А, то проблема распознавания применимости й к словам в А неразрешима. 323 ООНОВиые теОРемы невозможности ллгогиФмов ]Гл. Р! Существенность усиления усматривается из того, что 2.3. Могут бып|ь указаны алфавип| А и нормальный алгорифм Я над А такие, что проблема распознавания применимости 21 к славам в А неразрешил]а, но 21 пополнил| относительно А. Для доказательства достаточно взять какой-либо нормальный алгорифм Б в алфавите Б с неразрешимой проблемой распознавания применимости 5 к словам в некотором подалфавите А алфавита Б и построить нормальную композицию Й этого алгорифма с «аннулирующимь нормальным алгорифмом в Б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
