|
Tyuring mashinalari Reja Tyuring mashinasi tushunchasi
|
| bet | 1/4 | | Sana | 21.12.2023 | | Hajmi | 1.3 Mb. | | #126204 |
Bog'liq Rajabov Shohjahon Diskret tuzulmalari (3)
Tyuring mashinalari
Reja
Tyuring mashinasi tushunchasi.
Tyuring mashinasining ishlashi.
Tyuring mashinasida algoritmni realizatsiya qilish
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. Berilgan ko‘rsatmani bajaruvchi hisoblovchi odamdan yoki mavjud raqamli hisoblash mashinasidan Tyuring mashinasi ikki jihati bilan farq qiladi.
Birinchidan, «Tyuring mashinasi» xato qila oimaydi, 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 l ga teng bo'lgan so'zdir.
Bu alfavitda so‘z ko'rinishida mashinaga beriladigan axborot kodlashtiriladi. Mashina so‘z ko'rinishida berilgan axborotni 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). O’,Ch,J surilish simvollaridir (mos ravishda, o ‘ngga, chapga va joyida).
|
| |
