1. Rekursiv, rekursiv sanaluvchi to‘plam tushunchalari. Rekursiv va rekursiv sanaluvchi to‘plamlar xossalari. Post teoremasi

Ma’ruza: Rekursiv to‘plam. Rekursiv sanaluvchi to‘plam. Post teoremasi
Reja:
1. Rekursiv, rekursiv sanaluvchi to‘plam tushunchalari.
2. Rekursiv va rekursiv sanaluvchi to‘plamlar xossalari.
3. Post teoremasi.


1. Rekursiv, rekursiv sanaluvchi to‘plam tushunchalari
Biror alfavit berilgan bo‘lsin. Bu alfavitdagi hamma so‘zlar to‘plamini bilan va to‘plamning qism to‘plamini bilan belgilaymiz.
1-ta’rif. Agar so‘zning to‘plamga qarashlilik muammosini hal qila oladigan algoritm mavjud bo‘lsa, u holda rekursiv to‘plam deb ataladi.
2-ta’rif. Agar to‘plamning hamma elementlarini sanab chiqa oladigan algoritm mavjud bo‘lsa, u holda effektiv rekursiv sanaluvchi to‘plam deb ataladi.


2. Rekursiv va rekursiv sanaluvchi to‘plamlar xossalari
1-teorema. Agar va effektiv rekursiv sanaluvchi to‘plamlar bo‘lsa, u holda va ham effektiv rekursiv sanaluvchi to‘plam bo‘ladi.
Isboti. va effektiv rekursiv sanaluvchi to‘plamlar bo‘lsin. U holda,
2-ta’rifga asosan, ularning har biri uchun alohida algoritm mavjudki, ular orqali mos ravishda va dagi hamma elementlarni sanab chiqish mumkin. va to‘plamlarning effektiv hisoblovchi algoritmi va to‘plamlarning effektiv hisoblovchi algoritmlarini bir vaqtda qo‘llash natijasida hosil qilinadi. ■


3. Post teoremasi
2-teorema (Post teoremasi). to‘plamning o‘zi va to‘ldiruvchisi effektiv rekursiv sanaluvchi bo‘lganda va faqat shundagina to‘plam rekursivdir.
Isboti. a) to‘plam va uning to‘ldiruvchisi effektiv rekursiv sanaluvchi bo‘lsin. U holda, 2-ta’rifga asosan, bu to‘plamlarning elementlarini sanab chiqa oladigan va algoritmlar mavjud bo‘ladi. U holda va to‘plamlarning elementlarini sanab chiqish paytida ularning ro‘yxatida element uchraydi. Demak, shunday algoritm yuzaga keladiki, u orqali element to‘plamga qarashlimi yoki qarashli emasmi degan muammoni hal qilish mumkin. Shunday qilib, rekursiv to‘plam bo‘ladi.
b) rekursiv to‘plam bo‘lsin. U holda, 1-ta’rifga asosan, bu to‘plamning elementimi yoki elementi emasmi degan muammoni hal qiluvchi algoritm mavjud bo‘ladi. Bu algoritmdan foydalanib, va to‘plamlarga kiruvchi elementlarning ro‘yxatini tuzamiz. Shunday qilib, va to‘plamlar elementlarini sanab chiquvchi ikkita va algoritmni hosil qilamiz. Demak, va to‘plamlar effektiv rekursiv sanaluvchi to‘plamlar bo‘ladi. ■