48. Відносна обчислюваність. Мнро, альфа-чрф. Теза Тьюрінга. Релятивізація теорем.

Обмежимося розглядом відносної обчислюваності n-арних функцій на N, причому обчислюваності відносно тотальних функцій.

Функція f обчислювана відносно тотальної функції , яку називають оракулом, якщо існує алгоритм для обчислення f, який може в разі необхідності брати потрібні значення функції .

Поняття відносної обчислюваності уточнимо через поняття МНР з оракулом (МНРО). Для МНРО додається новий тип команд O(n) – звернення до оракула. Для виконання таких команд МНРО мусить з'єднатися з певним оракулом . Виконання команди O(n) означає, що вміст r регістру R_n засилається в оракул , який повертає в R_n значення (r). Після виконання команди O(n) наступною буде виконуватися чергова за списком команда програми МНРО. Програма МНРО – це скінченна послідовність команд МНРО. Смисл МНРО-програми залежить від конкретного оракула. МНРО-програму P, що виконується МНРО з оракулом , позначаємо P^.

МНРО-програма P обчислює функцію f : Nⁿ N відносно оракула , або -обчислює функцію f, якщо f(a₁ , a₂ , ..., a_п)=b  P^(a₁ , a₂ , ..., a_п)b.

Функція f МНРО-обчислювана відносно , або -обчислювана, якщо існує МНРО-програма P, яка обчислює f відносно .

Функція частково рекурсивна відносно , або -ЧРФ, якщо вона отримується із функцій о, s, І та  за допомогою операцій Sⁿ⁺¹, R, M. Тотальну -ЧРФ називають -рекурсивною (-РФ).

Теорема 5.3.1. Функція f є -ЧРФ  f є -обчислювана.

Вкажемо деякі елементарні властивості -ЧРФ:

о1) ЧРФ^ (тут ЧРФ^ позначає клас всіх -ЧРФ).

о2) Для довільного оракула  маємо ЧРФ ЧРФ^.

о3) Якщо тотальна функція  є -ЧРФ, то ЧРФ^ ЧРФ^.

о4) Якщо  рекурсивна, то ЧРФ^ =ЧРФ.

Релятивний аналог тези Чорча називають тезою Тьюрінга (ТТ). Тезу Чорча можна розглядати як окремий випадок тези Тьюрінга.

Теза Тьюрінга. Клас -ЧРФ співпадає з класом n-арних функцій на N, алгоритмічно обчислюваних відносно .

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

Множину L назвемо -РПМ, якщо L= або L=E_f для деякої -РФ f.

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

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

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

R1) Рeлятивна s-m-n-тeорeма. Для довiльних m, n>1 iснує (m+1)-арна РФ s (z, x₁, ..., x_m) така, що для всiх z, x₁, ..., x_т, у₁, ..., у_п маємо  (x₁, ..., x_т, у₁, ..., у_п) =  (у₁, ..., у_п).

R2) Рeлятивна s-m-n-тeорeма в спрощеній формі. Для кожної -ЧРФ f(x, y) iснує РФ s(x) така, що для всiх x, y маємо f(x, y)= (y).

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

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

R5) Релятивна теорема Кліні про НТ. Нехай f  (n+1)-арна РФ. Тодi iснує n-арна РФ g така, що для всiх значень x₁, ..., x_п маємо  =  .

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

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

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

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

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

R7) Рeлятивна теорема Поста. Якщо L та є -РПМ, то L та є -РМ.

R8) Предикат Q(x₁, ..., x_n) є -ЧРП  ( iснує -РП R(x₁, ..., x_n, y) такий, що

Q(x₁, ..., x_n)  yR(x₁, ..., x_n, y) ).

R9) Якщо Q(x₁, ..., x_n, y) є -ЧРП, то y₁...y_kQ(x₁, ..., x_n, y₁, ..., у_k) теж є -ЧРП.

R10) Множина D^={x |  (x) визначене} є -РПМ i не є -РМ.

R11) Множина D^={x |  (x) невизначене} не є -РПМ.

49.Т-звідність, її властивості. Т-степені, їх властивості.

Інтуїтивне поняття звідності найадекватніше відбиває поняття Тьюрінгової звідності, або T-звідності: множина A T-зводиться до множини B, що позначаємо A_T B, якщо для розв'язку питання "xA" треба відповісти на скінченну кількість питань про B, але їх кількість та природа заздалегідь нам не відомі. T-звідність не має патологічних властивостей m-звідності (специфічна поведінка  та N, не завжди A_m ), яка виникає внаслідок обмеженості її природи: g : A_m B, якщо для розв'язку питання "xA" треба задати єдине питання до B, причому заздалегідь вказаним способом "g(x)B".

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

Введемо відношення T-еквівалентності _T :

A_T B, якщо A_T B та B_T A.

Писатимемо A<_T B, якщо A _T B та невірно, що B_T A.

Писатимемо A | _T B, якщо невірно A_T B та невірно B _T A.

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

t1) A_TA.

t2) Якщо A_TB та B_TC, то A_TC.

t3) Для кожної множини A маємо A_T та _T A.

t4) A_TA для кожної множини A.

t5) Якщо A_mB, то A_T B.

t6) Якщо B є РМ і A_T B, то A є РМ.

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

t8) Якщо A є РПМ, то A_T D.

Теорема 5.4.2. 1) Існує РФ h така, що _h(z) : D _mD^А для всіх А, z.

2) Існує РФ u така: для всіх A, B, z якщо _z : А _m D^В, то А = D .

Теорема 5.4.1. Множина L є A-РПМ  L_m D^A.

Наслідок 1. Якщо L є A-РПМ, то L_T D^A.

Наслідок 2. A<_T D^А для кожної множини A.

Теорема 5.4.3. A_T B  D^A_m D^B.

Наслідок 1. A_T B  D^A _m D^B.

Наслідок 2. Якщо A_T B, то D^A _T D^B.

Теорема 5.4.4. Існують РФ f та РФ h такі:

1) для всіх A, B, z якщо _A= , то _f(z) : D^A_m D^B;

2) для всіх A, B, z якщо _z : D^A_m D^B, то _A= .

Відношення _T є відношенням еквівалентності, тому вводимо класи еквівалентності d_T(A) = {B | A__TB} відносно _T. Такі класи будемо називати T-степенями, або степенями нерозв'язності.

На множині T-степенів введемо відношення часткового порядку : ab, якщо A_T B для деяких Aa, Bb.

Зрозуміло, що ab  A_T B для всіх Aa, Bb.

Будемо писати a<b, якщо ab та a  b.

Будемо писати a | b, якщо невірно ab та невірно ba.

T-степінь рекурсивна, якщо вона містить РМ.

T-степінь рекурсивно перелічна (РП), якщо вона містить РПМ.

Вкажемо деякі властивості T-степенів:

s1) Існує єдина рекурсивна T-степінь 0, яка складається із всіх РМ. Вона є найменшою T-степінню: 0<b для кожної T-степені b0.

s2) Існує найбільша рекурсивно перелічна T-степінь 0'=d_T(D) така, що b0' для кожної рекурсивно перелічної T-степені b.

s3) Кожна нерекурсивна РП-степінь містить множини, які не є РПМ.

s4) Якщо d_m(A)_m d_m(B), то d_Т(A)_Т d_Т(B).

s5) d_m(A) d_Т(A) для довільної множини A.

Теорема 5.4.5. Для кожної пари T-степенів a та b існує єдина точна верхня грань ab = d_T(AB), де Aa, Bb.

Скачком T-степені b називають степінь b'=d_T(D^B), де Bb.

Таке визначення коректне, бо за наслідком 2 теореми 5.4.3 b' не залежить від вибору конкретного представника Bb.

Вкажемо деякі властивості операції скачка.

jm1) b<b' для довільної T-степені b.

jm2) Якщо a<b, то a'<b'.

jm3) 0<b' для довільної T-степені b.

jm4) Якщо a=b, то a'=b'.

jm5) Якщо Aa, Bb та B є A-РПМ, то b<a'.

T-степінь b повна, якщо b=a' для деякої T-степені a.

Повна T-степінь складається тільки з T-повних множин.

Множина всіх повних T-степенів є множиною значень операції скачка.

Введемо операції n-кратного скачка та -скачка.

Для довільної AN покладемо A⁽⁰⁾=A, A^(k+1)= .

Для довільної T-степені a покладемо a⁽⁰⁾=a, a^(k+1)=(a^(k))'.

Вкажемо деякі властивості операції n-кратного скачка.

jn1) A⁽⁰⁾<_T A⁽¹⁾<_T ...<_T A^(k)<_T A^(k+1)<_T ... для довільної AN.

jn2) a⁽⁰⁾<a⁽¹⁾< ...<a^(k)<a^(k+1)< ... для довільної T-степені a.

jn3) Якщо A_TB, то A⁽ⁿ⁾_mB⁽ⁿ⁾ для всіх n1.

-скачок множини AN – це множина A^() ={C(x, y) | xA^(y)}.

Із цього визначення випливає: xA^()  l(x)A^(r(x))