Sanaluvchi to’plamlar panjarasi. Maykil teoremasi
Yüklə 21,55 Kb.
|
|
Reja:
Sanaluvchi to’plamlar panjarasi. Maykil teoremasi. 3. Algaritmik darajalar. Tyuring darajalari. Sanaluvchi to’plamlar panjarasi Biror alfavit berilgan bo‘lsin. Bu alfavitdagi hamma so‘zlar to‘plamini
to‘plamning qism to‘plamini M bilan belgilaymiz. 1- t a ’ r i f . 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- t a ’ r i f . Agar M to‘plamning hamma elementlarini sanab chiqa oladigan algoritm mavjud bo‘lsa, u holda M effektiv rekursiv sanaluvchi to‘plam deb ataladi. Rekursiv va rekursiv sanaluvchi to‘plamlar xossalari. 1- t e o r e m a . Agar M va L effektiv rekursiv sanaluvchi to‘plamlar bo‘lsa, u holda L M va
M ham effektiv rekursiv sanaluvchi to‘plam bo‘ladi. I s b o t i . M va L effektiv rekursiv sanaluvchi to‘plamlar bo‘lsin. U holda, 80 2- ta’rifga asosan, ularning har biri uchun alohida algoritm mavjudki, ular orqali mos ravishda M va L dagi hamma elementlarni sanab chiqish mumkin. L M va L M to‘plamlarning effektiv hisoblovchi algoritmi M va L to‘plamlarning effektiv hisoblovchi algoritmlarini bir vaqtda qo‘llash natijasida hosil qilinadi. ■ 2- t e o r e m a (Post teoremasi). M to‘plamning o‘zi va to‘ldiruvchisi CM effektiv rekursiv sanaluvchi bo‘lganda va faqat shundagina M to‘plam rekursivdir. I s b o t i . a) M to‘plam va uning CM to‘ldiruvchisi effektiv rekursiv sanaluvchi bo‘lsin. U holda, 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 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
to‘plamlar elementlarini sanab chiquvchi ikkita A va B algoritmni hosil qilamiz. Demak, M va CM to‘plamlar effektiv rekursiv sanaluvchi to‘plamlar bo‘ladi. ■ 1- m i s o l . ,...} ,..., 9 , 4 , 1 { 2 n M natural sonlar kvadratlari to‘plami effektiv rekursiv sanaluvchi to‘plam bo‘lishi yoki bo‘lmasligini aniqlaymiz. M to‘plam effektiv rekursiv sanaluvchi to‘plam bo‘ladi, chunki uning elementlarini hosil qilish uchun ketma-ket natural sonlarni olib, ularni kvadratga ko‘tarish kerak. Bu to‘plam ham rekursiv bo‘ladi. Haqiqatan ham, birorta x natural sonning M to‘plamga kirish yoki kirmasligini aniqlash uchun uni tub ko‘paytuvchilarga ajratish kerak. Bu usul x natural son biror natural sonning kvadratimi yoki yo‘qmi degan savolga javob topish imkonini beradi. Maykil teoremasi: Matematikada bir xillik teoremasi har bir narsani aytadi oddiygina ulangan Riemann yuzasi bu mos ravishda teng Rimanning uchta sathidan biriga: ochiq birlik disk, murakkab tekislikyoki Riman shar. Xususan, bu har bir Riemann sirtining a ni tan olishini anglatadi Riemann metrikasi ning doimiy egrilik. Rimanning ixcham sirtlari uchun birlikning diskini universal qoplaganlar, aniqrog'i 1 dan katta bo'lgan giperbolik yuzalar, barchasi abeliya bo'lmagan fundamental guruhga ega; universal qoplamali murakkab tekislik - bu 1-turdagi Riemann sirtlari, ya'ni murakkab tori yoki elliptik egri chiziqlar asosiy guruh bilan Z2; va Riman doirasini universal qopqog'iga ega bo'lganlar nolga mansub, ya'ni ahamiyatsiz fundamental guruhga ega Riman sharining o'zi. Formalash teoremasi - ning umumlashtirilishi Riemann xaritalash teoremasi to'g'ri ulanganidan ochiq pastki to'plamlar tekislikning o'zboshimchalik bilan oddiygina bog'langan Riman sirtlariga. Formalash teoremasi, shuningdek, yopiq Riemann 2-manifoldlari bo'yicha ekvivalent bayonotga ega: har bir bunday manifold doimiy egrilikka ega bo'lgan konformal ravishda teng Riemann metrikasiga ega. Formalash teoremasining ko'plab klassik dalillari haqiqiy qiymatni yaratishga tayanadi harmonik funktsiya oddiygina bog'langan Riemann yuzasida, ehtimol bir yoki ikki nuqtada o'ziga xoslik bilan va ko'pincha bir shaklga mos keladi Yashilning vazifasi. Garmonik funktsiyani qurishning to'rtta usuli keng qo'llaniladi: Perron usuli; The Shvartsning o'zgaruvchan usuli; Dirichlet printsipi; va Veylortogonal proektsiyalash usuli. Yopiq Riemann 2-manifoldlari sharoitida bir nechta zamonaviy isbotlar konformal ekvivalent metrikalar maydonida chiziqli bo'lmagan differentsial tenglamalarni keltirib chiqaradi. Ular orasida Beltrami tenglamasi dan Teyxmuller nazariyasi va jihatidan ekvivalent formulasi harmonik xaritalar; Liovil tenglamasi, allaqachon Puankare tomonidan o'rganilgan; va Ricci oqimi boshqa chiziqli bo'lmagan oqimlar bilan birga. Algaritmik darajalar 1. Algoritmning so‘zlar orqali ifodalanishi. Bu usulda ijrochi uchun beriladigan har bir ko‘rsatma jumlalar, so‘zlar orqali buyruq shaklida beriladi. 2. Algoritmning formulalar bilan berilish usulidan matematika, fizika, kimyo kabi aniq fanlardagi formulalarni o‘rganishda foydalaniladi. Bu usulni ba’zan analitik ifodalash deyiladi. 3. Algoritmlarning grafik shaklida tasvirlanishida algoritmlar maxsus geometrik figuralar yordamida tasvirlanadi va bu grafik ko‘rinishi blok-sxema deyiladi. 4. Algoritmning jadval ko‘rinishda berilishi. Algoritmning bu tarzda tasvirlanishdan ham ko‘p foydalanamiz. Masalan, maktabda qo‘llanib kelinayotgan to‘rt xonali matematik jadvallar yoki turli xil lotereyalar jadvallari. Funksiyalarning grafiklarini chizishda ham algoritmlarning qiymatlari jadvali ko‘rinishlaridan foydalanamiz. Bu kabi jadvallardan foydalanish algoritmlari sodda bo‘lgan tufayli ularni o‘zlashtirib olish oson. Yuqorida ko‘rilgan algoritmlarning tasvirlash usullarining asosiy maqsadi, qo‘yilgan masalani yechish uchun zarur bo‘lgan amallar ketma-ketligining eng qulay holatinni aniqlash va shu bilan odam tomonidan programma yozishni yanada osonlashtirishdan iborat. Aslida programma ham algoritmning boshqa bir ko‘rinishi bo‘lib, u insonning kompyuter bilan muloqotini qulayroq amalga oshirish uchun mo‘ljallangan. Tyuring darajalari Tyuring darajasi tushunchasi hisoblash nazariyasi, bu erda natural sonlar to'plami ko'pincha ko'rib chiqiladi qaror bilan bog'liq muammolar. To’plamning Tyuring darajasi - bu to’plam bilan bog’liq qaror qabul qilish muammosini hal qilishning qanchalik qiyinligini, ya’ni ixtiyoriy sonning berilgan to’plamda ekanligini aniqlash. Ikki to'plam Turing ekvivalenti agar ular bir xil darajada hal qilinmaydigan darajaga ega bo'lsa; har bir Turing darajasi Turing ekvivalenti to'plamlarining to'plamidir, shuning uchun Turing ekvivalenti bo'lmaganida ikkita to'plam aynan Turing darajalarida bo'ladi. Bundan tashqari, Turing darajalari qisman buyurtma qilingan shuning uchun agar to'plamning Turing darajasi X to'plamning Tyuring darajasidan kam Y unda raqamlar mavjudligini to'g'ri hal qiladigan har qanday (hisoblanmaydigan) protsedura Y raqamlarning kirishini to'g'ri hal qiladigan protseduraga samarali ravishda o'tish mumkin X. Aynan shu ma'noda to'plamning Tyuring darajasi uning algoritmik echib bo'lmaydigan darajasiga to'g'ri keladi. Turing darajalari tomonidan kiritilgan Emil Leon Post (1944) va ko'plab asosiy natijalar tomonidan belgilandi Stiven Koul Klayn va Post (1954). O'shandan beri Turing darajalari qizg'in izlanishlar sohasi bo'lib kelgan. Hududdagi ko'plab dalillar, deb nomlanuvchi isbotlash texnikasidan foydalanadi ustuvor usul. Ikki to'plam X va Y deb belgilangan Turing ekvivalenti agar X Turing kamaytirilishi mumkin Y va Y Turing kamaytirilishi mumkin X. Notation X ≡T Y buni bildiradi X va Y Turing ekvivalenti. ≡ munosabatiT bo'lishi mumkin ekvivalentlik munosabati, demak, barcha to'plamlar uchun X, Yva Z: X ≡T X
Agar X ≡T Y va Y ≡T Z keyin X ≡T Z. A Turing darajasi bu ekvivalentlik sinfi munosabatning ofT. Yozuv [X] to'plamni o'z ichiga olgan ekvivalentlik sinfini bildiradi X. Tyuring darajalarining butun to'plami belgilangan { mathcal {D}}. Turing darajalari a ga ega qisman buyurtma ≤ shunday aniqlangan: [X] ≤ [Y] agar va faqat agar X ≤T Y. Barcha hisoblanadigan to'plamlarni o'z ichiga olgan noyob Turing darajasi mavjud va bu daraja boshqa darajalardan kam. U belgilanadi 0 (nol), chunki u posetning eng kichik elementi { mathcal {D}}. (Turing darajalari uchun ularni qalinlikdan farqlash uchun qalin yozuvlarni ishlatish odatiy holdir. Hech qanday chalkashlik yuzaga kelmasa, masalanX], qalin harf shart emas.) Har qanday to'plam uchun X va Y, X qo'shilish Y, yozma X ⊕ Y, to'plamlarning birlashishi deb belgilangan {2n : n ∈ X} va {2m+1 : m ∈ Y}. Turing darajasi X ⊕ Y bo'ladi eng yuqori chegara daraja X va Y. Shunday qilib { mathcal {D}} a semilattice qo'shilish. Darajalarning eng yuqori chegarasi a va b bilan belgilanadi a ∪ b. Ma'lumki { mathcal {D}} panjara emas, chunki eng katta pastki chegarasi bo'lmagan juft darajalar mavjud. Har qanday to'plam uchun X yozuv X′ Foydalanishda to'xtab qoladigan oracle mashinalari indekslari to'plamini bildiradi X oracle sifatida. To'plam X′ Ga Turing sakrash ning X. Tyuring darajasining sakrashi [X] daraja deb belgilangan [X′]; bu to'g'ri ta'rif, chunki X′ ≡T Y′ Har doim X ≡T Y. Bunga asosiy misol 0′, Darajasi muammoni to'xtatish. Har bir Turing darajasi nihoyatda cheksiz, ya'ni u to'liq o'z ichiga oladi aleph _ {0} to'plamlar. Lar bor 2 ^ { aleph _ {0}} aniq Turing darajalari. Har bir daraja uchun a qat'iy tengsizlik a < a′ Ushlab turadi. Har bir daraja uchun a, quyida joylashgan darajalar to'plami a bu hisoblanadigan. Dan katta darajalar to'plami a o'lchamga ega 2 ^ { aleph _ {0}}. Turing darajalarining tuzilishi bo'yicha juda ko'p tadqiqotlar o'tkazildi. Quyidagi so'rovnomada ma'lum bo'lgan ko'plab natijalarning ba'zilari keltirilgan. Tadqiqotdan kelib chiqadigan bitta umumiy xulosa shuki, Turing darajalarining tuzilishi nihoyatda murakkab. Buyurtma xususiyatlari Lar bor minimal darajalar. Bir daraja a bu minimal agar a nolga teng va o'rtasida daraja yo'q 0 va a. Shunday qilib darajalar bo'yicha tartib munosabati a emas zich tartib. Har bir nol daraja uchun a daraja bor b bilan taqqoslab bo'lmaydi a. To'plam mavjud 2 ^ { aleph _ {0}} tengsiz teng Turing darajalari. Eng pastki chegara bo'lmagan daraja juftlari mavjud. Shunday qilib { mathcal {D}} panjara emas. Qisman buyurtma qilingan har bir to'plam Turing darajasida joylashtirilishi mumkin. Hech qanday cheksiz, qat'iy ravishda ortib boruvchi ketma-ketlikning eng yuqori chegarasi yo'q. Sakrash bilan bog'liq xususiyatlar Har bir daraja uchun a o'rtasida qat'iy daraja mavjud a va a ′. Darhaqiqat, o'rtasida tengsiz darajalarning hisoblangan oilasi mavjud a va a ′. Bir daraja a shakldadir b ′ agar va faqat agar 0′ ≤ a. Har qanday daraja uchun a daraja bor b shu kabi a < b va b ′ = a ′; bunday daraja b deyiladi past ga bog'liq a. Cheksiz ketma-ketlik mavjud amen daraja shunday a′men+1 ≤ amen har biriga men. Mantiqiy xususiyatlar Simpson (1977) ning birinchi darajali nazariyasi { mathcal {D}} tilda ⟨ ≤, = ⟩ yoki ⟨ ≤, ′, =⟩ bu ko'p ekvivalenti haqiqiy ikkinchi darajali arifmetikaning nazariyasiga. Bu shuni ko'rsatadiki { mathcal {D}} juda murakkab. Shore and Slaman (1999) sakrash operatori darajalarning birinchi tartibli tuzilishida structure ≤, = language tili bilan aniqlanishi mumkinligini ko'rsatdi. XULOSA: Dastlab mulohazalar algebrasining formula tushunchasiga murojaat qilib, intiutiv ravishda, uni berilgan elementar mulohazalardan inkor, diz’yunksiya, kon’yunksiya, implikasiya, ekvivalensiya mantiqiy amallarining chekli kombinatsiyasi va, zarur bo‘lganda, mulohazalar ustida mantiqiy amallarning bajarilish tartibini ko‘rsatuvchi qavslar vositasida hosil qilingan murakkab mulohaza deb tushunamiz. Bu yerda qavslarni ishlatish qoidalari sonlar bilan ish ko‘ruvchi (oddiy) algebradagidek saqlanadi. 1.Mulohazalar algebrasi mazmun formula tushunchasiga tayanadi; 2.Teng kuchli formulalar yordamida berilgan formulalar bir ko’rinishda bosqa ko’rinishga o’tadi; 3.Aynan chin, aynan yolg‘on va bajariluvchi formulalar yordamida berilgan formulalarning mohiyatii o’rganildi; 4.Asosiy tengkuchliliklar, teng kuchli formulalarga doir teoremalar tadbiqi murakkab formulalar xususiyati o’rganildi Yüklə 21,55 Kb. Dostları ilə paylaş:
|