|
3-Ma’ruza. Mavzu: T’yuring mashinasi va tezisi Reja
|
| bet | 1/4 | | Sana | 28.11.2023 | | Hajmi | 409,53 Kb. | | #106838 |
Bog'liq 3-Ma\'ruza. T’yuring mashinasi va tezisi
3-Ma’ruza.
Mavzu: T’yuring mashinasi va tezisi
Reja:
1. Tyuring mashinasi tushunchasi.
2. Tyuring mashinasining ishlashi.
3. Tyuring mashinasida algoritmni realizasiya qilish.
Tayanch iboralar: Ommaviy muammo. Yechish algoritmi. Tyuring mashinasi. Tashqi alfavit. Ichki alfavit. Lenta (mashinaning tashqi xotirasi). Boshqaruvchi kallak. Boshlang‘ich axborot. Mashina dasturi. Tyuring funksional sxemasi. Algoritm. Realizasiya qilish. O‘nlik sistemada n dan n+1 ga o‘tish. Algoritm. Natural sonlarni qo‘shish. Evklid algoritmi.
Tyuring mashinalari
Tyuring mashinasi tushunchasi. Agar qandaydir ommaviy muammoni yechish algoritmi 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.
Birinchidan, «Tyuring mashinasi» xato qila olmaydi, ya’ni u og‘ishmay (chetga chiqmasdan) ko‘rsatilgan qoidani be kami-ko‘st bajaradi.
Ikkinchidan, «Tyuring mashinasi» potensial cheksiz xotira bilan ta’minlangan. Endi Tyuring mashinasi tushunchasi bilan batafsil tanishamiz. Tyuring mashinasini quyidagilar to‘liq aniqlaydi.
Tashqi alfavit, ya’ni chekli simvollar to‘plami. A to‘plam elementlarining chekli ketma-ketligi A to‘plamdagi so‘z deyiladi. So‘zni tashkil etuvchi simvollar soni shu so‘zning uzunligi deyiladi.
Masalan, A alfavitning har bir elementi uzunligi 1ga teng bo‘lgan so‘zdir.
Bu alfavitda so‘z ko‘rinishida mashinaga beriladigan axborot (informatsiya) kodlashtiriladi. Mashina so‘z ko‘rinishida berilgan informatsiyani qayta ishlab, yangi so‘z hosil qiladi.
Ichki alfavit, ya’ni simvollar.
mashinaning chekli son holatlarini ifodalaydi. Istalgan mashinaning holatlari soni tayinlangan bo‘ladi. Ikki holatda maxsus vazifa bajariladi:
mashinaning boshlang‘ich (dastlabki) holati,
natijaviy (oxirgi) holati (to‘xtash holati).
J ,Ch,O' surilish simvollaridir (mos ravishda, o‘ngga, chapga va joyida).
|
| |
