markov_teorija_algorifmov (522344), страница 55
Текст из файла (страница 55)
Пусть, в самом деле, Я вЂ” нормальный алгорифм в Л, Р— слово в этом алфавите. Тогда (3) Зг,ь(Я'ЬР) о Я' Ц 29.4.61, (4) й?г.ь(Я»ЬР) мр [9 29 4 7), ?31 (2(»ЬР) ж ~ (Вг, ь (Х>оЬР)) Ц 37 4 31 кЯ« [(3), 3(1)1, Я (Я»ЬР) о Я»ЬР [(2), (6), (4)1, Ы (Й'6Р) П (Ь (Я'ЬР)) [Ь 37 4,31 П (Я«ЬР) [(6)! Я (Р) [9 42,1(2)1, что и требовалось доказать. ГЛАВА У! ОСНОВНЫЕ ТЕОРЕМЫ НЕВОЗМОЖНОСТИ АЛГОРИФМОВ й 46. Понятие о массовой алгорифмической проблеме в 1. Пусть А - — какой-либо алфавит, а Р -- одноместный вербальный предикат в нем.
С каждым отдельным словом Й Х в А естественным образом связывается следующая „единичная" проблема: «выяснить, удовлетворяет ли данное Х предикату Р», а со всем предикатом Р в целом — однопараметрическое семейство таких проблем. Каждая из этих единичных проблем требует утвердительного или отрицательного ответа на поставленный вопрос, так что возникает естественная проблема разыскания единого общего метода (алгорифма), позволяющего находить правильное реп?ение любой нз единичных проблем рассматриваемого семейства.
Эта последняя и представляет собой то, что в математике принято называть массовой алгорифмической проблемой. 2. Можно, например, в качестве А взять алфавит, состоящий из единственной буквы (, а в качестве Р взять предикат «число Х четно и совершенно». Тогда соответствующая алгорнфмическая проблема будет состоять в разыскании единого общего метода, который по любому натуральному числу позволяет сказать, является ли это число четным и совершенным. Легко видеть, что в данном случае искомый алгорифм может быть указан — например, с помощью разложения Х на простые множители. Легко также сообразить, что он даст утвердительный ответ по крайней мере в 24 случаях (в настоящее время известно 24 четных совершенных числа). Если мы в качестве Р возьмем новый предикат «число Х нечетно н совершенно», то требующийся в этом случае алгорифм также будет возможен.
! Правда, в настоящее время мы не сможем сказать, ответит ли он зо1 300 ОСНОВНЫЕ ТЕОРЕМЫ НЕВОЗМОЖНОСТИ АЛГОРИФМОВ [ГЛ. ТН МАССОВАЯ АЛГОРИФМИЧЕСКАЯ ПРОБЛЕМА утвердительно на поставленный вопрос хотя бы когда-нибудь, потому что неизвестно ни одного нечетного совершенного числа. Но этого от иас и не требуется. Можно также, условившись записывать пары натуральных чисел в виде слов в алфавите ~ Ж, интересоваться единичными проблемами о взаимной простоте каких-нибудь двух данных натуральных чисел.
Каждая из этих проблем формулируется как требование; «выяснить, являются ли данные натуральные числа Х и К взаимно простыми». Массовая алгорифмическая проблема, соответствующая семейству этих единичных проблем, будет состоять в разыскании единого общего метода, позволяющего узнавать для любых двух данных натуральных чисел Х и т', являются ли они взаимно простыми.
Эта массовая проблема, как известно, разрешима; ее решение может, например, состоять в применении алгорифма Евклида для разыскания наибольшего общего делителя к данным натуральным числам Х и г'; эти числа тогда и только тогда взаимно просты, когда их наибольший общий делитель, найденный в результате применения алгорифма Евклида, равен единице. 3. Ситуация существенно осложнится, если мы станем интересоваться массовыми алгорифмическими проблемами следующего типа. Фиксируется какой-либо алфавит А и нормальный алгорифм Я в нем, а в качестве г" берется предикат «алгорифм Й применим к слову Х».
В отдельных случаях мы, возможно, сумеем, основываясь на конкретных особенностях алфавита А и алгорифма й, разработать искомый метод, позволяющий распознавать те слова Х, к которым алгорифм й применим. Однако в оба~ем случае не приходит на ум никакого другого средства, кроме как пытаться выяснить, применим ли алгорифм Я к слову Х, путем прямого применения алгорифма к этому слову. Но этот „прямолинейный" метод, если алгорифм Я не применим к слову Х, как раз и не приведет нас к цели: как бы далеко мы ни продвинулись в процессе применения Я к Х, если этот процесс еще не оборвался, мы ничего сказать не в состоянии: может быть, процесс оборвется на следующем шаге, а может быть, он не оборвется никогда.
Возникает вопрос: нельзя ли — поскольку „прямой" метод не дает желаемого результата — пытаться решить эту задачу каким-нибудь другим, „косвенным" снособом? Один из основных результатов общей теории алгорифмов гласит— и мы это установим в 5 48,— что при надлежащем выборе азгорифма Я не только „прямой", но и никакой другой метод к желаемому результату не приводит: такой метод о:азываетсл попросту невозможным.
4. Разумеется, чтобы получить такого рода результат, неточный, расплывчатый термин «единый общий метод», Встречающийся в формулировке массовой проблемы, должен быть надлежащим образом уточнен. Его естественно уточнить как «алгорифм». Алгорифм этот должен давать правильный ответ «да» или «нет» на всякий вопрос, составляющий содержание какой-либо из единичных проблем рассматриваемого семейства. Это требование естественно истолковывать так: алгорифм должен быть применим к любому значению параметра, определяющего единичную проблему рассматриваемого семейства, и должен перерабатывать это значение в слово «да», если проблема решается в положительном смысле, и в слово «нет», если она решается в отрицательном смысле.
При этом алфавит, используемый для записи значений параметра, дополняется русскими буквами а, д, е, н, т (нужными для составления слов «да» и «нет») и «алгорифм» понимается как алгорифм над полученным таким образом алфавитом А. Нетрудно, однако, видеть, что в явном введении этих русских букв в сущности нет надобности. Чтобы в этом убедиться, надо лишь принять во внимание наличие алгорифмов Й и 9 в алфавите А, работающих следующим образом: й перерабатывает «да» в пустое слово, а «нет» в непустое слово; Ю перерабатывает пустое слово в «да», а всякое непустое слово в алфавите А в слово «нет».
Наличие этих алгорифмов дает возможность заменить формулированное выше требование, предъявляемое к искомому алгорифму, следующим требованием: алгорифм должен быть применим к любому значению параметра, Определяющего единичную проблему рассматриваемого семейства, и должен тогда и только тогда перерабатывать это значение в пустое слово, когда единичная проблема решается в положительном смысле. Принцип нормализации алгорифмов [5 27.6) дает, наконец, возможность еще более уточнить формулировку массовой алгорифмической проблемы. Согласно этому принципу искомый алгорифм, если существует, то нормализуем и, следовательно, вполне эквивалентен относительно рассматриваемого алфавита значений параметра некоторому нормальному алгорифму над этим алфавитом. При применении к значениям параметра этот нормальный алгорнфм работает так же, как первоначальный: он тогда и только тогда перерабатывает значение ЗО2 ОснОВные теОРемы неВОзможнОсти А4НОРиФМОВ [Глп ч! параметра единичной проблемы в пустое слово, когда проблема решается в положительном смысле.
Таким образом мы приходим к следующей постановке массовой проблемы для данного семейства единичных проблем. Требуется построить нормальный алгорифм над алфавитом значений параметра рассматриваемых единичных проблем, применимый ко всякому значению параметра и тогда и только тогда перерабатывающий значение параметра единичной проблемы в пустое слово, когда эта проблема решается в положительном смысле. Так поставленные массовые алгорифмические проблемы мы будем называть нормальныл[и л[ассовыми проблемами.
Принцип нормализации, очевидно, дает возможность утверждать, что всякая массовая алгорифмическая проблема сводится к нормальной массовой проблеме. Нормальная массовая проблема называется разрешил[ой, если фигурирующий в ее формулировке нормальный алгорифм может быть построен. Ряд нормальных массовых проблем естественно возникает в самой теории алгорифмов, Зто в первую очередь проблемы, связанные с применимостью нормального алгорнфма к слову.
В настоящей главе мы докажем неразрешимость некоторых проблем этого рода — невозможность искомых в них нормальных алгорифмов. й 47. Самоприменимые и несамоприменимые алгорифмы 1. Если алфавит А содержит более одной буквы, то, как уже было выяснено [Э 45], имеется простая возможность записывать схемы нормальных алгорифмов в А в виде слов в этом же алфавите.
К записи е(в какого-нибудь нормального алгорифма Й в алфавите А можно тогда попытаться применить этот же самый алгорнфм Й. Мы докажем в этом параграфе одну простую н почти очевидную теорему невозможности, связанную с применением нормальных алгорифмов к их собственным записям.
В дальнейшем она послужит нам основой многих менее тривиальных результатов. 2. Будем рассматривать алфавит Л, являющийся расширением алфавита А„т. е. содержащий латинские буквы а и Ь. Определим, как выше (ч 451, запись произвольного нормального алгорнфма в А. Она является словом в А, и, значит, в А. Будем говорить о нормальном алгорифме й в А, что он самоприменим, если он применим к своей записи. Будем $47 САМОПРИМЕНИМОСТЬ И НЕСАМОПРИМЕНИМОСТЬ ЭОЗ говорить о нем, что он несамоприменим, если он не применим к своей записи л егно могут быть построены как самоприменимые, так и мы в А. Самоприменесамоприменимые нормальные алгорифмы в .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
