Mirzo Ulugʻbek nomidagi Oʻzbekiston Milliy universiteti Jizzax filiali “Amaliy matematika” fakulteti

Tyuring mashinasining ishlashi.
Barcha komandalar majmuasi Tyuring mashinasining dasturini tashkil qiladi. Dastur ikki oʻlchovli jadval shaklida boʻlib, u Tyuring funksional sxemasi deb ataladi. Bunday sxema 1-jadvalda misol sifatida berilgan.Tyuring mashinasining ishi butunlay 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-jadval.Tyuring jadvali

1- javalda berilgan funksional sxemaga mos keluvchi Tyuring mashinasining ishini misollarda koʻrib oʻtaylik.

1. 
   m is о 1. 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
_{       } uchinchi konfiguratsiya,
_{ 
         } toʻrtinchi konfiguratsiya,

_{         } beshinchi konfiguratsiya.
_{ }
Beshinchi konfiguratsiyada mashina _{ } holatda (toʻxtash holatida)
turganligi uchun _{ } soʻz hisoblashning natijasi boʻladi