Algoritm tushunchasi Tyuring mashinalari

Reja:
Kirish

1. 
   Algoritm tushunchasi
   
2. 
   Tyuring mashinalari
   
3. 
   Tyuring mashinasida algoritmni realizatsiya qilish
   
4. 
   Tyuring nazariyasining asosiy gipotezasi
   

Xulosa
Foydalanilgan adabiyotlar

Kirish
Matemetik mantiqiyot ( shuningday-oq, simvollıq mantiqiyot deb te nomlanadi )- matematik usullar bilan rivojlandırılıp etilayotgan mantiqiyot.” Marematikalıq mantiqiyot” fani bárshe fanlarding asli bo'lishiga qat'iy nazar, uni o'zlar oldiga fundamental fan sifatida chuqurroq o'rganish XIX asrda noevklid geometriyaning paydo bo'lishidan boshlangan.

“Matematik mantiqiyot ” fani mantiqiyot usullarinian keng foydalanilib kelinbekte. Masalan, matematik tahlil -fanida limitke ega bo'lmagan izbe -izliklerdiń, tekis uzliksiz bo'lmagan funkciyalardıń izohin berishda predikatlar olgebrası usullarinian foydalanilib, yuqorida keltiritgan tushunchalarding aniq izohin beriladi.
Matematikaliq mantiqiyot faniniini tamalǵI maqsadinae matematikaning eng ahmiyetli tusiniklerin dalillashlik, teorema, keltirib shigáriw tusinikleri, shakll aksiomatik nazariya tamalinda oqiwshillarga etkazib berish kirei. Bundan tisqari matematikaliq mantiqiyot fani oqiwshilardi ravon o'ylashga o'rgatadi.
Fannin tamalǵI voziypasi talabalarga bilim berish jo'rligida ularding abstract fikrle qobiliyatini kusheytiriwge yo'naltirilgan
Bu kurs jumisinda biz Tyuring mashinalari, onin qaytip ishlashi, algoritmlar, Tyuring mashinasinda algoritmlarni realizasiya qiliwdi, natural sonlar qo'shlarish algoritmi, Evklid algoritmi, algoritmlar nazariyasinda tamalǵI gipotezalarga haqqinda toliq maǵliwmat keltirdik.

Matematikaning asosiy tushunchalaridan biri algoritm (olgorifm) tushunchasi dir. «Algoritm» lafzi IX-asrda ijodiy etgan ulug' matematik vatandoshimiz Abu Abdullo Muhammad ibn Muso ol -Xorazmiy isminingń lotincha Olgorithmi tarzida buzib yozilishinan kelib chiqqan. Har biri «awa » yoki «yaq» degan javob taqozo etuvchi ayrim sanoqli -cheksiz matematik yoki mantiqlik muammolar sinfin ko'raylik. Chekli son qadamda bu sinfdagi har qanday so'rovga biz javob bera oladigan jarayonlik (prosedura) bormi? Agar o'shanaqa prosedura mavjud bo'lsa, u holda u berilgan so'rovlar sinfi uchun yechuvchi prosedura yoki yechuvchi algoritm (olgorifm) deb aytiladi. Yechuvchi prosedurani izlash muammosinia bu sinf uchun yechilish muammosi deb aytiladi. Shakll tizimlar uchun yechilish muammosini kun tartibiga birinchi qo'ygan olimlardan Shryoder (1895), Lyovengeym (1915) va Gilbertlarni (1918) ko'rsatish mumkin. Masalan, quyidagilar yechuvchi algoritmlarga misol bo'la oladi :

