markov_teorija_algorifmov (522344), страница 63
Текст из файла (страница 63)
Проиллюстрируем теорему 2.1 следующим примером. Рассмотренный в З 54.2 способ представления вычислимых вербальных функций позволяет „расположить" записи приведенных функций одной переменной в эффективную последовательность. Например, мы можем упорядочить записи по их длине, а при равной длине — лексикографически.
Можно, конечно, взять и какой-нибудь другой, „более хитрый" способ выписывания членов этой последовательности, лишь бы он допускал реализацию в виде нормального алгорифма. Утверждается, что в любой такой последовательности можно будет найти рядом стоящие записи двух равных (т. е. принимающих при равных аргументах одинаковые значения) функций.
В самом деле, без труда может быть построен вычислимый оператор (ь), переводящий всякую запись из этой последовательности в соседнюю и распространенный на записи остальных вербальных функций с учетом равенства их приведенным функциям. Согласно теореме 2.1 этот оператор имеет неподвижную точку, а тогда она найдется и среди функций построенной нами последовательности, что и требовалось доказать. Легко видеть, что записи равных функций найдутся не только рядом, но и на любом заданном расстоянии. Читатель, без сомнения, найдет и другие любопытные примеры.
й 56. Распознавание инвариантных свойств вычислимых вербальных функций В настоящем параграфе мы изложим теорему Успенского— Райса о неразрешимости проблемы распознавания нетривиальных инвариантных свойств вычислимых вербальных функций. Для конкретности мы снова будем рассматривать функции только одной переменной, иногда не оговаривая этого специально. Перенос на общий случай не составляет труда. 1.
Говоря о свойствах вычислимых вербальных функций, мы будем иметь в виду свойства их записей, т. е. фактически одноместные вербальные предикаты для слов в алфавите А,. Выражения «функция Я обладает свойством Р» и «запись функции Й обладает свойством Р» мы будем считать синонимичиыми.
Пусть Я и Э вЂ вычислим вербальные функции (одной переменной). Мы будем говорить, что Й и Э эквивалентны, и писать е( ж Э, если для любого Р в А имеет место условное равенство Й (Р) ж Э (Р). М Пусть Р— свойство вычислимых вербальных функций.
ы будем называть его инвариантным, если из того, что Й М им обладает, а Эжй(, следует, что Э также обладае Р. т ы будем называть Р нетривиальным, если могут быть указаны две такие вычислимые вербальные функции, что одна из них им Обладает, а другая не обладает. Имеет место следующее утверждение (В. А. Успен- с к и й 111 *) — Г. Р а й с 111), 1.1. Всякое нетривиальное инвариантное свойство Р вычислимых вербальных функций одной переменной нераз ре- |иимо в том смысле, что не существует нормального алгв о- рифма С над алфавитом А„применимого к записи всякой вычислимой вербальной функции одной переменной Й и пере- рабатывающего зту запись в пустое слово тогда и только тогда, когда Й обладает свойством Р, В самом деле, пусть Р— указанное в формулировке тео- ремы нетривиальное инвариантное свойство.
Покажем, что из предположения о существовании нормального алго- рифма 6 с указанными в формулировке теоремы свойствами вытекает противоречие. Действительно, пусть 6 — нормальный алгорифм над алфавитом А„проверяющий (в указанном выше смысле слова) наличие свойства Р у произвольной функции Й.
Пусть функция Я, обладает свойством Р, а функция Я, им не обладает, так что (1) 6 (Йз) а (2) 6 (Й,') ~ А. Построим два нормальных алгорифма 3, и 3, в алфа- вите А, так, чтобы для любого Р в А, выполнялись гра- фические равенства (3) 3 (Р) |2(з и (4) 3, (Р) ~Я». Затем по теореме разветвления построим нормальный алго- рифм (5) Е = (3, у 3,( 6). ') См. также В. А. У с и е и с к к й 121, с.
З|0, теорема 9. ВЫЧИСЛИМЫЕ ВЕРБАЛЬНЫЕ ФУНКЦИИ 1ГЛ. УН Непосредственно очевидно, что для любого слова Р в А„ [ ~Х1, если си (Р) тг Л [(5), (4)], ( )='[ Я;, ж(Р)-д Л [(5), (3)1, и если 9 применйм к Р, то 6 также применйм к. этому слову. Таким образом, слова в алфавите А, алгорифм 9 в случае применимости снова перерабатывает в слова в А,. С учетом процедуры, изложенной в 2 54.2, можно счи- тать, что алгорифм 9 является вычислимой вербальной функцией одной переменной. Так как алгорифм 6 приме- ним к записи любой вычислимой вербальной функции одной переменной «1, тем же самым свойством обладает и 9 [(6)1.
Кроме того, 9(ес') всякий раз представляет собой запись некоторой вычислимой вербальной функции (ьаз или й»), так что 9 является вычислимым оператором над вычисли- мыми вербальными функциями одной переменной. Согласно теореме з 55.2.1 этот оператор имеет некоторую неподвиж- ную точку л).
Очевидным образом (Т) З = <9(В»)>. Поэтому в силу инвариантности Р е) обладает этим свойст- вом тогда и только тогда, когда им обладает <9(В')>. Предположим теперь, что 2) обладает свойством Р. Тогда (4 (Вз) в-Л. Но тогда Я(е)з) тй1[(6)) и, значит, <9 (6»)> есть «1«, а й, не обладает Р.
Поэтому л) не обладает Р. С другой стороны, предположим, что ю' не обладает Р. Тогда 9(2)з)л Л. Но тогда 9(11)з)а1Х1; [(6)1 и, значит, <(1(2)*)) есть 2(„а ВХ, обладает Р. Поэтому неверно, что 6 не обладает Р. Полученное противоречие — «е) не обладает Р, и неверно, что кз не обладает Р» — и доказывает теорему 1,1, Заметим, что, несколько изменив рассуждение, мы могли бы получить другое, „более сильное" и в определенном отношении более естественное противоречие «е) обладает Р, и неверно, что я) обладает г».
Но для нашей цели это не- существенно, и мы этим заниматься не будем. 2. Рассмотрим следующие примеры. 1'. Свойство Р вычислимой вербальной функции «быть применимой к заданному фиксированному слову Р» при любом Р является иивариантным и нетривиальным. Следовательно, оно неразрешимо *).
(Зтот пример является любопытным допол- нением к теореме З 48.!.4.) ") В примерах 1' — Е' неразрешимость понимается в смысле, указ»пном и формулнроике теоремы 1.1, РАСПОЗНАВАНИЕ ИНВАРИАНТНЫХ СВОЙСТВ 341 2'. Свойство функции «иметь разрешимую проблему распознавания применимости к словам в алфавите А» является инвариантным и, как нетрудно видеть (2 48.1.4), нетривиальным. Следовательно, оно неразрешимо.
3'. Свойство функции «быть полной относительно А» инвариантно и очевидным образом нетривиально. Следовательно, оно неразрешимо. 4'. Свойство функции «быть пополнимой относительно алфавита А.» очевидным образом инвариантно и нетривиально (з 53.1.11. Следовательно, оно также неразрешимо. В заключение мы рассмотрим еще один пример, требующий, как нам кажется, известной осторожности в рассуждении. 5'.
Пусть яз — произвольная вычислимая вербальная функция одной переменной. Рассмотрим свойство бв «быть функцией, эквивалентной ез» и покажем, что оио неразрешимо. Это свойство очевидным образом инвариантно. Поэтому возникает естественное желание применить к нему теорему 1.1, тем более, что функция, обладающая свойством схе, имеется: это функция ьл1. Более сложно, однако, обстоит дело с функцией, не обладающей этим свойством, т.
е. с функцией, неэквивалентиой ьл). В самом деле, рассчитывать на разработку эффективного способа нахождения такой функции в общем случае мы ие можем из-за теоремы й 55.2.1: такой способ порождал бы вычислимый оператор над вычислимыми вербальными функциями без неподвижной точки. И все-таки здесь может быть применено следующее рассуждение: Если е1(Л) определено, то функция, ие обладающая свойством 0Е, может быть указана: в качестве такой функции можно взять, например, нигде не определенную функцию из примера ~ 54.1.2'. И в том случае, когда е)(Л) не определено, такая функция тоже может быть указана: например, можно взять функпию из примера б 54.!.1'. Таким образом, если бы свойство Оч было проверяемым, то в силу теоремы 1.1 не существовало бы вычислимой вербальной функции, не обладающей свойством с»в.
А это в силу только что проведенного рассуждения означало бы, что: 1) е)(Л) не определено и 2) неверно, что «з(Л) не определено. Полученное противоречие показывает, что с«и неразрешимо, что и требовалось доказать. Математик, разделяющий веру в незыблемый характер „закона исключенного третьего", разобрав случаи «В(Л) 342 вычислимые ББРБАльные Функции |гл ю| определено» и «В(Л) не определено», вероятно, следующим образом закончил бы доказательство неразрешимости свойства бв. «Итак, если В(Л) определено или В(Л) не .определено, то существует функция, не обладающая свойством бв. Но посылка этой импликации г силу закона исключенного птргтьего истинна.
Следовательно, истинно и ее заключение. Таким образом, существует функция, не обладающая свойством бв. Значит, это свойство нетривиально, и потому в силу теоремы 1.1 оно неразрешимо». Но с какой стати мы так уж должны верить в незыблемость этого „закона"? Казалось бы, напротив, пример 1' показывает, что не существует способа„позволяющего по функции В выяснять, какой именно из членов дизъюнкции (1) «В(Л) определено или В(Л) не определено» имеет место *), а ведь в точности это и требуется по нашему соглашению (см.
4 7,1) для признания дизъюнкции (1) истинной. Правда, в примере 1' утверждается невозможность нормального алгорифма, распознающего свойство гл. Но принцип нормализации [2 27.61 не оставляет нам надежд на существование какого-либо другого эффективного способа решения этой задачи. В свете сказанного рассуждение, проведенное нами, представляется нам более осторожным, а потому и более убедительным, чем рассуждение воображаемого коллеги. ') Конечно, оба они не могут быть ложными одновременно, так как тогда была бы истинной конъюнкция, у которой второй член является отрицанием первого.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
