1. Har biriga “ha” yoki “yo‘q” degan javob berish mumkin bo‘lgan ayrim sanoqli-cheksiz matematik yoki mantiqiy masalalar sinfini ko‘raylik. Chekli son qadamda ushbu sinfdagi har qanday savolga biz javob bera oladigan jarayon (protsedura)
Download 17.97 Kb.
|
10-topshiriiiq
|
10 topshiriq savolga javob 1. Har biriga “ha” yoki “yo‘q” degan javob berish mumkin bo‘lgan ayrim sanoqli-cheksiz matematik yoki mantiqiy masalalar sinfini ko‘raylik. Chekli son qadamda ushbu sinfdagi har qanday savolga biz javob bera oladigan jarayon (protsedura) mavjudmi? Agar shunday protsedura mavjud bo‘lsa, u holda u berilgan savollar sinfi uchun yechuvchi protsedura yoki yechuvchi algoritm (algorifm) deb ataladi.
bo‘lsa, u holda u berilgan savollar sinfi uchun yechuvchi protsedura yoki yechuvchi algoritm (algorifm) deb ataladi. Yechuvchi protsedurani izlash muammosi bu sinf uchun yechilish muammosi deb ataladi 3. Aytilganlarni hisobga olib algoritmning quyidagi intuitiv ta’rifini berish mumkin. 1- t a ’ r i f. Berilgan ommaviy muammodagi barcha masalalarni umumiy bir xil shaklda, aniq ma’lum bo‘lgan usul bilan yechish jarayoni algoritm deb ataladi. Bunday ta’rifni qat’iy deb hisoblash mumkin emas. Haqiqatan ham, unda aniq mazmuni noma’lum so‘zlar uchraydi. Bu fikr, xususan, «usul» so‘ziga ham tegishlidir. Shuning uchun ham algoritmning bu qat’iy bo‘lmagan ta’rifi intuitiv ta’rifdir. 4. Algoritmning xarakterli hususiyatlariga algoritmnining diskretligi, determinatsiyalanuvchanligi, elementarligi, natijaviyligi kiradi.
dastlabki chekli sistemasi berilgan bo‘lib, har bir navbatdagi momentda miqdorlar sistemasi ma’lum aniqlangan qonun (dastur) asosida oldingi holatdagi miqdorlar sistemasidan hosil qilinadi. Algoritmning determinatsiyalanuvchanligi (aniqlanuvchanligi). Boshlang‘ich holatdan farq qiluvchi boshqa holatda aniqlangan miqdorlar sistemasi ilgarigi holatlarda hosil qilingan miqdorlar sistemasi orqali bir qiymatli aniqlanadi. Algoritm qadamlarining elementarligi. Ilgarigi miqdorlar sistemasidan keyingisini hosil qilish qonuni sodda qadamlardan iborat bo‘lishi kerak. Algoritmning ommaviyligi. Boshlang‘ich miqdorlar sistemasini ayrim potensial cheksiz to‘plamdan tanlash mumkin. Algoritmning natijaviyligi. Miqdorlarni topish jarayoni chekli bo‘lishi va natijani (masalaning yechimini) berishi kerak. 6. 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. 7. 1- t e o r e m a . Agar M va L effektiv rekursiv sanaluvchi to‘plamlar bo‘lsa, u holda M L va M L ham effektiv rekursiv sanaluvchi to‘plam bo‘ladi 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 3- t e o r e m a . Rekursiv bo‘lmagan effektiv rekursiv sanaluvchi natural sonlar to‘plami Mavjud
8. Algoritm tushunchasini aniqlash bo‘yicha yondashishlarni uch asosiy yo‘nalishga bo‘lish mumkin. Birinchi yo‘nalish effektiv hisoblanuvchi funksiya tushunchasini aniqlash bilan bog‘liq. Bu yo‘nalish bo‘yicha A.Chyorch, K.Gyodel, S.Klini40 tadqiqot ishlariniolib borishgan. 1932-1935 yillar davomida A.Chyorch va S.Klini tomonidan o‘rganilgan va « -aniqlanuvchi funksiyalar» deb atalgan, to‘g‘ri aniqlangan hisoblanuvchi nazariy-sonli funksiyalar sinfining « - aniqlanuvchi funksiyalar» sinfi bizning intuitiv tasavvurimiz bo‘yicha hisoblanuvchi deb qaraladigan hamma funksiyalarni qamrab olishi mumkin degan fikr tug‘ilganligi 1935 yilda e’lon qilindi. Bu kutilmagan natija edi. IkkinchiIkkinchi yo‘nalish algoritm tushunchasini bevosita aniqlash bilan bog‘liq: 1936-1937 yillarda, A.Tyuring42 Chyorch ishlaridan bexabar holda yangi funksiyalar sinfini kiritdi. Bu funksiyalarni «Tyuring bo‘yicha hisoblanuvchi funksiyalar» deb atadilar. Uchinchi yo‘nalish – Rossiya matematigi A.Markov43 tomonidan ishlab chiqilgan normal algoritmlar tushunchasi bilan bog‘liq.
yo‘nalish bo‘yicha A.Chyorch, K.Gyodel, S.Klini40 tadqiqot ishlarini olib borishgan. 1936 yilda Chyorch quyidagi tezisni e’lon qildi: har qanday intuitiv effektiv (samarali) hisoblanuvchi funksiyalar umumrekursiv funksiyalardir. 10. J.Erbranning41 bir g‘oyasi asosida 1934 yilda K.Gyodel tomonidan aniqlangan va «umumrekursiv funksiyalar» deb atalgan boshqa hisoblanuvchi funksiyalar sinfi ham « - aniqlanuvchi funksiyalar» xossalariga o‘xshash xossalarga ega edi. 1936 yilda A.Chyorch va S.Klini tomonidan bu ikkita sinf bir xil sinf ekanligi isbotlandi, ya’ni har qanday l-aniqlanuvchi funksiya umumrekursiv funksiya bo‘lishi va har qanday umumrekursiv funksiya l-aniqlanuvchi funksiya ekanligi tasdiqlandi. 11. 1936 yilda Chyorch quyidagi tezisni e’lon qildi: har qanday intuitiv effektiv (samarali) hisoblanuvchi funksiyalar umumrekursiv funksiyalardir. Bu teorema emas, balki tezisdir: tezis tarkibida intuitiv aniqlangan effektiv hisoblanuvchi funksiya tushunchasi, aniq matematik atamalarda aniqlangan umumrekursiv funksiya tushunchasi bilan aynan tenglashtirilgan. Shuning uchun bu tezisni isbotlash mumkin emas. Ammo Chyorch va boshqa olimlar tomonidan bu tezisni quvvatlovchi ko‘p dalillar ko‘rsatildi. 12. 1932-1935 yillar davomida A.Chyorch va S.Klini tomonidan o‘rganilgan va « -aniqlanuvchi funksiyalar» deb atalgan, to‘g‘ri aniqlangan hisoblanuvchi nazariy-sonli funksiyalar sinfining « - aniqlanuvchi funksiyalar» sinfi bizning intuitiv tasavvurimiz bo‘yicha hisoblanuvchi deb qaraladigan hamma funksiyalarni qamrab olishi mumkin degan fikr tug‘ilganligi 1935 yilda e’lon qilindi. Bu kutilmagan natija edi.
hisoblanuvchi funksiyalar umumrekursiv funksiyalardir. Bu teorema emas, balki tezisdir: tezis tarkibida intuitiv aniqlangan effektiv hisoblanuvchi funksiya tushunchasi, aniq matematik atamalarda aniqlangan umumrekursiv funksiya tushunchasi bilan aynan tenglashtirilgan. Shuning uchun bu tezisni isbotlash mumkin emas. Ammo Chyorch va boshqa olimlar tomonidan bu tezisni quvvatlovchi ko‘p dalillar korsatildi. 14. J.Erbranning41 bir g‘oyasi asosida 1934 yilda K.Gyodel tomonidan aniqlangan va «umumrekursiv funksiyalar» deb atalgan boshqa hisoblanuvchi funksiyalar sinfi ham « - aniqlanuvchi funksiyalar» xossalariga o‘xshash xossalarga ega edi.
yillarda, A.Tyuring42 Chyorch ishlaridan bexabar holda yangi funksiyalar sinfini kiritdi. Bu funksiyalarni «Tyuring bo‘yicha hisoblanuvchi funksiyalar» deb atadilar. Bu sinf ham yuqorida aytilgan xossalarga ega edi va buni Tyuring tezisi deb aytamiz. 1937 yilda A.Tyuring isbotladiki, uning hisoblanuvchi funksiyalari l -aniqlanuvchi funksiyalarning o‘zi va, demak, umumrekursiv funksiyalarning xuddi o‘zi ekan. Shuning uchun Chyorch tezisi bilan Tyuring tezisi ekvivalentdir.
ma’lum bo‘lsa, u holda uni realizasiya qilish uchun shu algoritmda aniq yoritilgan ko‘rsatmalarni ijro qilish zarur. Algoritmni realizasiya qilish jarayonini avtomatlashtirish g‘oyasi, tabiiyki, inson bajaradigan ishni mashinaga uzatishni taqozo qiladi. Bunday mashinani XX asrning 30- yillarida E.Post va A.Tyuring tavsiya etishgan. Tyuring mashinasi tushunchasi intuitiv ma’lum bo‘lgan hisoblash protsedurasini elementar operasiyalarga ajratish natijasida hosil bo‘lgan. Tyuring ta’kidlaydiki, istalgan mumkin bo‘lgan hisoblashni o‘tkazish uchun uning elementar operasiyalarini qaytarish yetarli. Tyuring ayrim turdagi nazariy hisoblash mashinasini izohlab berdi. Bu mashina muayyan mexanik qurilma emas, balki «xayoliy» matematik mashinadir. Berilgan ko‘rsatmani bajaruvchi hisoblovchi odamdan yoki mavjud raqamli hisoblash mashinasidan Tyuring mashinasi ikki jihati bilan farq qiladi. 18. 1936 yilda E.Post (Tyuring ishlaridan bexabar holda) aynan Tyuring erishgan natijalarga mos keladigan natijalarni e’lon qildi va 1943 yilda, 1920-1922 yillardagi nashr etilmagan ishlariga asoslanib, to‘rtinchi ekvivalent tezisni nashr etdi. Shunday qilib, algoritm tushunchasini bevosita aniqlashga va so‘ngra uning yordamida hisoblanuvchi funksiya tushunchasini aniqlashga birinchi bo‘lib bir-biridan bexabar holda E.Post va A.Tyuring erishdilar. Post va Tyuring algoritmik jarayonlar ma’lum bir tuzilishga ega bo‘lgan «mashina» bajaradigan jarayonlar ekanligini ko‘rsatishdi. Ular ushbu «mashinalar» yordamida barcha hisoblanuvchi funksiyalar sinfi bilan barcha qismiy rekursiv funksiyalar sinfi bir xil ekanligini ko‘rsatdilar va, demak, Chyorch tezisining yana bitta fundamental tasdig‘i yuzaga keldi. 19. Markovning normal algoritmi tushunchasi. 1- t a ’ r i f. Bo‘sh bo‘lmagan chekli simvollar to‘plami alfavit, alfavitdagi simvollar esa harflar deb ataladi. 2- t a ’ r i f. A alfavitdagi harflarning har qanday chekli ketma-ketligi shu to‘plamdagi so‘z deb ataladi. Harflarning bo‘sh ketma-ketligi bo‘sh so‘z deb ataladi va u simvoli bilan belgilanadi. Agar B A bo‘lsa, u holda A alfavit B alfavitning kengayishi (kengaytirilgani) deb ataladi. Ravshanki, bu holda B alfavitdagi har bir so‘z o‘z navbatida A alfavitining ham so‘zi bo‘ladi. A alfavitdagi hamma so‘zlar to‘plamini D bilan belgilaymiz. D to‘plamning biror qism to‘plami C bo‘lsin, ya’ni C D . 3- t a ’ r i f. Aniqlanish sohasi C va qiymatlar sohasi D bo‘lgan effektiv hisoblanuvchi funksiya A alfavitdagi algoritm (algorifm) deb ataladi. 4- t a ’ r i f. Agar A alfavitdagi biror P so‘z U algoritmning aniqlanish sohasiga tegishli bo‘lsa, u holda U algoritm P so‘zga tatbiq etiladigan algoritm deb ataladi. 5- t a ’ r i f. Agar A B bo‘lsa, u holda B alfavitdagi har bir algoritm A alfavit ustidagi algoritm deb ataladi. A alfavitdagi normal algoritm tushunchasi bilan A alfavit ustidagi normal algoritm tushunchasi o‘rtasidagi farq juda ham muhimdir. A alfavitdagi har qanday normal algoritm faqat A alfavitning harflaridan foydalanadi. A alfavit ustidagi normal algoritm esa A alfavitga kirmagan boshqa qo‘shimcha harflardan ham foydalanishi mumkin. Shunday qilib, A alfavitdagi har qanday normal algoritm A ustidagi normal algoritm ham bo‘ladi. Ammo, A alfavitda shunday algoritmlar mavjudki, ular A ustida normal algoritm bo‘lishiga qaramasdan, A alfavitda normal algoritm bo‘la olmaydi. 20. Gilbertning 10- muammosi deb nom olgan quyidagi muammo ham bor edi: «Koeffitsiyentlari butun sonlardan iborat bo‘lgan har qanday algebraik tenglamaning butun sonli yechimi mavjudmi?». Gilbertning 10- muammosi bilan dunyoning ko‘p matematiklari deyarli 70 yil mobaynida shug‘ullanishdi va nihoyat, 1968 yilga kelib Sankt-Peterburglik yosh matematik Yu. V. Matiyasevich38 va sal keyinroq, aniqrog‘i, 1970 yilda rus matematigi G. V. Chudnovskiy39 bu muammoni hal qilishdi. Aniqlandiki, qo‘yilgan masalaning yechimini bera oladigan algoritm mavjud emas.
mashinasida realizasiya etish (amalga oshirish) mumkin. Bu gipoteza Tyuring tezisi deb ataladi. Uni isbotlash mumkin emas, chunki bu tezis qat’iy ta’riflanmagan algoritm tushunchasini qat’iy aniqlangan Tyuring mashinasi tushunchasi bilan bog‘laydi. Bu tezisni rad etish uchun Tyuring mashinasida realizasiyalanmaydigan (amalga oshirilmaydigan) algoritm mavjudligini ko‘rsatish kerak. Ammo hozirgacha aniqlangan hamma algoritmlarni Tyuring funksional sxemasi orqali realizasiya etish mumkin. Ekvivalent tushunchalar. Shuni ham ta’kidlab o‘tamizki, Markovning normal algoritm tushunchasi hamda Chyorch, Gyodel va Klini tomonidan kiritilgan rekursiv algoritm va rekursiv funksiya tushunchalari, mos ravishdam, Tyuring tomonidan kiritilgan algoritm tushunchasi va Tyuring funksional sxemasi bilan ekvivalentligi isbotlangan. Bu dalil o‘z navbatida Tyuring gipotezasining to‘g‘riligini yana bir marta tasdiqlaydi. Download 17.97 Kb. Do'stlaringiz bilan baham: 
|