markov_teorija_algorifmov (522344), страница 59
Текст из файла (страница 59)
Теорема 3.4 показывает, что для некоторого нормального алгорифма 9В, в А, проблема распознавания аннулирования слов в А, неразрешима. Теорема 3.2 послужит нам основой для доказательства некоторых дальнейших теорем невозможности алгорифмов. 4. Теоретико-множественный комментарий. Теорема 3.2 фактически означает, что множество слов в алфавите А„не аннулнруемых алгорнфмом дг)„неперечислимо. Тем более оно неразрешимо (теорема 3.3). Множество слов в А„аннулируемых алгорифмом 2В„также неразрешимо (теорема 3.4).
Но оно перечислимо. 3 52. Сложностной подход к проблеме распознавания применимости 1. Учитывая важность теоремы 5 48.2.4, мы дадим в этом параграфе еще одно ее доказательство, которое в известном смысле выявляет причину неразрешимости рассматриваемой в этой теореме проблемы. Доказательство будет основываться на особом подходе, развитом А. А. Марковым в его исследованиях *) по сложности алгорифмов. Подход этот заключается в следующем. Пусть мы хотим доказать неразрешимость некоторой нормальной массовой проблемы У, определяемой вербальным пре*) Основные результаты нзлогкены в работах 1161 н 1171. СЛОЖНОСТНОЙ ПОДХОД 3!9 5 аз) 3!3 ОСНОВНЫЕ ТЕОРЕМЫ НЕВОЗМОЖНОСТИ АЛГОРИЬМОВ !ГЛ.
Ч1 дикатом Р в алфавите А. Берем произвольное натуральное число У и рассматриваем слова в А с длиной, не превосходящей У. Таких слов имеется конечное число, и потому, как нетрудно сообразить, предположение о том, что не существует нормального алгорифма над А, распознающего среди этих слов те из них, которые удовлетворяют предикату Р, ведет к противоречию. Вполне возможно, что мы не будем знать, как построить такой алгорифм (ведь в общем случае всего лишь опровергается предположение о его несуществовании, а это, вообще говоря, не дает никакого способа его построения). Но, может быть, нам удастся доказать, что всякий такой алгорифм имеет сложность, т.
е. длину изображения *), не меньшую 7(У), где ! — некоторая неограниченная, т. е. принимающая сколь угодно большие значения, вычислнмая арифметическая функция. Тогда можно будет утверждать, что рассматриваемая проблема неразрешима. В самом деле, если бы существовал нормальный алгорифм, решающий эту проблему, то он, в частности, при любом У решал бы ее для слов с длиной, не превосходящей У. А тогда сложность этого алгорифма была бы больше !(У) при любом У, что невозможно ввиду неограниченности !. Таким образом, идея этого подхода заключается в том, чтобы пытаться аппроксимировать исходную нормальную массовую проблему и последовательностью „урезанных" проблем У ч (каждая из которых не может быть неразрешимой ввиду ее «конечности») так, чтобы минимальная сложность решения частичных проблем Уч оценивалась снизу некоторой неограниченной вычислимой функцией аргумента У.
Если этот план действий удастся реализовать, то тем самым будет установлена неразрешимость проблемы У. Намеченный подход мы теперь проиллюстрируем на простом примере рассмотрснной в 9 48 проблемы распознавания применимости алгорифма к исходному данному. Впервые пример алгорифма с линейной нижней оценкой сложности решения проблемы распознавания применимости опубликован в работе Я. М. Б а р з д и н я !1!. План нашего изложения восходит к дипломной работе В. А. Илюшкина, выполненной в МФТИ под руководством А.
А. Маркова и доложенной осенью 1967 г. на работавшем в то время под руководством авторов семинаре по конструктивной математике МГУ н ВЦ АН СССР. 2. Как и в предыдущих параграфах, А, и А, будут означать соответственно алфавиты ай н а11сд. Для нормальных ") Сн. 1 31.3. алгорифмов й в А, мы определим их изображения й" [9 42. Ц и записи й' [9 45.2]. Сложностью нормального алгорифма гзл в А, мы будем называть обозначаемое в дальнейшем символом совр! (й) натуральное число [йаг [ср.
9 31.3). Подобно утверждению 9 47.2.1, легко доказывается следующее утверждение: 2.1. Пусть У вЂ” натуральное число, а Т вЂ” нормальный алгорифм в А, такой, что для всякого нормального алгоРифма й в А, с сошр! (й) (У выполняется следующее условие: 2) применим к й' тогда и только тогда, когда й несамоприменим. Тогда совр!(6) > У. В самом деле, если сошр! (2)) (У, то 2) самоприменим тогда и только тогда, когда он несамоприменим. А отсюда, как мы уже видели это в доказательстве леммы 9 47.2.1, легко выводится противоречие, что и дает сагир! (л)) > У.
Читатель видит, что в данном случае снова моделируется «парадокс Рассела». Пожалуй, еще ббльшие ассоциации вызывает известный житейский «парадокс деревенского брадобрея»1 парикмахер, бреющий в данной деревне тех н только тех, кто сам себя не бреет, не живет в этой деревне. 3. Пусть теперь 1г — какой-либо нормальный алгорифм в А„и пусть е — буква, не являющаяся буквой алфавита А,. Рассмотрим в алфавите А,г нормальный алгорифм д), определенный следующей сокращенно записанной схемой; еэ— (1) $г — ° се« где литеральная переменная $пробегает алфавит А„а конструкция Сле имеет тот же самый смысл, что и в доказательстве теоремы о композиции *).
Легко может быть доказано (мы предоставляем это читателю) следующее утверждение: 3.1. Если Р— слово в А„то З(Р) определено тогда и только тогда, когда Сь(Р) ~'Л **). Пусть теперь )В означает перевод алгорифма З в алфавит А„[см. 9 41,6), определенный таким образом, что роли алфавитов А и Б играют соответственно А, и еде, а роль А,-лнтероидов, поставленных в соответствие буквам с, е( и г, ') Сн. с. !99. *") Как обычно, 5 (Р) М, Л означает здесь, что 5 (Р) определено и отлично от пустого слова. СЛОЖНОСТНОЯ ПОДХОД 321 320 ОСНОВНЫЕ ТЕОРЕМЫ НЕВОЗМОЖНОСТИ АЛГОРИФМОВ 1ГЛ. Ч! 'З 521 И играют слова ст(с, сгЫС и сг(гЫс.
Оценим сверху совр! (3) через совр! (6). Пусть схема алгорифма 6 состоит из я формул подстановок. Тогда число букв алфавита А, в схеме 6 равняется совр1 (6) — (2й+ 1). Схема алгорифма 6' содержит столько же букв алфавита А,. Но число формул подстановок по сравнению со схемой алгорифма 6 у нее увеличилось на единицу. Кроме того, в схеме 6' появились вхождения буквы е, число которых может доходить до у+1. При переходе к переводу алгорифма 6' буквы алфавита А, будут заменяться словами длины, не превосходящей 4. Буквы е заменятся словами длины 5. Таким образом, сложность перевода алгорифма 6' оценивается сверху числом 4 [совр! (6) — (2я+ 1)]+ 5 (й+ 1) + 2 (А+ 1) + 1, т.
е. числом 4 совр! (6) — й + 4. Нетрудно, кроме того, проверить, что первые три строки схемы (1) дают в сложность В вклад, равный 86. Таким образом, совр!(1В) ( 4 согор1(6) — й+ 90, и, значит, (2) совр!(гВ) ( 4 совр! (6)+89. 4. Покажем теперь, что 4.1. Если натуральное число У и нормальный алгорифлг 6 в А, таковы, что для всякого нормального алгооифма й е А, с совр1(й)(Ф: 1) 6(й') определено и 2) 6(й')хЛ тогда и только тогда, когда Й самоприменим, то совр! (6)) 1 89 ) — )у — '. 4 4 ' В самом деле, пусть Лг и 6 таковы, как указано в формулировке. Построим Ь и 1В способом, указанным в п.
3. Тогда для нормального алгорифма 111 в А, такого, что согпр1(й) ( У, лл(й') — а потому в силу 9 41.6.27 и 6(йа)— определено тогда и только тогда, когда й несамоприменим [3.1]. Так как ет — нормальный алгорифм в А„то (1) совр! (9) ) У [2.1]. Но тогда !ч' < 4 совр! (6) + 89 [(1), 3 (2)] совр! (6) ) — Аг — —, 1 89 4 4 ' что и требовалось доказать. 5. Пусть Š— нормальный алгорифм над алфавитом А, Ф вЂ” натуральное число. Будем говорить, что нормальный алгорифм 6 над А решает И-ограниченную проблему распознавания применимости алгорифма 6 к словам е алфавите А, если для любого слова Р в А такого, что [Рь(!ч', выполнены следующие два условия: 1) алгорифм 6 применим к Р и 2) 6(Р)м. Л тогда и только тогда, когда Е применим к Р.
Возьмем теперь алфавит А, и согласно видоизмененной ~' теореме об универсальном алгорифме [9 45.5,1] построим [ такой нормальный алгорифм егл над А,е, чтобы для любого нормального алгорифма Й в А, и для любого слова Р в этом алфавите выполнялось условное равенство (1) 4В(йвер) ае Я(р) Согласно теореме об объединении построим такой нормаль- ный алгорифм ьг над алфавитом А,е, чтобы для любого слова Р в А, выполнялось графическое равенство (2) Я'(Р) Х РеР. ! Определим теперь алгорифм !г как нормальную композицию алгорифмов !к и еа3: (3) $ (влВ о 1г), ] Тогда б.— нормальный алгорифм над А,е и для любого слова РвА, (4) В (Р) - 2В(3Т (Р)) [(3)] ае 2В (Рер) [(2)].
В частности, для любого нормального алгорифма й в А, (5) 3 (8!в) ЯВ (Йвейв) [(4)] й (й') [(1)]. Согласно теореме 9 41.6.27, может быть построен нормальный:алгорифм Е в двухбуквенном расширении алфавита А, (т. е., например, в алфавите А,) такой, что для любого слова Р в А, $ (Р) определено тогда и только тогда, когда определено 61 (Р), так что, в частности, алгорифм й применим к слову й', гдсй — нормальный алгорифм вА„тогда 11 А. А. Марков, Н.
Лг. Нагорной з22 основные теоремы невозможности клгогиомов !гл. в н епополнимыя АЛГОРИФм З2З $531 Действительно, если нормальный алгорифм 6 в А, решает У-ограниченную проблему распознавания применимости алгорифма Ю к словам в А„то, в частности, для любого нормального алгорифма Я в А, такого, что [Я'з ( й(, 1) 6(Я') определено и 2) 6(Я') лг Л тогда и только тогда, когда Й самоприменим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
