markov_teorija_algorifmov (522344), страница 56
Текст из файла (страница 56)
амоприменимым является, например, тождественный р ф ый алга ифм в алфавите ф А 12 28.4). Он применим ко всякому слову в А, в частности к своей записи. Несамоприменимым явл алгорифм в А (э 28.5). Он не применим ни к какому слову в А и, в частности, неприменим к своей записи. 2.1.
Невозл[оясен нормальный алгорифм в Л, применимый к записи какого-либо норл[ального алгор ф и только тогда, когда 2[ несамоприменим. е, предположим, что может быть построен В самом деле, п д ф ф. Покажем, что тогда он будет и само- такой алгорифм,з. и ин ип гедпсВо применим, и несамоприменим. А это по принципу ао аЬзцгйшп *) и будет означать, что он невозможен. Докажем сначала, что 9 несамоприменим. С этой целью допустим, что ф самопрнменим.
Тогда,~ применим к $4, н, значит, по условию ловию 94 есть запись несамоприменимого алгорифма, т. е.,О несамоприменим. Итак, нз допущения о самоприменимости 9 вытекает, что 9 несамоприменим. Но из этого допущения вытекает, разумеется, и салюприменил[ость 9. Зти два следствия противоречат друг другу, п инцнпу гедпсВо а[1 ВЬзцгдшп допущение го и м ействио самоприменимостн 9 неверно, т. е. алгорифм $ д тельно несамоприл[еним. Но отсюда немедленно получается, что 4) салюпримгним. В самом деле, по услов , по словию он применим к записи любого несамоприменимого нормального алгорифма в А, а значит, и к собственной записи.
Тем самым теорема 2.1 доказана. 3 ч а н и е. Невозможность алгорифма ф здесь, амечан оп ос: разумеется, озна ачает его несуществование. Возникает в р ? какой смысл мы долж лжны вложить в это отрицание. Рассмотре. иведенного доказательства показывает, что данное ние приведенн отрицание естественно трактовать как ре у [( Э 15.4). Ч ель, искушенный в математической логике, итат видит, что на заключительном этапе рассуждения о им вывод (средствами ннтуицнонистского исчисления высказываний) противоречия 1( (фе) 8 ) 1Я (гтт) % е) П ивеление к нелепости (лат.)... к ..
Си. к 15.4. Т зт>',, САМОПРИМЕНИМОСТЬ И НЕСАЫОПРИМЕНИЫОСТЬ зоб ЗОВ ОснОВные теоремы неВОзможности АлГОРНФмОВ Пл. у! из ранее полученного утверждения 16 (9') — = ) 1Ф ®з). Проведенное рассуждение повторяет схему так называемого „парадокса Рассела" ") и по существу представляет собой его теоретико-алгорифмическую версию. Более известна первоначальная — теоретико-множественная — версия парадокса.
Она заключается в следующем. Пусть 77 означает множество всех множеств, не являющихся элементами самих себя. Это значит, что для каждого множества Х имеет место утверждение: Х Е й' тогда и только тогда, когда Х ( Х. Следовательно, 1Т Б 77 тогда и только тогда, когда 1т ~ А'. А отсюда, как и в нашем случае, получается противоречие: одновременно и А' Е )т, и )т!Е 71. (Отметим, что в обоих рассуждениях мы не пользовались законом исключенного третьего, и, значит, он за окончательный результат ответственности не несет.) Следует подчеркнуть, что обе рассмотренные версии „парадокса" ничего противоречащего здравому смыслу в себе не содержат, так что сам термин „парадокс" здесь должен пониматься с надлежащей осторожностью.
Правда, в обоих случаях рассуждение в конце концов приводит к противоречию, но противоречие это извлекается из некоторого предполоясения: в первом случае — из предположения о существовании нормального алгорифма, а во втором — из предположения о существовании множества, удовлетворяющего определенному условию. В рассмотренных случаях „преодоление" парадокса состоит в констатации „неправомерности" этих предположений, т. е.
их ложности. Первая констатация дает нашу теорему 2.1. Вторая показывает, что в рамках теоретико-множественной концепции при определении множеств, рассматриваемых затем в качестве единых объектов, недопустима слишком большая свобода, что нельзя, не впадая в противоречия, любым образом объединять „объскты" в „множества", которые сами будут рассматриваться как „объекты". Запретив употребление множества Тс', мы избавим теорию множеств от одной конкретной трудности, но не создадим никаких надежных гарантий на будущее.
В самом деле, простой, хотя, Но>кот быть, и несколько вычурный способ задания множества )с с виду не противоречит исходной позиции !(антора, и „недопустимость" 1т обнаруживается лишь а роз(ег(ог(. з) Этот парадокс был иезавигимо открыт также Э.!(ермело. 3.
(1 доказанной только что теореме устанавливалась невозмои(ность нормального алгорифма в алфавите А, обладающего неКоторым специальным свойством. Предполагая теперь, что алфавит А содержит не только буквы а и Ь, но также буквы с и й, мы усилим теорему 2.1, утверждая невозможность обладающих тем же свойством нормальных алгорифмов над алфавшпом А,. Записи нормальных алгорифмов, о которых будет идти речь, по-прежнему Определены лишь для нормальных алгорифмов в А. Алфавит, состоящий из четырех букв а, Ь, с, й, мы обозначим через А,*). 3.1.
Если алфавит А является расширением А„то невозмозкен никакой нормальнь>й алгорифм м над А„применимый к записи нормального алгорифма 31 в А тогда и только тогда, когда 2( несамоприменим. В самом деле, допустим, что построен такой алгорифм й. Тогда к алфавиту А„буквам с, й и алгорифму ат применима теорема ~ 41,б,27, Согласно этой теореме может быть построен нормальный алгорифм зре в алфавите А„применимый к тем и только тем словам в А„к которым применим алгорифм й. Принимая во внимание, что А является расширением Ато построим естественное распространение ф алгорифма трз на алфавит А Ц 35.31.
Для любого слова Р в А, имеет место условное равенство ,т,(Р) = ~ (Р), показывающее, что алгорифм т> примениМ к тем и только к тем словам в А„к которым применим алгорифм 9а. Так как А, является расширением А„алгорифмы ф и й применимы к одним и тем же словам в А, и, значит, к одним и тем же записям нормальных алгорифмов в А.
Следовательно, 1з, как и Й, применим к записи нормального алгорифма 21 в А тогда и только тогда, когда алгорифм Я( несамоприменим. Вместе с тем ф есть нормальный алгорифм в А. Такой алгорифм, однако, невозможен (2.11. Невозможен, следовательно, н нормальный алгорифм ат над А, со свойством, указанным в формулировке теоремы 3.1, что и требовалось доказать. 4.
Со свойствами самоприменимости и несамоприменимости нормальных алгорифмов естественно связать массовые алгорифмические проблемы распознавания этих свойств. *) Разумеется, вместо букв а, Ь, с, е! можно было бы взять любые другие четыре различные буквы. 306 ОСНОВНЫЕ ТЕОРЕМЫ НЕВОЗМОЖНОСТИ АЛГОРИФМОВ !Г!! Ч! Д вЂ” $, где 5 пробегает алфавит Б.
Очевидно, что !Х) применим к Л и не применим ни к какому непустому слову в Б. Определим алгорифм ьг как нормальную композицию алгорифмов 33 и В: (!) Я (Цоф), ат есть нормальный алгорифм над Б 1(1), 3 З7.4.2) и, следовательно, над А,.
Для любого слова Р в Б ХХ (Р) л) (а! (Р)) ((1)1 и, в частности, (2) аат» (Йа) 2) (~ (2(а)) для любого нормального алгорифма Й в А. Согласно (2) для применимости й к записи Я' нормального алгорифма Й необходимо н достаточно, чтобы алгорифм 9 был применим к Я', а алгорифм 23 — к !Т(Я'). Но и случае применимости,т! к ВР $(Й') есть слово в Б, так Для каждого нормального алгорифма в алфавите А, заданного своей записью, можно поставить единичную проблему выяснения самоприменимости (несамоприменимости) этого алгорифма.
Всякому данному алфавиту А, являющемуся расширением алфавита А„соответствует класс таких единичных проблем. Каждая единичная проблема этого класса характеризуется некоторым словом в алфавите А,— записью нормального алгорифма, о котором идет речь в единичной проблеме. Соответствующая нормальная массовая проблема будет состоять в построении нормального алгорифма над алфавитом записей Л„ применимого к записи Й' любого нормального алгорифма Й в А и перерабатывающего Й' в Л тогда и только тогда, когда Й самоприменим (несамоприменим).
Мы покажем сейчас, что эта массовая проблема неразрешима, если А является расширением А,. 4.1. Если А является расширением А„то невозможен нормальный алгорифм $ над А„удовлеп!воряющий следующему условию: каков бьс ни был нормальный алгорифм Й в А, Х) тогда и только тогда перерабатывает Я' в Л, когда Й несамоприл!енил!.
В самом деле, допустим, что построен нормальный алгорифм ф над А„удовлетворяющий этому условию. Пусть Б — его алфавит. Построим нормальный алгорифм !Х) в Б со схемой САМОПРИМЕНИМОСТЬ И НЕСЛМОПРИМЕПИМОСТ! 307 как,Б — алгорифм в Б. Поэтому )Б применим к 9(ВР) тогда и только тогда, когда ф (Й') ь Л. Таким образом, алгорифм ХХ тогда и только тогда применим к Й', когда,тз(ВХ') ~Л, т. е. когда алгорифм Я несамоприменим.
Такой алгорифм АГ, однако, невозможен, так как Л является расширением А, (З.1!. Невозможен, следовательно, и нормальный алгорифм Л1, удовлетворяющий формулированному в теореме 4.1 условию, что и требовалось доказать. В теореме 4.1 не требовалось даже, чтобы алгорифм а! был применим к записи любого нормального алгорифма в А. Требовалось лишь, во-первых, чтобы он перерабатывал в пустое слово запись всякого несамоприменимого алгорифма и, Во-вторых, чтобы Всякий нормальный алгорифм в А, запись которого $ перерабатывает в пустое слово, был несамоприменим. Теорема утверждала невозможность алгорифма 9 над А„удовлетворяющего этим условиям.
Теорема, разумеется, остается верной, если к условиям, налагаемым на т», добавить требование применимости к записи любого нормального алгорифма в А в соответствии с приведенной выше формулировкой нормальной массовой проблемы распознавания несамоприменнмости. Мы получаем, таким образом, следующее видоизменение теоремы 4.1, 4.2. Если А является расширением Л„то невозможен норл!альный олгорифм над А„применимый к записи Я' любого нормального алгорифма Я в А и перерабатывающий 9Р в Л тогда и только тогда, когда Й несил!оприменим. Нетрудно, далее, видеть, что в теореме 4.2 возможна замена слова «несамоприменим» словом «самоприменим», т. е. что имеет место и следующая теорема: 4.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
