12. Множество а продуктивно тогда и только тогда, когда существует такая общерекурспвная функция / (г), что

/ (X) 6 (а - л) и {Лх - а)

для всех значений х (Майхил, ср. Фридберг и Роджерс

13. Пересечение продуктивного и простого множеств есть ьшо-жество продуктивное (Деккер [2]).

14. Анализ доказательства теоремы 3 из п. 8.2 непосредственно приводит к следуюпщм результатам, несколько более тонким, чем сама теорема 3. Множество а назовем слабо продуктивным, если для него существует такая общерекурсивная функция / (х), что

а) = 0 =Ф / (г) 6 «,

б) (Лж одноэлементно и а) =ф / (г) $ л.

Показать, что каждое рекурсивно перечпслимое множество т-сводимо к дополнению произвольного слабо прдуктивного множества и потому каждое слабо продуктивное множество продуктивно.

16. Пусть все множества некоторого семейства ® имеют одну и ту же слабо продуктивную футакцию. Тогда

а) существует функция, продуктивная одновременно для кан-дого множества из ©;

б) пересечение всех множеств из © продуктивно;

в) объединение всех множеств из © продуктивно (С м а л ь я н [1], с. 101 (с. 148-149 русского перевода)).

16. Каждое рекурсивно перечпслимое мнонество, имеющее бесконечное дополнение, содержится в некотором простом множестве. Верно ли, что каждое рекурсивно перечислимое множество, имеющее бесконечное дополненпе, содержится в некотором максимальном мнонестве?

17. Согласно п. 7.4 у-номером (стандартным номером) конечного мнон{ества, состоящего из чисел с, < < . . . < с, называется число 2" -f 2* -f . . . -f 2 а у-номером пустого множества называется 0. Словами уп, пп обозначаются конечное ъшо-жество, пмеющее стандартный нолюр п, и соответственно рекурсивно перечпслпмоемножество, имеющее постовский номер п.

Бесконечное ьшожество а называется гипериммунным, если не стцествует нп одной общерекурспвной функции i{x), для которой всемножества yi (0), уг (1), . .., уг (ге), . . . попарноне пересекаются и каждое имеет хотя бы один элемент пз а.

Бесконечное ьшожество а называется гипергипериммунным., еслп не существует нп одной общерекурсивной функцпп i {х), для которой шон<ества яг (0), яг (1), . . ., т (ге), . . . попарно не пересекаются, конечны п каждое из них имеет непустое пересечение с а.

Множество а называется гиперпростым илп гипергиперпростым, еслп а рекурсивно неречислимо, а его дополнение а гиперпммунно или соответственно гипергипертипнно.

Показать, что "каждое гипергинерпростое ьшожество гппёр-просто, а гиперпростое просто. Доказать, что все максимальные 1шожества гипергпперпросты (Фрпдберг [1]).

18. Постропть максимальные лшожества а, Р, отличающиеся бесконечным 1шожрством элементов (напрпмер, прпнять во внимание, что дополненпе максимального множества состоит .либо почти целиком из четных, либо почтп целпком пз нечетных чпсел).

19. Если максимальные множества а, Р отличаются бесконеч-пы.м мноичсством чисел, то их пересечение гппергиперпросто, но пе максимально (Е й т с [1]).

20. Если рекурсивно перечислпмое множество а не гипергинерпростое и его дополнение а бесконечное, то найдется такая общерекурсивпая функция j (х), что последовательность .ч/ (0), я/ (1), . . . будет состоять из попарно не пересекающихся множеств, каждое пз которых имеет бесконечное пересеченпе с а (Ейтс [1]).

21. Существует гиперпростое множество, не являющееся ги-иергппериростым.

22. Прямым пересчетом (пли трассирующей функцией) множества а называется функция / {х), пересчитывающая элементы а строго в порядке пх возрастания. Иначе говоря, для бесконечного а t (х) ~ монотонно возрастающая функция, совокупность значе-unii которой совпадает с а. Показать, что общсрекурсивпым прямым пересчетом обладают бесконечные рекурсивные множества и только они.

23. Говорят, что функция g {х) мажорирует функцию / (г), если существует такое а, что g (х) f (х) для а; > а. Доказать, что рекурсивно перечпслимое множество а гпперпросто тогда и только тогда, когда его дополнение а бесконечно и прямой пересчет а не мажорируется никакой общерекурсивной функцией (Успенский [2], Райе [3]).

24. Говорят, что частично рекурсивная функция / (х) ретрас-сирует множество а, еслп для каждого а; 6 а: а) значение / (а;) определено; б) если число X не минимально в а, то / (а;) есть ближайшее меньшее в а; в) если х минимально в а, то / (а;) = х. Множество сс называется ретрассируемым, если существует хотя бы одна частично рекурсивная функция, ретрассирующая а.

