Sanaluvchi to’plamlar panjarasi. Maykil teoremasi

Reja:

1. 
   Sanaluvchi to’plamlar panjarasi.
   

2. 
   Maykil teoremasi.
   

3. Algaritmik darajalar.

4. 
   Tyuring darajalari.
   

Sanaluvchi to’plamlar panjarasi

Biror alfavit berilgan bo‘lsin. Bu alfavitdagi hamma so‘zlar to‘plamini
S
bilan va
S

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
L

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
CM

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
X ≡T Y nazarda tutadi Y ≡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