WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Звідності. Відносна обчислюваність - Реферат

Звідності. Відносна обчислюваність - Реферат

TB та B TC, то A TC.
t3) Для кожної множини A маємо A T та 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.
Приклад 4. Існують множини А та В: А ВНаприклад, візьмемо А=N та B= .
Приклад 5. Існують множини А та В: А ВНаприклад, візьмемо А=D та B= .
Приклад 6. Не існують множини А та В: А ВЗгідно r13) А т А В, тому А Т А В. Отже, неможливо А ВПриклад 7. Не існують множини А та В: А ВЗгідно r13) В т А В, тому неможливо А ВПриклад 8. Покажемо, що А В T А В.
Маємо х А В 2х А В 2х+1 А В. Звідси отримуємо А В (х) = sg( А В(2x)+ А В(2x+1)). Отже, А В є А В-РФ.
Приклад 9. Покажемо, що А В T А В.
Маємо х А В l(х) А & r(х) В 2l(х) А В & 2r(х)+1 А В. Отже, А В (х) = А В(2l(х)) А В(2r(х)+1). Отже, А В є А В-РФ.
Приклад 10. Покажемо, що D T T D T D .
За t4) D T ; за r13) D m D , за r14) D m D , звідки за t5) маємо D T D та D T D . Враховуючи t2), досить довести D T D та D T D. Маємо х D х парне та х/2 D х непарне та (х 1)/2 D. Звідси "х D " є D-РП, тому є D-РФ. Маємо х D l(х) D & r(х) D. Звідси "х D " є D-РП, тому є D-РФ.
А-РПМ М T-повна, якщо L T М .для кожної А-РПМ L
Приклад 11. Для кожної A N множина DА ={x | (x) визначене} є T-повною A-РПМ. Це негайно випливає з наступного твердження:
Тeорeма 4.1. Множина L є A-РПМ L m DA.
Нехай L є A-РПМ. Функцiя f(x, y) = (x)+o(y) є A-ЧРФ, бо є A-ЧРФ. За релятивною s-m-n-теоремою iснує РФ s: f(x, y)= (у) для всiх x, y. При x L (у)=1 для всiх y, звiдки (s(x)) , тому s(x) DA. При x L (у) для всiх y, тому (s(x)) , звiдки s(x) DA. Отже, x L s(x) DA, тому L m DA.
Нехай РФ f : L m DA. Тодi x L s(x) DA. Але DA є A-РПМ, f є РФ, звiдки предикат "x L" є A-ЧРП. Отже, L є A-РПМ
Наслідок 1. Якщо L є A-РПМ, то L T DA.
Наслідок 2. AПриклад 12. Із прикладу 11, зокрема, дістаємо: D є T-повною РПМ.
Ефективним варіантом теореми 9.4.1 є
Тeорeма 4.2. 1) Існує РФ h така, що h(z) : D mDА для всiх А, z.
2) Існує РФ и така: для всiх A, B, z якщо z : А m DВ, то А=D .
Приклад 13. Існує РФ k(z) така: якщо z : A m B, то A= .
Функція A(x)= B( z(x)) є B-ЧРФ, тому за релятивною s-m-n-тео-ремою iснує РФ k : для всiх z, x B( z(x))= (x). Отже, A= .
За наслiдком 2 теореми 9.4.1 маємо A TDA для кожної A N. Це означає, що при переходi вiд A до DA скачкоподiбно зростає складнiсть множини, тому DA називають скачком множини A.
Операцiю, яка кожнiй множинi A N ставить у вiдповiднiсть множину DA, називають операцiєю скачка.
Теорема 4.3. A T B DA m DB.
Наслідок 1. A T B DA m DB.
Наслідок 2. Якщо A T B, то DA T DB.
Зворотне до наслiдку 2 твердження невiрне (див.[9]). Можливi випадки AЕфективним варіантом теореми 9.4.3 є
Тeорeма 4.4. 1) Існує РФ f така: для всiх A, B, z якщо A= , то f(z) : DA m DB;
2) Існує РФ h така: для всiх A, B, z якщо z : DA m DB, то A= .
Вiдношення T є вiдношенням еквiвалентностi, тому вводимо класи еквiвалентностi dT(A)={B | A T B} вiдносно T. Такi класи будемо називати T-степенями, або степенями нерозв'язностi.
На множинi T-степенiв введемо вiдношення часткового порядку, яке також будемо позначати :
a b, якщо A T B для деяких A a, B b.
Зрозумiло, що a b A T B для всiх A a, B b.
Будемо писати aБудемо писати a | b, якщо невірно a b та невірно b a.
T-степiнь назвається рекурсивною, якщо вона мiстить РМ.
T-степiнь назвається рекурсивно перелiчною (РП-T-степiнню), якщо вона мiстить РПМ.
Вкажемо деякi властивостi T-степенiв:
s1) Існує єдина рекурсивна T-степiнь 0, яка складається iз всiх РМ. Вона є найменшою T-степiнню: 0s2) Існує найбiльша рекурсивно перелiчна T-степiнь 0'=dT(D) така, що b 0' для кожної рекурсивно перелiчної T-степенi b.
s3) Кожна нерекурсивна РП-степiнь мiстить множини, якi не є РПМ.
s4) Якщо dm(A) m dm(В), то dТ(A) Т dТ(В).
s5) dm(A) dТ(A) для довiльної множини A.
Тeорeма 4.5. Для кожної пари T-степенiв a та b iснує єдина точна верхня грань a b=dT(A B), де A a, B b.
Oперацiю скачка поширимо на множину T-степенiв.
Скачком T-степенi b називають степiнь b'=dT(DB), де B b.
Таке визначення коректне, бо за наслiдком 2 теореми 9.4.3 b' не залежить вiд вибору конкретного представника B b.
Вкажемо деякi властивостi операцiї скачка.
jm1) bjm2) Якщо ajm3) 0jm4) Якщо a=b, то a'=b'.
jm5) Якщо A a, B b та B є A-РПМ, то bT-степінь b називають повною, якщо b=a' для деякої T-степені a. Повна T-степінь складається тільки з Т-повних множин. Множина всіх повних T-степенів є множиною значень операції скачка.
Введемо операцiю n-кратного скачка для множин та степенів
Для довiльної A N покладемо A(0)=A, A(k+1)= .
Для довiльної T-степенi a покладемо a(0)=a, a(k+1)=(a(k))'.
Вкажемо деякi властивостi операцiї n-кратного скачка.
jn1) A(0)jn2) a(0)jn3) Якщо A TB, то A(n) mB(n) для всiх n 1.
-скачком множини A N назвемо множину A( )={C(x, y) | x A(y)}.
Із цього визначення випливає: х А( ) l(x) А(r(x))
Приклад 14. Існує РФ f така: для всiх A, B якщо для всiх у маємо , то A( ) T B.
Маємо х А( ) l(x) А(r(x)) (згідно умови) В-РП. Отже, є В-РФ.
Приклад 15. Існує РФ така: для всiх A та у маємо .
Функція = є А( )-РФ, тому за релятивною s-m-n-теоремою існує РФ f така, що для всіх х, у маємо . Отже, .
Як наслідок звідси отримуємо, що A(у)Тeорeма 4.6. Якщо A T B, то A( ) m B( ).
Тeорeма 4.7. Існують множини A і B такi: A( ) m B( ) та B
Loading...

 
 

Цікаве