Natural sonlar nazariyasi. Natural sonlar nazariyasi

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!

http://azkurs.org