Natural sonlar nazariyasi. Natural sonlar nazariyasi

Rekursiv va rekursiv sanaluvchi to’plamlar.
5. Rekursiv va rekursiv sanaluvchi to’plamlar.
Biror alfavit berilgan bo'lsin. Bu alfavitdagi hamma so‘zlar to'plamini S bilan va S to‘plamning qism to'plamini M bilan belgilaymiz.
1-ta’rif. Agar x so'zning M to'plamga qarashlilik muammosini hal qila oladigan algoritm mavjud bo'lsa, u holda M rekursiv to‘plam deb ataladi.
2-ta’rif. Agar M to ‘plamning hamma elementlarini sanab chiqa oladigan algoritm mavjud bo`lsa, u holda M effektiv rekursiv sanaluvchi to ‘plam deb ataladi.
1 – teorema. Agar M va L effektiv rekursiv sanaluvchi to 'plamlar bo`lsa, u holda ML va ML ham effektiv rekursiv sanaluvchi to`plam 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, ular orqali mos ravishda M va L dagi hamma elementlami sanab chiqish mumkin. ML va M to'plamlaming effektiv sanaluvchi algoritmi M va L to'plamlaming effektiv sanaluvchi algoritmlarini bir vaqtda qo‘llash natijasida hosil qilinadi.
2-teorema (Post teoremasi). M to ‘plamning о ‘zi va to ‘Idiruvchisi CM effektiv rekursiv sanaluvchi bo'lganda va faqat shundagina M to`plam rekursivdir.
2-teorema (Post teoremasi). M to ‘plamning о ‘zi va to ‘Idiruvchisi CM effektiv rekursiv sanaluvchi bo'lganda va faqat shundagina M to`plam rekursivdir.
Isboti. a) M to‘plam va uning CM to'ldiruvchisi effektiv rekursiv sanaluvchi bo'lsin. U holda, 2- ta’rifga asosan, bu to‘plamlaming elementlarini sanab chiqa oladigan A va В algoritmlar mavjud bo'ladi. U holda M va CM to'plamlaming elementlarini sanab chiqish paytida ularning ro'yxatida x element uchraydi. Demak, shunday С algoritm yuzaga keladiki, u orqali Jt 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 CM to‘plamlarga kiruvchi elementlarning ro‘yxatini tuzamiz. Shunday qilib, M va C M to‘plamlar elementlarini sanab chiquvchi ikkita A va В algoritmni hosil qilamiz. Demak, M va CM to‘plamlar effektiv rekursiv sanaluvchi to‘plamlar bo'ladi.