2-amaliy mashg’ulot: tyuring mashinasi

AVTOMAT UCHUN ALGORITM

Turing qurilmasining ish paytida tashish dasturi har bir bosqichda quyidagi harakatlar ketma-ketligini bajaradigan dastur tomonidan boshqariladi:

1. 
   Tashqi alifbo belgisini pozitsiyaga, shu jumladan bo‘shga yozish, undagi elementni, shu jumladan bo‘shni almashtirish.
   
2. 
   Bir katakchani chapga yoki o‘ngga siljiting.
   
3. 
   Sizning ichki holatingizni o‘zgartirish.
   

Shunday qilib, har bir juft belgilar yoki pozitsiyalar uchun dasturlarni yozishda uchta parametrni aniq tasvirlash kerak: ai - tanlangan A alifbosidan element, vagonning siljish yo‘nalishi ("←" chapga, "→" o‘ng, "nuqta" - harakat yo‘q) va qk - qurilmaning yangi holati Masalan, 1 "←" q 2 buyrug’i "belgini 1 ga almashtiring, vagon boshini chapga bir katak qadamiga o‘tkazing va bajaring. q 2" holatiga o‘tish.

TYURING MASHINASI: MISOLLAR

1-misol. Vazifa lentada joylashgan berilgan sonning oxirgi raqamiga bitta qo‘shadigan algoritmni qurishdir. Kirish ma’lumotlari - so‘z - lentadagi ketma-ket katakchalarga yozilgan butun o‘nli raqamlar. Dastlabki vaqtda qurilma eng o‘ngdagi belgi - raqam raqamining qarshisida joylashgan.
Yechim. Agar oxirgi raqam 9 bo‘lsa, u 0 ga almashtirilishi kerak va keyin oldingi belgiga qo‘shilishi kerak. Bu holda dastur uchun bu qurilma Turingni quyidagicha yozish mumkin:
Bu yerda q 1 - raqam o‘zgarishi holati, q 0 - to‘xtash. Agar q 1 da avtomat 0..8 qatordan elementni tuzatsa, u holda uni mos ravishda 1..9 dan biri bilan almashtiradi va keyin q 0 holatiga oʻtadi, yaʼni qurilma toʻxtaydi. Agar vagon 9 raqamini o‘rnatsa, keyin uni 0 bilan almashtirsa, keyin q 1 holatida to‘xtab, chapga siljiydi. Bu harakat qurilma 9 dan kichik raqamni tuzatmaguncha davom etadi. Agar barcha belgilar 9 ga teng bo‘lsa, ular nolga almashtiriladi, yetakchi element o‘rniga 0 yoziladi, vagon chapga siljiydi va bo‘sh katakka 1 ni yozadi. . Keyingi qadam q 0 - to‘xtash holatiga o‘tish bo‘ladi.