Teng kuchli formulalar va asosiy teng kuchliliklar Ta’rif

t a ’ r i f . Agar M to‘plamning hamma elementlarini sanab chiqa oladigan algoritm mavjud bo‘lsa, u holda M effektiv rekursiv sanaluvchi to‘plam deb ataladi.

Rekursiv va rekursiv sanaluvchi to‘plamlar xossalari.

1- t e o r e m a . Agar M va L effektiv rekursiv sanaluvchi to‘plamlar bo‘lsa, u holda
M  Lva M  L
ham effektiv rekursiv sanaluvchi to‘plam bo‘ladi.
I s b o t i . 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 elementlarni sanab chiqish mumkin.
M  L
va M  L
to‘plamlarning effektiv
hisoblovchi algoritmi M va L to‘plamlarning effektiv hisoblovchi algoritmlarini bir vaqtda qo‘llash natijasida hosil qilinadi. ■
2- t e o r e m a (Post teoremasi). M to‘plamning o‘zi va to‘ldiruvchisi CM effektiv rekursiv sanaluvchi bo‘lganda va faqat shundagina M to‘plam rekursivdir.
I s b o 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 B algoritmlar mavjud bo‘ladi. U holda M va CM to‘plamlarning elementlarini sanab chiqish paytida ularning ro‘yxatida x element uchraydi. Demak, shunday C 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 CM to‘plamlarga kiruvchi elementlarning ro‘yxatini tuzamiz. Shunday qilib, M va CM to‘plamlar elementlarini sanab chiquvchi ikkita A va B algoritmni hosil qilamiz. Demak, M va CM to‘plamlar effektiv rekursiv sanaluvchi to‘plamlar bo‘ladi.