Анимация
JavaScript


Главная  Библионтека 

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

Основное значение далее будет иметь не сама теорема 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