Algoritmlar 10-ma’ruza X. X. Ro’zimuradov

Yurish raqami	Boshlovchining yurishi
Raqibning yurishi
1	3	n
2	4-n	m
3	4-m	p
4	4-p	O

Haqiqatan ham, boshlovchi bunday strategiya natijasida 3+(4-n)+(4-m)+(4-p)=15-(n+m+p) predmet oladi va raqib n+m+p predmet oladi, ya’ni ikkalasi birgalikda 15 ta predmet oladilar. Oxirgi predmetni boshlovchi olganligi tufayli, u o’yinni yutadi.
Yechiluvchi va sanaluvchi to’plamlar
Qandaydiralfavitberilganbo’lsin. Bu alfavitdagihammaso’zlarto’plaminibilanvato’plamningqismto’plaminibilanbelgilaymiz.
1-ta’rif. Agar so’zningto’plamgaqarashlilikmuammosinihalqilaoladiganalgoritmmavjudbo’lsa, u holdagayechiluvchito’plam deb aytiladi.
2-ta’rif. Agar M to’plamning hamma elementlarini sanab chiqa oladigan algoritm mavjud bo’lsa, u holda M ga effektiv sanaluvchi to’plam deb aytiladi.
1-teorema.Agar va lar effektivsanaluvchito’plamlarbo’lsa, u holdavalar ham effektivsanaluvchito’plamlardaniboratbo’ladi.
Isbot.valar effektivsanaluvchito’plamlarbo’lsin. U vaqtda, 2-ta’rifga asosan, ularninghar biri uchunalohidaalgoritmmavjudki, ularorqalimosravishdavadagihammaelementlarnisanabchiqishmumkin.vato’plamlarningeffektivhisoblovchialgoritmivato’plamlarningeffektivhisoblovchialgoritmlarinibirvaqtdaqo’llashnatijasidahosilqilinadi.

2-teorema (Post teoremasi). M to’plamning o’zi va uning CM to’ldiruvchisi effektiv sanaluvchi bo’lganda, va faqat shundagina M to’plam yechiluvchidir.

Isbot. a) M to’plam va uning CM to’ldiruvchisi effektiv sanaluvchi bo’lsin. U vaqtda, 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 qarashli yoki qarashli emasligini hal qilish mumkin. Shunday qilib, M yechiluvchi to’plam bo’ladi.