Mavzu: rekursiv va rekursiv sanaluvchi to‘plamlar. Bajardi: Ro`ziyeva M

Isboti. Effektiv rekursiv sanaluvchi ixtiyoriy U natural sonlar to'plami berilgan bo'lsin. U to'plamning rekursiv emasligini isbotlash uchun. Post teoremasiga (2- teorema) ko'ra, uning CU to'ldiruvchisi effektiv rekursiv sanaluvchi emasligini isbotlash yetarli. М 0,М Х,М 2,... - hamma rekursiv sanaluvchi natural sonlar to‘plamlaridagi effektiv sanab chiqilgan to‘plamlar boisin. Demak, har qanday ne 1\ uchun M n to'plamni tiklash mumkin. Endi U to'plamning hamma elementlarini sanab chiqadigan A algoritmni kiritaylik. Bu algoritm (m.n) raqamli qadamda me M n ni hisoblab chiqadi. Agar bu son n son bilan ustma-ust tushsa, bu holda A9 algoritm uni U to'plamga kiritadi, ya’ni neU <-> tie Mit. Bundan ko'rinib turibdiki, har qanday rekursiv sanaluvchi to'plamdan CU to'plam hech bo'lmaganda bitta element bilan farq qiladi, chunki CU shunday n elementlardan iboratki, n I z о h . Isbot qilingan bu teorema aslida Gyodelning formal arifme-tika to'liqsizligi haqidagi teoremasini oshkormas tarzda qamrab olgan. Algoritm tushunchasini aniqlashdagi muammolar.

Isboti. Effektiv rekursiv sanaluvchi ixtiyoriy U natural sonlar to'plami berilgan bo'lsin. U to'plamning rekursiv emasligini isbotlash uchun. Post teoremasiga (2- teorema) ko'ra, uning CU to'ldiruvchisi effektiv rekursiv sanaluvchi emasligini isbotlash yetarli. М 0,М Х,М 2,... - hamma rekursiv sanaluvchi natural sonlar to‘plamlaridagi effektiv sanab chiqilgan to‘plamlar boisin. Demak, har qanday ne 1\ uchun M n to'plamni tiklash mumkin. Endi U to'plamning hamma elementlarini sanab chiqadigan A algoritmni kiritaylik. Bu algoritm (m.n) raqamli qadamda me M n ni hisoblab chiqadi. Agar bu son n son bilan ustma-ust tushsa, bu holda A9 algoritm uni U to'plamga kiritadi, ya’ni neU <-> tie Mit. Bundan ko'rinib turibdiki, har qanday rekursiv sanaluvchi to'plamdan CU to'plam hech bo'lmaganda bitta element bilan farq qiladi, chunki CU shunday n elementlardan iboratki, n I z о h . Isbot qilingan bu teorema aslida Gyodelning formal arifme-tika to'liqsizligi haqidagi teoremasini oshkormas tarzda qamrab olgan. Algoritm tushunchasini aniqlashdagi muammolar.