1. Sonlar ustida arifmetik amallardi bajarish qoidalari.
2. Kvadrat chiqarish qoidasi.
3. Eng katta umumiy bo'luvchin topish qoidasi (Yevklid algoritmi ).
4. Kvadrat tenglamading yechimini topish qoidasi.
5. n -tartibli ko'phadlarding hosilan topish qoidasi.
6. Rostional funksiyani integralroq qoidasi.
Yuqorida keltiritgan har bitta misolda mushtarak tipli (turdagi ) muammolar sinfi bilan yumush ko'rishlikga to'g'ri keladi. Mushtarak turdagi muammolar sinfi ommaviy muammo deb aytiladi. Bunday tabaqalarning masalalari bitta biridan xolos ifodasi dagi parametrlar bilan farq etadi. Masalan ax²  bx  +c = 0 Kvadrat tenglamading yechimini topish masalasinde a, b va c parametrlar qatnashadi. Ularning baholarini o'zgartirish yo'li bilan bitta sinfga tegishli turli xil muammolarga kelamiz.
Aytilganlarni hisobga olib algoritmding quyidagi intuitiv ta'rifini berish mumkin.
1-ta'rif. Berilgan ommaviy muammo dagi borlik masalalarni umumiy mushtarak shaklda, aniq ma'lumki bo'lgan usul bilan yechish jarayonine algoritm deb aytamiz. Bunday ta'rifni qat'iy deb hisoblash mumkin emas. Darhaqiqat, unda aniq mundarijasi noma'lum so'zlar uchraydi. Xususan, bu «usul» lafziga da tegishli. O'sha sababli da algoritmding bu qat'iy bo'lmagan ta'rifiga intuitiv ta'rif deb aytiladi
Endi algoritmding xarakterli xususiyatlarin ko'rib o'taylik.
1. Algoritmding diskretligi. Algoritm -miqdorlarni o'shanaqa ketma-ket qurish jarayoniki, boshlang'ich holatda miqdorlarding dastlabki chekli tizimsi berilgan bo'lib, har bitta navbatdagi momentte miqdorlar tizimsi ma'lumki aniqlangan qonun (dastur ) asosida avvalgi holat dagi miqdorlar tizimidan paydo qilildi.
2. Algoritmding daterminasiyalanuvchanligi (aniqlanguvchanligi). Boshlang'ich holatdan farq etuvchi boshqa holatda aniqlangan miqdorlar tizimsi ilgarigi hollarda unum etilgan miqdorlar tizimsi qirg'oqlari bitta baholi aniqlangadi.
3. Algoritm qadamlarining unsurarligi. Ilgarigi miqdorlar tizimidan keyingisini hosil qilish qonuni oddiy qadamlardan iborat bo'lishi zurur.
4. Algoritmding ommaviyligi. Boshlang'ich miqdorlar tizimini ayrim potensial cheksiz to'plamtan tanlov mumkin.
5. Algoritmding xotimalikligi. Miqdorlarni topish jarayoni chekli bo'lishi va xotima (masalaniń yechimini ) berishi zurur.
Algoritm tusinigin aniqlawdaǵI muammolar
Matematika tarixinda mushtarak turdegi so'rovlar kompleksininge “ha” yoki “yaq” va mushtarak turdegi so'rovlar klasi “hisoblanuvchi ' yoki “hisoblanuvchi emas” degan javoblar berilishi mumkin bo'lgan algoritmlarni izlash uzoq davom qildi. Ayrim vaqtlarda bu izlanishlar xotimasiz tugadi. Bu hollarda, tabiiyki, algoritmding mavjudligiga guman bilan qaraladi.
1- misol. Fermaning «buyuk teoremasi» deb ataluvchi tasdiqni qaraymiz. 1637-yillar atrofida Ferma quyidagi teoremaning tasdiqi o'zida borligin e'lon qildi :
« x n + y" = z" tenglama n > 2 Bo'lganda o'ng butun son baholi x, y, z, n qarorga ega emas». Bu teorema faqatgina 2000-yilda Angliya olimi Endryu Uals tomonidan tasdiqlandi. ■
2- misol. 1900-yilda Parijda o'tkazilgan ikkinchi xalqaro matematiklar kongressida umon matematigi David Gilbert yechilishi zarurli boMgan 23 matematik muammolar ro'yxatini o'qib berdi. Bu ro'yxatda Cilbertning 10 - muammosi deb atalgan quyidagi muammo ham mavjud edi : «Koefficiyentleri butun sonlardan iborat bo'lgan har qanday olgebraik tenglamading butun sonli yechimi bormi? ». Gilbert butun sonli koefficiyentlerden iborat bo'lgan har qanday olgebraik tenglama butun sonli qarorga egami degan muammoni hal qildilik (hal qildilik ) algoritm yaratuv kerakligini ko'rsatdi.
Matematikada butun sonli koefficiyentlerge ega boMgaalgebraik tenglamalar Diofant tenglamalari1 deyiladi. Masalan

Ko'rinishdagi tenglamalar diofant tenglamalari boMadi, ulardan birinchisi uchlar o'zgaruvchili va ikkinchisi bitta o 'zgaruvchili tenglama dir. Umumiy holda tenglama xohlagan sondagi o'zgaruvchilarga bogMiq boMishi hamda bunday tenglamalar butun sonli yechimlarga ega boMishi ham, ega bo'llarmasligi ham mumkin. Masalan , x² +y ² - 2xz = 0 cheksiz ko’p butun sonli yechimlarga ega, 10x⁵ +7x²  +5 = 0 tenlama bo’lsa butun sonli yechimlarga ega emas.
Bitta o'zgaruvchili diofant tenglamasining hamma butun sonli yechimlarini topish algoritmi anchadan buyon bor. Aniqlanganki, agar