Mavzu: Mavzu: To`liqsizlik haqidagi Gyodel teoremasi Reja

5-teorema. Rekursiv bo`lmagan effektiv rekursiv sanaluvchi natural sonlar to`plami mavjud.

• 5-teorema. Rekursiv bo`lmagan effektiv rekursiv sanaluvchi natural sonlar to`plami mavjud.
• 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.
• - hamma rekursiv sanaluvchi natural sonlar to‘plamlaridagi effektiv sanab chiqilgan to‘plamlar bo isin. Demak, har qanday nN uchun to‘plamni tiklash mumkin.

•  

Endi U to‘plamning hamma elementlarini sanab chiqadigan A algoritmni kiritaylik. Bu algoritm (m, n) qadamda m ni hisoblab chiqadi. Agar bu son n son bilan ustma-ust tushsa, bu holda A algoritm uni U to‘plamga kiritadi, ya’ni .

• Bundan ko‘rinib turibdiki, har qanday rekursiv sanaluvchi to‘plamdan CU to‘plam hech boimaganda bitta element bilan farq qiladi, chunki CU shunday n elementlardan iboratki, n. Shuning uchun ham CU rekursiv sanaluvchi to‘plam emas. Demak, Post teoremasiga asosan U rekursiv to‘plam bo`lmaydi.
• I z о h . Isbot qilingan bu teorema aslida Gyodelning formal arifmetika to’liqsizligi haqidagi teoremasini oshkormas tarzda qamrab olgan.

•  

FOYDALANILGAN ADABIYOTLAR

• FOYDALANILGAN ADABIYOTLAR
• H.T. To’rayev, I.Azizov “Matematik mantiq va diskret matematika” T.2011
• Алексеев В.Б., Кудрявцев В.Б., Сапоженко А.А, Яблонский С.В. и лр. Методическая разработка по курсу «Математическая логика и дискретная математика». 1980.
• To’rayev H.T. Mulohazalar hisobi va predikatlar mantiqi. Muammoli leksiyalar kursi. Samarqand, SamDU nashriyoti, 2003/
• Sarimsakov G.A. Haqiqiy o’zgaruvchining funksiyalar nazariyasi. Toshkent, “O’qituvchi”, 1968.
• Малъцев А.И., Алгоритмы и рекурсивные функции. М., «Наука»,1965
• Iskandarov R.I., Matematik logika elementlari. Toshkent. Samarqand, SamDU nashriyoti, 1970.
• Yakubov T., Kallibekov C. Matematik mantiq elementlari. Toshkent, “O’qituvchi”, 1996.
• Soleev A. Ordering in Complicated Problems. In 14-th British Combinatorical Conference. Keele, GB, July, 1993. Abstracts. p. 96-98.

E’tiboringiz uchun rahmat!