2-amaliy mashg’ulot: tyuring mashinasi

QURILMA NIMADAN IBORAT

Har bir bunday mashina ikkita komponentdan iborat:

1. 
   Cheksiz tasma. U har ikki yo‘nalishda ham cheksiz bo‘lib, katakchalarga bo‘linadi.
   
2. 
   Avtomatik mashina - boshqariladigan dastur, ma’lumotlarni o‘qish va yozish uchun bosh-skaner. Bu har qanday vaqtda ko‘plab shtatlardan birida bo‘lishi mumkin.
   

Har bir mashina ikkita chekli ma’lumotlar qatorini bog’laydi: kiruvchi belgilar alifbosi A = (a0, a1, ..., am) va holatlar alifbosi Q = (q0, q1, ..., qp). q0 holati passiv deb ataladi. Taxminlarga ko‘ra, qurilma urilganda o‘z ishini tugatadi. q1 holati boshlang’ich holat deb ataladi - mashina o‘z hisob-kitoblarini uning boshida bo‘lgan holda boshlaydi. Kirish so‘zi lentada joylashgan bo‘lib, har bir pozitsiyada bir qatorda bitta harf. Uning ikkala tomonida faqat bo‘sh katakchalar joylashgan.

MEXANIZM QANDAY ISHLAYDI

Turing mashinasi hisoblash qurilmalaridan tubdan farq qiladi - uning xotira qurilmasi cheksiz lentaga ega, raqamli qurilmalarda esa bunday qurilma ma’lum uzunlikdagi chiziqqa ega. Har bir vazifa sinfi faqat bitta qurilgan Turing mashinasi tomonidan hal qilinadi. Boshqa turdagi muammolar yangi algoritm yozishni o‘z ichiga oladi.
Tekshirish moslamasi bitta holatda bo‘lib, kamar bo‘ylab istalgan yo‘nalishda harakatlanishi mumkin. U chekli alifboning belgilarini katakchalarga yozadi va o‘qiydi. Harakat paytida bo‘sh element tanlanadi, u kirish ma’lumotlarini o‘z ichiga olmaydigan pozitsiyalarni to‘ldiradi. Turing mashinasi algoritmi boshqaruv qurilmasi uchun o‘tish qoidalarini belgilaydi. Ular o‘qish-yozish boshiga quyidagi parametrlarni o‘rnatadilar: katakka yangi belgi yozish, yangi holatga o‘tish, lenta bo‘ylab chapga yoki o‘ngga siljitish.

MEXANIZM XUSUSIYATLARI

Tyuring mashinasi, boshqa hisoblash tizimlari kabi, o‘ziga xos xususiyatlarga ega va ular algoritmlarning xususiyatlariga o‘xshaydi:

1. 
   Diskretlik. Raqamli mashina keyingi bosqichga o‘tadi n + 1 oldingisi tugagandan keyingina. Har bir tugallangan bosqich n + 1 bo‘lishini belgilaydi.
   
2. 
   Tushunuvchanlik. Qurilma bir xil katakcha uchun faqat bitta amalni bajaradi. U alifbodagi belgini yozadi va bitta harakatni amalga oshiradi: chap yoki o‘ng.
   
3. 
   Determinizm. Mexanizmdagi har bir pozitsiya ma’lum bir sxemani bajarishning yagona variantiga mos keladi va har bir bosqichda harakatlar va ularni amalga oshirish ketma-ketligi aniq.
   
4. 
   Samaradorlik. Har bir bosqich uchun aniq natija Turing mashinasi tomonidan aniqlanadi. Dastur algoritmni bajaradi va cheklangan miqdordagi qadamlarda q0 holatiga o‘tadi.
   
5. 
   Ommaviy xarakter. Har bir qurilma to‘g’ri alifbo so‘zlari bo‘yicha aniqlanadi.