Natural sonlar nazariyasi. Natural sonlar nazariyasi


Rekursiv va rekursiv sanaluvchi to’plamlar



Yüklə 50 Kb.
səhifə5/6
tarix22.12.2023
ölçüsü50 Kb.
#189468
1   2   3   4   5   6
Dildora

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.

Yüklə 50 Kb.

Dostları ilə paylaş:
1   2   3   4   5   6




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin