•Tyuring mashinasi tushunchasi. Agar qandaydir ommaviy muammoni yechish algoritmi ma’lum bo‘lsa, u holda uni realizatsiya qilish uchun shu algoritmda aniq yoritilgan ko'rsatmalarni ijro qilish zarur. Algoritmni realizatsiya 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 operatsiyalarga ajratish natijasida hosil bo'lgan. Tyuring ta’kidlaydiki, istalgan mumkin bo‘lgan hisoblashni o‘tkazish uchun uning elementar operatsiyalarini qaytarish yetarli. Tyuring ayrim turdagi nazariy hisoblash mashinasini izohlab berdi. Bu mashina muayyan mexanik quriima emas, balki «xayoliy» matematik mashinadir. •Tyuring mashinasida o‘nlik sistemada n dan n + 1 ga o‘tish algoritmini realizatsiya qilish. 0 ‘nlik sanoq sistemasida n sonning yozuvi berilgan bo‘lsin va n +1 sonning o ‘nlik sistemasidagi yozuvini ko'rsatish, ya’ni / (n) = n +1 funksiyani hisoblash talab etilsin. Ravshanki, mashinaning tashqi alfaviti 0,1,2,3,4,5,6,7,8,9 raqamlardan va bo‘sh katakcha a 0dan iborat bo‘lishi kerak. Lentaga o ‘nlik sistemada n sonini yozamiz. Bu yerda qatorasiga bo‘sh joysiz har bir katakchaga bitta raqam yoziladi. Qo^yilgan masalani yechish uchun ishning birinchi taktida mashina n sonning oxirgi raqamini o‘chirib, uni bir birlik katta songa almashtirib va agar oxirgi raqam 9 sonidan kichik bo‘lsa, u holda to‘xtash holatiga o‘tishi kerak. Agar n sonning oxirgi raqami 9 bo‘lsa, u holda mashina 9 raqamni o‘chirib, bo‘sh qolgan katakchaga 0 raqamni yozib, o‘sha holatda qolgan holda chapga yuqoriroq razryadli qo‘shnisiga surilishi kerak. Bu yerda ishning ikkinchi taktida mashina yuqoriroq razryadli raqamga 1 sonini qo‘shishi kerak. Tabiiyki, chapga surilish paytida yuqoriroq razryadli raqam bo'lmasa, u holda mashinaning boshqaruvchi kallagi bo‘sh katakchaga chiqishi mumkin. Bu holatda bo‘sh katakchaga mashina 1 raqamini yozadi. Aytilganlardan shu narsa kelib chiqadiki, f (n) = n + 1 funksiyani hisoblash algoritmini realizatsiya qilish paytida mashina bor yo‘g‘i ikkita holatlarda bo‘ladi. Ular ••Evklid algoritmi berilgan ikkita natural son uchun ulaming eng katta umumiy bo‘luvchisini topish kabi masalalami yechishda qo‘llaniladi