Muhammad Al-Xoramiy nomidagi Toshkent Axborot Texnalogiyalari Unversisteti

Algoritmlar nazariyasining asosiy gipotezasi
Tyuring tezisi. Tyuring, Chyorch, Gyodel, Klini va Markov olgan natijalarning ekvivalentligi.
Tyuring tezisi. Tyuring mashinasi algoritm tushunchasini aniqlashning bitta yo‘lini ko‘rsatadi. Shu tufayli bir necha savollar paydo bo‘ladi:
- Tyuring mashinasi tushunchasi qancha umumiylik xususiyatiga ega?
- algoritmlami Tyuring mashinasi vositasi bilan berish usulini universal usul deb bo‘ladimi?
- hamma algoritmlami shu usul bilan berish mumkinmi?
Bu savollarga hozirgi vaqtda mavjud bo‘lgan algoritmlar nazariyasi
quyidagi gipoteza bilan javob beradi: har qanday algoritmni Tyuring
funksional sxemasi orqali berish va mos Tyuring mashinasida realizatsiya
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 realizatsiyalan
maydigan (amalga oshirilmaydigan) algoritm mavjudligini ko‘rsatish
kerak. Ammo hozirgacha aniqlangan hamma algoritmlami Tyuring
funksional sxemasi orqali realizatsiya 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 ravishda, Tyuring tomonidan kiritilgan algoritm
tushunchasi va Tyuring funksional sxemasi bilan ekvivalentligi is
botlangan. Bu dalil o‘z navbatida Tyuring gipotezasining to‘g‘riligini yana bir marta tasdiqlaydi.


Algoritmik yechilmovchi muammolar.


Matem atik mantiqda keltirib chiqaruvchanlikni tanish
muammosi. Matematika tarixida biror masalani yechish, odatda uning
yechilish algoritmini topish deb hisoblanardi. Deyarli XX asr
boshlarigacha hamma matematik masalalar algoritmik rekursiv masalalar
deb qaralgan va ulami yechuvchi algoritmlar izlangan. Masalan, haqiqiy
Koeffitsiyentli n-darajali ko‘phadning ildizlarini uning koeffitsiyentlariyordamida radikallarda ifoda etish algoritmini izlash bir necha asrlar davom etdi. Masalan, uchinchi va to‘rtinchi darajali tenglamalar uchun bu algoritmni XVI asrda italyan matematiklari Kardano1 va Ferrari yaratdilar. Uzoq yillardan keyin Abel3 n > 5 bo‘lganda bunday algoritm mavjud emasligini ko‘rsatdi. Ikkinchi misol sifatida Gilbertning Diofant tenglamalari haqidagi 10- muammosi deb ataluvchi muammoni ko‘rsatish mumkin. Bu muammo Gilbert tomonidan 1900-yilda Parijda e’lon qilingan edi
Faqat algoritmning intuitiv tushunchasidan Tyuring mashinasining aniq tushunchasiga o‘tish berilgan ommaviy muammoning algoritmik yechiluvchanlik masalasiga aniqlik kiritdi. Bu masalani quyidagicha ifodalash mumkin: berilgan ommaviy muammoni yechadigan Tyuring mashinasi mavjudmi yoki bunday mashina mavjud emasmi?
Bu savolga algoritmlar nazariyasi ayrim hollarda salbiy javob beradi.
Shu turdagi natijalami birinchilar qatorida 1936-yilda amerikalik matematik A.Chyorch oldi. U predikatlar mantiqidagi yechilish muammosi umumiy holda algoritmik yechimga ega emasligini ko‘rsatdi. O‘sha yilning o‘zida u matematik mantiqdagi keltirib chiqaruvchanlikni tanish muammosi ham algoritmik yechilmasligini isbot qildi. Keyingi masalani batafsilroq ko‘rib o ‘taylik.
Matematikada aksiomatik metodning mazmuni quyidagidan iborat:
berilgan nazariyaning hamma mulohazalari (teoremalari) shu nazariyada isbotsiz qabul qilingan mulohazaiardan (aksiomalardan) formal mantiqiy keltirib chiqarish vositasi bilan olinadi.
Matematik mantiqda formulalarning maxsus tili ifodalanadi. U orqali matematik nazariyaning istalgan mulohazasi butunlay aniqlangan formula ko‘rinishida yoziladi. A asosdan (shartdan) В natijani mantiqiy keltirib chiqarish jarayonini dastlabki formulalarni formal almashtirishlar jarayoni sifatida ifodalash mumkin. Bunga mantiqiy hisobdan foydalanish yo‘li bilan erishish mumkin.
Tanlangan mantiqiy hisobda В mulohazani A asosdan mantiqiy
keltirib chiqarish masalasi A formuladan В formulaga olib keluvchi
deduktiv zanjirning mavjudligi masalasidir. Shu tufayli keltirib
chiqaruvchanlikni tanish muammosi paydo bo‘ladi: mantiqiy hisobdagi
istalgan ikkita A va В formula uchun A dan В ga olib keluvchi deduktiv
zanjir mavjudmi yoki yo‘qmi? Bu muammoning yechimi sifatida har
qanday A va В uchun javob beradigan algoritm mavjudligi ma’nosida
tushuniladi. Chyorch olgan natija quyidagicha izohlanadi.