Пусть числа а, а, . . ., а„, . . . удовлетворяют условиям 1 < По < 9, О < aj < 9 (г = 1, 2, . . . ). Показать, что множество

а = {ао,. 10. ао + а, 10-а, + lO-flj + а----}

ретрасспруется функцией

/И =

если 0а:<9, еслп 10 < X.

Таким образом, функцпя / (а:) является ретрассирующей для кон-типуального числа йшожеств о.

Показать, что каждое рекурспвное лмножество ретрассируемо " что каждое ретрассируемое множество рекурсивно пли пммунно Д е к к е р и М а й X п л [2]).

25. Каждое ретрассируемое множество, имеющее рекурсивно перечпслимое дополнение, пли рекурспвно, пли гиперийшунно (см. задачу 23) (Д е к к е р п М а й х и л [2]).

26. Рекурсивно перечислпмое множество а имеет ретрасспруе-loe дополнение тогда и только тогда, когда С5тцествует общерекурсивная функция 7 (а;) такая, что йгножество а является совокупностью тех значений х, для которых неравенства

X () < X W & 2/ > 2:

имеют некоторое решение у {представление Е й т с а [1]).

27. Множество а гппергиперпросто тогда п только тогда, когда! оно рекурсивно неречислпмо, его дополиение а бесконечно и aJ не содержит бесконечни.хретрасснруемы-х подмножеств (Е итс[1]);

28. Табличная сеодимоапь. С алгоритмической точки зрения! т-сводимость множества а. к множеству Р означает пстинность для1 некоторой общерекурспвной функцип / (г) следующего предписа.-! пня: если хотите знать, расположено число х внутри или вне ътаЩ жества а, то найдите / (.г-) и узнайте расиоложеппе / (i) отпосптель но р. Если / (.т) внутри Р, то а; внутри а; если же / (х) впе Р, то Щ вне а. I

Вид этого предписания легко обобщается, например, следую-! щим образом: если хотите знать, как расположено х относительно al вьгаислите значения двух рекурсивных функций / [х), (х) п нос мотрите, как эти значения расположены относительно" р. Есл /j (z) б Р & /а (х) е Р, то z б а, а в остальных случаях х а.

Последний критерий можно изменить, потребовав, ЧтобШ I 6 а было в случаях /i (г) $ р & /а {х) G р или h (г) 6 Р & /г () 6 Р> в остальных случаях чтобы было х а..

К.часс рассматриваемых предписаний можно еще расширить! путем задания п функций / (z), . . ., /„(ж) и усложнения соответ!

г г I X критериев вхождения х в а (таблицистинности). Все эти! предписания были названы П о с т о м [31 табличными сводимостяМ ми. Ясно, что вместо задания п фзгнкций можно ограничиться й1 заданием лишь одной функции z (i) = [ге - 1, [/ (i), ...,/„ (i)] т - 1]. Тогда знание х (i) дает не только число ге, значения! А (*). • > fn (0. по и номер т соответствующей таблицы истинно-! сти. Изложенное можно резюмировать в следующем формальном! определении. ,1

Условимся говорить, что число X таблично сводимо к множеству Р (символически р \=ц z), если в результате следующих вычисле- ПИЙ:

1) ищем числа ге == [zjgi -f 1, = [х],, щ = [zjgg -f- 1, где {x\ii - нумерацпопные функции из п. 7.1 (илп соответствующие И8 п. 3.3);

2) ищем числа = х Ыщ), , % = X Ыпп), где х -1 характеристическая функция множества р;

3) находим число м = ei -Ь 62-2 -f ... -f e„-2"-i и, представ-1

ляя т в виде т = 2" + 2 + . . . + 2" ("о < < • • • < находим числа и, и, . . ., и - окажется, что и 6 {цд, и . . ., uj.

Множество а называется таблично сводимым к ьшожеству р1 (символически а р), если существует такая общерекурсивная функция / (i), что Z G а 4Ф р =,- / (z) для каждого значения х. i

Показать, что отношение табличной сводимости рефлексивно,; транзитивно и что пз w-сводимостп вытекает табличная сводимость, i

29. Говорят, что множество а сводится к р таблицами ширины W, еслп стцествует такая общерекурсивная функция / (z), что \ Z 6 а Р =(( / (!•) п [/ (г)]з1 -- 1 ш для каждого значения х.

Если множество а сводится к р таблицами ширины v, а. сво-! дптся к у таблицами ширины ш, то а сводится к у таблицами шпрпны VW. Из 71г-сводимостп вытекает сводимость таблицами пшрпны 1. Верно лп обратное?

30. Если а таблично сводимо к рекурсивному множеству, то а; рекурсивно.

31. Креативные множества таблично сводимы к простому мно-л.рству Поста, построенному в п. 8.3 (Пост [3]).

32. ]\роативиые множества не сводимы таблично к пшерпро-cтыr множествам (Пост [3]).

33. Множество а называется ограниченно таблично сводимым i; множеству Р, если для некоторого w а сводимо к р таблицами ширины w. Никакое креативное мноя{ество не может быть ограничении таблично сводимым к простому множеству (Пост [3], с. 304).

34. Пусть а" обозначает совокупность номеров ге-ок с элементами из а. Показать, что а" сводится к а таблицами ширины п. Существует такое простое множество а, что та, гз? тО?, . . . (с/. < тР означает, что а не ге-сводимо к р) (Фишер [1]).

35. Согласно Смальяну иммунное множество а называется о!>фективно иммунным, если существует такая частично рекурсивная функция / (z), что для каждого значения х: если пх содержится в а. то f(x) определено и количество чисел в пх меньше / (z). Рекурсивно перечислимое множество пазывается эффективно простым, если его дополнение эффективно иммупно. Показать, что построопное в и. 8.3 простое мнон{ество Поста эффективно просто. Ьаждое эффективно простое множество просто. Существуют простые мнонества, не являющиеся эффективно простыми (Сакс [1]).

36. Показать, что пересечение двух простых множеств есть простое множество, объединение двух простых множеств либо просто, либо имеет конечное дополнение, существуют два простых множества, объединение которых совпадает со всем множеством натуральных чисел. Те же утверждения имеют место и для гипер-иростых множеств (Д е к к е р [1]).

§ 9. Нумерации произвольных совокупностей

В данном параграфе излагаются основы общей теории нумерованных совокупностей объектов. Одно простое свойство нумерации Клини, сформулированное в абстрактном виде, принимается в качестве аксиомы, определяющей так называемые полные нумерации, среди которых, помимо нумераций Клини и Поста, имеется и ряд других конкретных важных нумераций. Более детально изучаются свойства некоторых специальных нумераций семейств рекурсивно неречислимых множеств, что позволяет отчетливее выделить место, занимаемое нумерациями Клини п Поста среди других возможных нумераций совокупностей частично рекурсивных функциймножеств. В конце параграфа рассматривается понятие рекурсивной неотделимости множеств, связанное с нумерациями и играющее •аметнуюТроль в теории рекурсивных функций.

9.1. Изоморфизм и эквивалентность нумерации. "Яг/-пераиией ф.совокупности объектов Z7 называется отображение некоторого множества Жц, натуральных чисел на

совокупность и. Число п б Жф называется (-номером (или просто номером, если ф фиксировано) объекта фп б б Z7. Множество Жц, называется номерным множеством нумерации ф. Из этого определения следует, что каждый объект нумерованной совокупности имеет хотя бы один номер. Если каждый объект имеет в точности одинномер, то нумерация называется одно-однозначной (или, короче, однозначной). Если номерное множество Уц, совпадает с всем натуральным рядом N, то нумерация называется простой. Далее мы будем рассматривать лишь простые нумерации, хотя многие понятия и теоремы легко переносятся и на непростые нумерации (см. Мальцев [3] и указанную там литературу). Соответственно этому далее иод словом «нумерация», если не оговорено противное, всегда понимается простая нумерация.

Пусть (JI, ф> - некоторая нумерованная совокупность и с нумерацией ф. Вводим на номерном множестве Жф = W бинарное отношение 9, полагая по определению xQy фх = фг/.

Ясно, что отношение О рефлексивно, транзитивно и симметрично. Его иногда называют нумерационной эквивалентностью и вместо xQy пишут х = у (mod 9). Совокупности чисел, эквивалентных друг другу но mod 9, называются нумерационными классами. Иначе говоря, нумерационными классами называются совокупности всех номеров отдельных объектов из U. Если п - число, то через Qn обозначается множество чисел, сравнимых но mod 9 с /г, т. е. Qn есть множество всех номеров объекта ф/г. Система JJ/Q всех нумерационных классов находится в естественном взаимно однозначном соответствии с совокупностью объектов и. В каком-то сдшсле нумерацию ф можно считать вполне заданной, если задано отношение 9. С этой точки зрения теория нумерованных совокупностей - это теория рефлексивных, транзитивных и сидшет-ричных отношений, заданных на натуральном ряде.

Говорят, что обгдерекурсивная функция / (х) представляет гомоморфизм нумерованного множества <JI, ф) на HjiepoBaHHoe множество <F,t}))>, если f [х) отображает взаимно однозначно натуральныйрядна себя и если для каждых X, у

щ = (рг/ =Ф я];/ [х) = ipf (у). (1)

Из условия (1) следует, что отображение h: фж -> "ф/ (х) есть однозначное (в одну сторону) отображение 17

на V, которое, собственно, и называется гомоморфизмом, я функция / (х) ЛИШЬ «представляет» этот гомоморфизм.

Ясно, что если / (х) представляет гомоморфизм нумерованного множества (U, ф> на нумерованное множество <F, Tj)), а функция g (а;) представляет гомоморфизм <F, ij)) на нумерованное множество CW, %), то функция g (/ (х)) представляет гомоморфизм <?7, ф>на<ТГ, %). Иначе говоря, композиция гомоморфизмов есть гомоморфизм.

