O’zbekoston Respublikasi Oliy va O’rta maxsus ta’lim vazirligi Buxoro Davlat Universiteti Mustaqil ish Mavzu: Tyuring mashinalari. Tyuring mashinasida algoritmni realizatsiya qilish. Algoritmlar nazariyasining asosiy gipotezasi

Evklid algoritmi. Evklid algoritmi berilgan ikkita natural son uchun ulaming eng katta umumiy bo‘luvchisini topish kabi masalalami yechishda qo‘llaniladi. M a’lumki, Evklid algoritmi quyidagi kamayuvchi sonlar ketmaketligini tuzishga keltiriladi: birinchisi berilgan ikki sonning eng kattasi bo‘ladi, ikkinchisi - kichigi, uchinchisi - birinchi sonni ikinchisiga bo'lishdan hosil bo‘lgan qoldiq, to‘rtinchisi — ikkinchi sonni uchinchisiga bo‘lishdan hosil bo‘lgan qoldiq va hokazo, bu jarayon qoldiqsiz bo‘linguncha davom ettiriladi. Oxirgi bo‘lishdagi bo‘luvchi masala yechimining natijasi bo‘ladi. Evklid algoritmini Tyuring mashinasining dasturi sifatida ifodalash talab etilgan bo‘lsin. Bu dastur sonlami taqqoslash va ayirish sikllarining navbatma-navbat (navbatlashib) kelishini ta’minlashi kerak. To‘rtta harfdan iborat < a 0,\,CX, /3 > tashqi alfavitdan foydalanamiz. Bu yerda a 0 - bo‘sh katakcha simvoli, | - tayoqcha, a va j8 - tayoqcha rolini vaqtinchalik o‘ynaydigan harflar.
Birinchi navbatda mash ina lentada yozilgan sonlarni taqqoslashi kerak. Shu maqsadga erishish uchun mashina birinchi sonni ifodalovchi tayoqchalarni a harfi bilan va ikkinchi sonni ifodalovchi sonlarni f3 harfi bilan almashtirishi kerak. Mashina ishining birinchi to'rt taktiga mos keluvchi uning konfiguratsiyasi quyidagicha bo'ladi.
Shu bilan dastlabki sonlarni taqqoslash sikli tamom bo'lib, ayirish sikli boshlanadi. Bu sikl davomida kichik son lentadan butunlayiga o'chiriladi, f3 harfi bilan belgilangan ikkinchi son tayoqchalar bilan almashinadi va, demak, katta 6 soni ikkita 4 va 2 sonlariga bo'linadi. Bu operatsiyalarga bir qator konfiguratsiyalar to'g'ri keladi. Shulardan ayrimlarini yozamiz.

Algoritmlar nazariyasining asosiy gipotezasi
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 realizatsiyalanmaydigan (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 isbotlangan. Bu dalil o‘z navbatida Tyuring gipotezasining to‘g‘riligini yana bir marta tasdiqlaydi