Mavzu: rekursiv va rekursiv sanaluvchi to‘plamlar. Bajardi: Ro`ziyeva M

Rekursiv va rekursiv sanaluvchi to‘plamlar xossalari. 1- teorema. Agar M va L effektiv rekursiv sanaluvchi to'plamlar bo ‘Isa, и holda M U L va M C\L ham effektiv rekursiv sanaluvchi to ‘plant bo ‘ladi. Isboti. M va L effektiv rekursiv sanaluvchi to'plamlar bo‘lsin. U holda, 2- ta’rifga asosan, ularning har biri uchun alohida algoritm mavjudki, utar orqali mos ravishda M va f dagi hamma elementlami sanab chiqish mumkin. M{J L va M f]L to'plamlarning effektiv sanaluvchi algoritmi M va L to'plamlarning effektiv sanaluvchi algoritmlarini bir vaqtda qo‘llash natijasida hosil qilinadi. 2-t e o r e m a (Post teoremasi). M to ‘plamning о ‘zi va to ‘Idiruvchisi CM effektiv rekursiv sanaluvchi bo'lganda va faqat shundagina M to plam rekursivdir.

Rekursiv va rekursiv sanaluvchi to‘plamlar xossalari. 1- teorema. Agar M va L effektiv rekursiv sanaluvchi to'plamlar bo ‘Isa, и holda M U L va M C\L ham effektiv rekursiv sanaluvchi to ‘plant bo ‘ladi. Isboti. M va L effektiv rekursiv sanaluvchi to'plamlar bo‘lsin. U holda, 2- ta’rifga asosan, ularning har biri uchun alohida algoritm mavjudki, utar orqali mos ravishda M va f dagi hamma elementlami sanab chiqish mumkin. M{J L va M f]L to'plamlarning effektiv sanaluvchi algoritmi M va L to'plamlarning effektiv sanaluvchi algoritmlarini bir vaqtda qo‘llash natijasida hosil qilinadi. 2-t e o r e m a (Post teoremasi). M to ‘plamning о ‘zi va to ‘Idiruvchisi CM effektiv rekursiv sanaluvchi bo'lganda va faqat shundagina M to plam rekursivdir.

I s b о t i .a) M to'plam va uning CM to'ldiruvchisi effektiv rekursiv sanaluvchi bo'lsin. U holda, 2- ta’rifga asosan, bu to'plamlarning elementlarini sanab chiqa oladigan A va В algoritmlar mavjud bo'ladi.

U holda M va CM to'plamlarning elementlarini sanab chiqish paytida ularning ro'yxatida x element uchraydi. Demak, shunday С algoritm yuzaga keladiki, u orqali x element M to'plamga qarashlimi yoki qarashli emasmi degan muammoni hal qilish mumkin. Shunday qilib, M rekursiv to'plam bo'ladi. b) M rekursiv to'plam bo'lsin. U holda, 1- ta’rifga asosan, x bu to'plamning elementimi yoki elementi emasmi degan muammoni hal qiluvchi algoritm mavjud bo'ladi. Bu algoritmdan foydalanib, M va CM7 to'plamlarga kiruvchi elementlarning ro'yxatini tuzamiz. Shunday qilib, M va CM to'plamlar elementlarini sanab chiquvchi ikkita A va В algoritmni hosil qilamiz. Demak, M va CM to'plamlar effektiv rekursiv sanaluvchi to'plamlar bo'ladi. 1-misol. M = {1, 4, 9,...,n2,...} natural sonlar kvadratlari to'plami effektiv rekursiv sanaluvchi to'plam bo'Iishi yoki bo'lmasligini aniqlaymiz. M to'plam effektiv rekursiv sanaluvchi to'plam bo'ladi, chunki uning elementlarini hosil qilish uchun ketma-ket natural sonlarni olib, ularni kvadratga ko'tarish kerak. Bu to'plam ham rekursiv bo'ladi.