Mavzu: Mavzu: To`liqsizlik haqidagi Gyodel teoremasi Reja


Rekursiv va rekursiv sanaluvchi to’plamlar



Download 0,72 Mb.
bet6/7
Sana05.07.2022
Hajmi0,72 Mb.
#741311
1   2   3   4   5   6   7
Bog'liq
taqdimot.algebra.mohlaroy

5. 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.

Download 0,72 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish