Анимация
JavaScript
|
Главная Библионтека Основное значение далее будет иметь не сама теорема 4 а ее частный случай: Следствие 1. Пусть ф - полная нумерация. Тогда для каждой общерекурсивной функции f {х) уравнение ф/ {х) = Щ (5) имеет решение {«неподвижную» точку) х. При этом существует алгоритм, позволяющий по клиниевскому нож-ру f находить определенное решение х уравнения (5). Иначе говоря, существует общерекурсивная функция g (п) такая, что (рК {п, g {п)) = Ф (ге) (6) для всех тех значений п, jiflR которых функция К (ге, t) всюду определена. Но существование функции g (ге) с этими свойствами утверждает теорема 4, если в ее условии положить / {Ху, Жа) = -К {х2, ж). Нижеследующая важная теорема была сначала доказана Р о»д ж е р с о м [1] для нумерации Клини и позже была распространена на произвольные полные нумерации (Мальцев [2]). Теорема 5. Если полная нумерация ф совокупности и сводится к какой-нибудь ее нумерации ф, то ф одно-сводится к ф. Каждая нумерация, эквивалентная полной нумерации, изоморфна последней, а потому и полна. Второе утверждение теоремы вытекает из первого, так как одноэквивалентные нумерации в силу теоремы 2 из и. 9.2 являются изоморфными. Поэтому докажем лишь первое утвернадеиие. Пусть общерекурсивная функция / {х) сводит ф к ф. Если совокупность tl имеет лишь одпп объект, то утверждение теоремы 5 тривиально. Поэтому мы можем предполагать, что существуют числа а, Ъ, являющиеся ф-номе-рамп различных объектов из U. Нам надо построить общерекурсивную функцию 5о {х, у), обладающую следуюпщ-ми свойствами (ср. п. 9.2): ф5о {х, у) = ф.т, уфг=¥ Во (х, у) ф В {х, z). Строим сначала вспомогательную общерекурсивную функцию S {х, у), удовлетворяющую требованиям ф5 {X, у) = щ, f {S {х, у)) Ф f {S {х, Z)) {у Ф Z). (7) Полагаем по определению S (х, 0) = х и далее по ин-дукцпп допускаем, что для некоторого г значения 5 {х, 0), S {х, I), . . ., S {х, г) уже найдены и притом такие, что тре- бования (7) для у, z = О, . . . местные частичные функции X, есйи f{t){f(S(x, 0)), ...,f{S{x, г))}, а в противном случае; hi{t) = г выполнены. Вводим одно- Функции существует , если f{t)e{fiS(x,0)),. ..,f{S(x,r))}, в противном случае. hy, частично рекурсивны. Более того, алгоритм, позволяющий по числам х, S (х, 0), . . ., S {х, г) находить определенные клиниевские номера Пу, функций/г, к. Полагаем, далее, т = g (щ), Щ = g (гег), где g (t) - функция из соотношения (6). Следовательно, (Щ) = Ч>Щ, 4>K {Щ) = Ц>Щ. (10) Если / (ту) {/ {S (х, 0)), . . .,f{S {х, г))}, то полагаем S (ж, г -Ь 1) = ту. Из соотношений (8), (10) в этом случае имеем ц>ту = ц>х ж потому требование (7) выполняется для у, Z = О, . . ., г, г -Ь 1. Если / {ту) 6 {{S {х, 0)), . . .,fiS (х, г))}, то полагаем S {х, г -f 1) = т. Покажем, что и в этом случае требование (7) выполнено для у, z = О, . . ., г -\- 1. Но предположению для некоторого i, О < г < г, имеем / (ттг) = = / {S {х, 0) и, значит, фттг = (р {S {х, i)) = щ = фу{ту). Но в рассматриваемом случае согласно (8) hy (ту) = а. Поэтому (рту = щ = фа. Если бы оказалось, что f (т) £ {f {S [х, 0)), ... • . ., f {S [х, г))}, то аналогичным путем получились бы равенства фттг, = фж = ф&, противоречащие уже установленным соотношенпям щ = щ ф ф6. Поэтому / {т) (j; I; {/ {S {х, 0)), . . .,f{S {х, г))} и в силу (9) /г (ша) = а. Отсюда имеем f{S{x, r-\-i)){f{S{x, 0)), f{S{x, г))], (pS {х, г + i) = (рт.2 = фа = щ. Таким образом, требования (7) в рассматриваемом случае выполнены и функцию S [х, у) можно считать построенной. Из регулярности процесса построения функции S {х, у) впдна ее общерекурсивность. Формальное доказательство этого предоставляется читателю. Свойства (7) показывают, что в качестве искомой функции В {х, у) для нуме-Рацин ф может быть взята функция f {S [х, у)), п доказательство теоремы 5 закончено. 9.4. Семейства объектов нумерованных совокупностей. Нумерация элементов произвольной совокупности U позволяет перенести основные понятия теории числовых рекурсивных множеств и на произвольные совокупности и. Однако перенесение это можно делать различными способами, в силу чего понятия рекурсивности, рекурсивной перечислимости и т. и. ири переходе от множеств чисел к семействам объектов разветвляются на вполне рекурсивные, слабо рекурсивные и т. д. Мы рассмотрим пока лишь понятия с приставкой «вполне»: вполне рекурсивные, вполне неречислимые и т. д. Пусть и - совокупность объектов с нумерацией ф. Семейство S объектов из U будем называть нетривиальным, если 8 непусто и не совпадает с U. Символом ц)~8 будем обозначать множество всех ф-номеров всех объектов из 8. Если А - некоторое множество чисел, то через (рА будет обозначаться ф-образ А в U, т. е. ф4 есть семейство объектов, хотя бы один ф-номер которых содержится в А. Семейство 8 называется вполне перечислимым {вполне рекурсивным, вполне креативным), если множество ф~/8 рекурсивно неречислимо (рекурсивно, креативно) (ср. и. 7.2). Следуюп],ая теорема является дословным распространением теоремы Раиса, доказанной в и. 7.2 для нумерации Клини, на произвольные полные нумерации. Теорема 1. Вполне рекурсивные семейства объектов в совокупностях с полными нумерациями тривиальны. В самом деле, допустим, напротив, что совокупность U с полной нумерацией ф имеет нетривиальное вполне рекурсивное семейство объектов 8. Это означает, что множество ф~/8 не пусто, отлично от натурального ряда и рекурспвно. Но тогда непустым п рекурсивным будет и дополненпе ф~/8" множества ф">. Пусть а G ф", Ъ G 6 ф~/8". Строим вспомогательную функцию а, еоли X G Ц!8, 1{х) = Ъ, есяи х(Ц!~8. Эта фзнкцпя обш;ерекурспвна (п. 6.3). Согласно теореме о неподвижной точке (и. 9.3) существует чпсло с, для которого ф/ {с) = фс. Как и в п. 7.2, .тегко убеждаемся, что оба предположения c(f~8, сЕф"" ведут к протп-воречпю. Теорема 2. Никакое нетривиальное вполне перечислимое семейство 8 объектов совокупности U, имеющей полную нумерацию ф, не может содержать особого элемента о нумерации ф. Пусть, напротив, семейство 8 вполне перечислимо нетривиально и содержит о. Выберем номер b какого-нибудь объекта, не входящего в 8, и рассмотрим функцию = Ь, если а; G ф 8, не определено, если а;ф 8. Согласно п. 6.3 эта функция частично рекурсивна. Поэтому найдется общерекурсивная функция g {х) такая, что ф6, если X б Ц>~8, о, если хц>~8. (pg{x) = Следовательно, X б Ч>-8 g{x)e Г8. Это означает, что множество ф"* ш-сводимо к множеству ц>~8. Но последнее множество рекурсивно неречислимо. Значит, множество ф"" также рекурсивно неречислимо (п. 8.1). Из рекурсивной перечислимости взаимно дополни-те.льных множеств вытекает их рекурсивность. Поэтому семейство S вполне рекурсивно, что противоречит теореме 1. Теорема 3. Каждое вполне перечислимое нетривиальное семейство 8 объектов совокупности U, имеющей полную нумерацию ф, является вполне креативным. Пусть а б ц>~8. Обозначим через Т какое-нибудь креативное множество, например, пз числа тех, которые былп построены в п. 8.2. Рассмотрил! вспомогательную функцию fix) = а, если хТ, не определено, если хТ. Эта функцпя частично рекурсивна и потому существует общерекурсивная функция g (х), для которой Ф(.г-) = фа, если хТ, о, если хТ. fix) если ф {о}. не определено, если а; G Ф о. где ф& (Е S. Из полноты нумерации ф вытекает, что найдет ся общерекурсивная функция g (х), для которой (pg{x) = (pb, если X G ф {o}i о, если жб ф 0, X е ц>~ о g [х) е (p-S. и, значит, Согласно теореме 3 множество ф~o продуктивно. Но это множество ш-сводится к ц>~-8. Следовательно, ф"* про- s дуктивно, что и требовалось. Известно (п. 7.2), что в нумерации Клини семейство {о} вполне перечислимо. Поэтому из теоремы 4, например, следует, что совокупность всех клиниевских номеров нигде не определенной функции является продуктивным множеством. Более общо: продуктивной является совокупность всех клпнпевскпх номеров функций любого семейства, лишь бы это семейство включало нигде не определенную функцию и не было семейством вообще всех частично рекурсивных функций. Теоремы 1-4 хотя и дают небольшую информацию о строении вполне неречислимых семейств, но зато для всех полных нумераций. Строение вполне перечислимых семейств для нумераций Клпни и Поста известно гораздо более подробно (см. задачи 9, 10 пз § 7). 1. Пусть В (.г, у) - частично рекурсивная функция. Показать (II те.м самы.м закончить формальное доказательство теоремы 1 пз п. 9.2), что фупкция g (х), определенная схемой g (0) = а, h (а) = {В {п, t)i{g{0----,g{n)}), (а) g{n+i) = B {п, h («)), частично рекурсивна. 2. Пусть функция В {х, у) в предыдуи.;ей; задаче примитивно рекурсивна и удовлетворяет условию разиозиачностн: из у =j= z вытекает В {х, у)ф В {х, z). Тогда функция g {х), определенная схе-Moii (а), также примитивно рекурсивна. 3. Провести формальное доказательство рекурсивности функции h (х), построенной в процессе доказательства теоремы 2 из и. 9.2. Показать, что если заданные односводящие функции f{x), ,? (.г) примитивно рекурсивны, то функция h (z), осуществляющая изоморфизм, также примитивно рекурсивна (см. Мальцев [2]). 4. Пусть частично рекурсивная фупкция / имеет рекурсивную ниласть определения. Тогда каждое множество чисел, содержащее псе клиниевские номера / и не содержащее ни одного номера какого-нибудь частично рекурсивного расширения /, является продуктивным (Райе [1], см. также Мальцев [3]). 6. Множество чисел заведомо продуктивно, если оно содержит псе клиниевские номера некоторой частично рекурсивной функции / ив то же время не содержит нп одного клиниевского номера ни одной конечно опредолеппоп функции, график которой содержится в графике / (Мальцев [3]). 0. Дополнение вполне неречислимой совокупности рекурсивно неречислимых множеств <В тогда п только тогда вычислимо (определение вычислимости см. п. 7.4), когда © есть совокртность всех надмножеств некоторой системы конечных множеств, стандартные номера которых составляют рекурсивное множество. Аналогичное утверждение справедливо и для дополнения вполне неречислимой спвокуиности частично рекурсивных функций (Р а ii с [2]). 7. Показать, что нумерации Клини и Поста не изоморфны fM а л ь ц е в [3]). f*. Селюпство объектов @ ну.мерованпой совокупностп, имеющей нумерацию а, называется внутренне продуктивным, если сущест-»ует такая общерекурсивная функция g (х), что для каждого п ая с © =Ф (ге) = @& (ге) ф ап. Показать, что никакое внутренне продуктивное семейство в нумерациях Клпнп и Поста не может быть вычислимым. 9. Показать, что в нумерации Клпнп каждое семейство частично рекурсивных функций с бесконечной областью определения, содержащее частичные характеристические функции всех бесконечных рекурсивных множеств, является внутренне продуктивным f-M а л ь ц е в [3]). 10. Если семейство частично рекурсивных функгщп © имеет полную вычислимую нумерацию с особым объектом о = / (z), значения каждой функции из @ совпадают с значенпялш / (т) 1я всех X пз области определенпя /, Согласно предыдущей теореме о (j; S. Поэтому Мы видим, следовательно, что креативное множество Т ш-сводится к рекурсивно перечислимому множеству (pS. Поэтому множество (pS креативно. Теорема 4. Пусть в совокупности U, имеющей полную нумерацию ц>, семейство {о} всех неособых объектов вполне перечислимо. Тогда каждое семейство 8 объектов и, содержащее о и отличное от Л, является вполне продуктивным. Рассмотрим частично рекурсивную функцию Дополнения, примеры и .задачи 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 [ 30 ] 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |