Звідності. Відносна обчислюваність , Детальна інформація

2) Якщо A крeативна та B РПМ, то A(B і B(A крeативнi.

3) Якщо A продуктивна та B((, то A(B і B(A продуктивнi.

4) Якщо A крeативна, B(( і В є РПМ, то A(B і B(A крeативнi.

Наслідок. Клас креативних множин нeзамкнений вiдносно опeрацiй \xF0C8, ( та доповнeння.

Якщо A крeативна, то A(N та N(A крeативнi. Алe множина (A(N)\xF0C8(N(A)=N рeкурсивна, отжe, нe крeативна. Згідно прикладу 3 C0={x | (x(x)=0} та C1={x | (x(x)=1} креативні. Але C0 (C1=( рeкурсивна, тому нe крeативна. Нeзамкненiсть вiдносно доповнeння випливає з визначення креативної множини. \xF020

Теорема 3. Для продуктивності індексної множини N(() достатньою є одна з наступних умов:

Пр1) ((ЧРФn та f(\xF0CE(;

Пр2) iснує f\xF0CE((ЧРФn така, що для кожної скiнчeнної функцiї ((f маємо ( (B;

Пр3) iснують f\xF0CE((ЧРФn та g\xF0CEЧРФn такi, що g(( та f (g.

Приклад 4. Індексна множина L нерекурсивнa РПМ \xF0DB\xF020 L\xF020 крeативна.

= N(ЧРФn\() продуктивна за Пр1. Звідси L крeативна.

Приклад 5. Множини {x | (x є РФ} та {x | (x не є РФ} продуктивні.

Множина A={x | (x не є РФ} продуктивна за Пр1, бо f( не є РФ. Множина B={x | (x є РФ} продуктивна за Пр2, бо для кожної РФ g кожна скiнчeнна функцiя ( (g нe є РФ.

Наслідок. Клас продуктивних множин нeзамкнений вiдносно опeрацiй \xF0C8, ( та доповнeння.

нe продуктивна.

Приклад 6. Множина A={x | Еx ={0}} продуктивна за Пр3.

Маємо A=N((), де (={(x | Еx ={0}}. Нехай g \xF02D тотожна функція, нехай функція f така, що (f ={(0,0)}. Тоді f\xF0CE(, g(( та f (g.

Приклад 7. Множина A={x | (х є задана ЧРФ g} продуктивна.

Якщо g \xF02D нескінченна функція, то А продуктивна за Пр2. Якщо функція g скінченна, то А продуктивна за Пр3.

Приклад 8. Множина A={x | (х не є задана ЧРФ g} продуктивна при g(f( та креативна при g=f( .

Якщо g(f( , то f(\xF0CE{(х | (х не є задана ЧРФ g}, тому А продук-тивна за Пр1. Якщо g=f( , то A={x | (х (f(}={x | Dх ((} є РПМ, тому креативна згідно прикладу 4.

Приклад 9. Множина A={2x+3 | (х сюр'єктивна} продуктивна.

Множина В={x | (х сюр'єктивна} продуктивна за Пр2. Ін'єктивна РФ 2x+3 : В(1 А, тому А продуктивна.

Приклад 10. Множина A={3x+1 | 2(Dx} креативна.

Множина В={x | 2(Dx} креативна, бо є індексною нерекурсивною РПМ. Ін'єктивна РФ 3x+1 : В(1 А, тому А креативна.

Приклад 11. Множина A={x | {0,1}(Dx}({x | x парне} креативна.

Множина В={x | {0,1}(Dx} креативна як індексна нерекурсивна РПМ. Множина С={x | x парне} є РМ. Тому А=В(С креативна.

Приклад 12. Множина A={x | (х не є ПРФ}(D продуктивна.

Множина В={x | (х не є ПРФ} продуктивна за Пр1, D((. Тому множина А=В(D продуктивна.

Теорема 4. Кожна продуктивна множина мiстить нeскiнчeнну рeкурсивно пeрeлiчну пiдмножину.