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

позначатимемо вiдповiдно ЧРФL та РФL.

(x)=nsg((A(x)).

Приклад 5. Якщо A є B-РМ i B є C-РМ, то A є C-РМ.

Якщо B є C-РМ, то (B є (C-РФ, звiдки маємо ЧРФB (ЧРФC. Але A є B-РМ, тобто (A(ЧРФB, звiдки (A(ЧРФC.

Приклад 6. Якщо A є B-РПМ i B є C-РМ, то A є C-РПМ.

(ЧРФB (ЧРФC.

Приклад 7. Якщо A є B-РМ i B є C-РПМ, то не завжди A є C-РПМ.

не є C-РПМ

4. ПОНЯТТЯ T-ЗВІДНОСТІ. T-СТЕПЕНІ

. Така патологія m-звiдностi виникає внаслiдок обмеженостi її природи: g: A(m B, якщо для розв'язку питання "x(A" треба задати єдине питання до B, причому заздалегiдь вказаним способом "g(x)(B".

Множина A називається T-звiдною до множини B, якщо множина A є B-рекурсивною. Цей факт позначатимемо A(TB.

Введемо вiдношення T-еквiвалентностi (T :

A(T B, якщо A(T B та B(T A.

Писатимемо A
Писатимемо A | T B, якщо невiрно A(T B та невiрно B( T A.

Вкажемо елементарнi властивостi T-звiдностi:

t1) A(TA.

t2) Якщо A(TB та B(TC, то A(TC.

(T A.

t4) A(T A для кожної множини A.

t5) Якщо A(mB, то A(T B.

t6) Якщо B є РМ i A(T B, то A є РМ.

t7) Якщо A є РМ, то A(T B для кожної множини B.

t8) Якщо A є РПМ, то A(T D.

Приклад 1. Існують множини А та В: А(В
Наприклад, візьмемо А=D та B=(.

Приклад 2. Існують множини А та В: А<т А(В та А (T А(В.

Наприклад, візьмемо А=N та B=(.

Приклад 3. Існують множини А та В: А
Наприклад, візьмемо А=N та B=D.