Говорят, что обгдерекурсивная функция / (х) представляет изоморфизм нумерованного множества (J7, ф> на ну-герованное множество <F,i3>, если/(а;) отображает взаимно однозначно натуральный ряд на себя и для каждых X, У

щ = фг/ 44>г;/ (х) = ij)/ (у).

Таким образом, функция / (х) представляет изоморфизм, если / представляет гомоморфизм <(С/, ф> на (F, ф), а обратная функция /" представляет гомоморфизм <F, il)> на <г7, ф>.

Нумерованные множества называются изоморфными, если сутцествует функция, нредставляюгдая изоморфизм первого множества иа второе. Из замечания о композиции гомоморфизмов следует, что отношение изоморфизма нумерованных множеств рефлексивно, симметрично и транзитивно .

Вводя понятия гомоморфизма и изоморфизма, мы рассматривали, вообгде говоря, различные нумерованные совокупности объектов. Однако случай, когда сравниваются различные нумерации одного и того же множества, играет важную роль и требует новых понятий. Пусть ф, ij) - (простые) нумерации одной и той же совокупности объектов и. Мы будем говорить, что нумерация ф сводится к нумерации (символически ф <;i;), если суш:ествует общерекурсивная функцпя / (х) такая, что

Ц)Х = Tj)/ (х).

Нумерации ф и г)) называются эквива.гентными, если каждая пз них сводили к другой. С точки зрения теории алгоритмов эквивалентные тшерации - это такие нумерации, для которых сзпществует алгоритм, позволяющий по произво-льному номеру любого объекта из основной совокупности в одной нумерации найтп некоторый номер того же объекта в другой нумерации.