Tyuring mashinasining ishlashi. Barcha komandalar majmuasi Tyuring mashinasining dasturini tashkil qiladi. Dastur ikki oichovli jadval shaklida bo‘lib, u Tyuring funksional sxemasi deb ataladi. Bunday sxema 1- jadvalda misol sifatida berilgan. Tyuring mashinasining ishi butunlayiga uning dasturi bilan aniqlanishi ravshan. Agar ikkita Tyuring mashinasining funksional sxemalari bir xil bo‘lsa, u holda ular bir-biridan farq qilmaydi. Har xil Tyuring mashinalari har xil dasturga ega bo‘ladi. Bundan keyin Tyuring mashinasining har xil konfiguratsiyalarini (ko‘rinishlarini) soddaroq ifodalash uchun lenta va uning katakchalarini ifodalamasdan axborotni faqat so‘z shaklida yozamiz:
Boshqaruvchi kallak va mashina holatini ifodalash sifatida mashina holatini yozamiz.
1- jadvalda berilgan funksional sxemaga mos keluvchi Tyuring mashinasining ishini misollarda ko'rib o‘taylik.
1- misоl. Dastlabki konfiguratsiya quyidagicha berilgan bo‘lsin:
Boshqaruvchi kallak harfini ko‘rib turganligi va mashina holatda bo'lganligi uchun mashina komandani ishlab chiqadi va natijada ikkinchi konfiguratsiyani hosil qilamiz.
Ravshanki, navbatdagi konfiguratsiyalar quyidagi ko‘rinishlarda bo‘ladi:
uchinchi konfiguratsiya,
to‘rtinchi konfiguratsiya,
beshinchi konfiguratsiya,
Beshinchi konfiguratsiyada mashina holatda (to‘xtash holatida) turganligi uchun so‘z hisoblashning natijasi bo‘ladi.
2-misol. Boshlang'ich konfiguratsiya quyidagicha bo‘lsin:
1-jadvaldagi funksional sxemadan foydalanib, quyidagi konfiguratsiyalarga kelamiz:
ikkinchi konfiguratsiya,
uchinchi konfiguratsiya,
to’rtinchi konfiguratsiya,
beshinchi konfiguratsiya,
oltinchi konfiguratsiya.
Ikkinchi va oltinchi konfiguratsiyalardan ko‘rinib turibdiki, mashinaning ish jarayoni takrorlandi va, demak, natija bo‘lmaydi.
|
