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

.

Множину L називатимемо (-РМ, якщо (L є (-РФ.

Множину L називатимемо (-РПМ, якщо L=( або L=Ef для деякої (-рекурсивної функцiї f.

Предикат P називатимемо (-РП, якщо (P є (-РФ.

є (-ЧРФ.

Приклад 2. Релятивнi варiанти для теорем роздiлiв 7 та 8:

(у1, ..., уп).

(y).

R3) Функцiя, унiверсальна для класу n-арних (-РФ, не є (-ЧРФ.

R4) Існує (-ЧРФ, унiверсальна для класу n-арних (-ЧРФ.

.

R6) Наступнi визначення (-РПМ еквiвалентнi:

df1) L=( або L є областю значень деякої (-РФ;

df2) L є областю значень деякої (-ЧРФ;

df3) L є областю визначення деякої (-ЧРФ;

df4) часткова характеристична функцiя множини L є (-ЧРФ.

є (-РМ.

R8) Предикат Q(x1, ..., xn) є (-ЧРП ( ( iснує (-РП R(x1, ..., xn, y) такий, що Q(x1, ..., xn) \xF0DB \xF024yR(x1, ..., xn, y) ).

R9) Якщо Q(x1, ..., xn, y) є (-ЧРП, то \xF024y1...\xF024ykQ(x1, ..., xn, y1, ..., уk) теж є (-ЧРП.

(x) визначене} є (-РПМ i не є (-РМ.

(x) невизначене} не є (-РПМ.

: Існують РФ g та h такi:

.

Обчислюванiсть вiдносно довiльної множини L визначають як обчислюванiсть вiдносно її характеристичної функцiї (L.



Функцiю називають L-ЧРФ, якщо вона (L-ЧРФ.

Множину A називають В-рекурсивною, якщо (A є (B -РФ.

є (B -ЧРФ.

Предикат P називають L-рекурсивним, якщо (P є (L-РФ.

є (L-ЧРФ.