Amaliy mashg‘ulotlarni bajarish buyicha uslubiy ko’rsatmalar. Amaliy mashg’ulot. Mavzu

TYURING MASHINASI: Amaliy MISOLLAR

1-misol. Vazifa lentada joylashgan berilgan sonning oxirgi raqamiga bitta qo'shadigan algoritmni qurishdir. Kirish ma'lumotlari - so'z - lentadagi ketma-ket hujayralarga 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 erda 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.
2-misol. Sizga ochiq va yopiq qavslar uchun bir qator belgilar beriladi. Bir juft qavsni, ya'ni bir qatorda joylashgan elementlarni - "()" olib tashlaydigan Turing qurilmasini qurish talab qilinadi. Masalan, boshlang'ich ma'lumotlar: ") (() (()", javob quyidagicha bo'lishi kerak: ").. ((". Yechish: q 1 da bo'lgan mexanizm, chiziqning eng chap elementini tahlil qiladi.
q 1 holati: agar “(” belgisi uchrasa, o‘ngga siljiting va q 2 holatiga o‘ting; agar “a 0” aniqlangan bo‘lsa, to‘xtating.
q 2 holat: “(” qavs juftlik mavjudligi uchun tahlil qilinadi, mos kelsa, “)” bo'lishi kerak. Agar buyum juft bo'lsa, vagonni chapga qaytaring va q 3 ga o'ting.
q 3 holati: avval “(” va keyin “)” belgisini o‘chiring va q 1 ga o‘ting.
ch.da. XII algoritmlarga qo'llaniladigan asosiy intuitiv aniq talablarni tushuntirdi. Bular algoritmlarning determinizmi, ommaviy xarakteri va qo'llanilishi ("maqsadliligi") uchun talablardir. Algoritmni qo'llash natijasi uni kim ishlatishiga umuman bog'liq emasligi muhimdir. Algoritmni bajaruvchi shaxs faqat ko'rsatmalarni qanday to'g'ri bajarish haqida qayg'urib, "mashina kabi" harakat qilishi kerak. Shunday qilib, tabiiyki, shunday fikr tug'iladi: haqiqatan ham algoritmni bajarishni mashinaga ishonib topshirish mumkinmi?
Yuqorida aytib o'tilgan algoritmlarning xususiyatlari nazarda tutadi Umumiy talablar algoritm bilan ishlaydigan mashinaga. Birinchidan, mashina butunlay deterministik bo'lishi va berilgan qoidalar to'plamiga muvofiq harakat qilishi kerak! Ikkinchidan, u turli xil "dastlabki ma'lumotlar" ni kiritishga imkon berishi kerak (ma'lum bir sinfdagi vazifalarga mos keladigan). Uchinchidan, mashinaning ishlashi uchun berilgan qoidalar tizimi va echilishi kerak bo'lgan muammolar sinfi mashinaning ishlash natijasini doimo "o'qish" mumkin bo'lishi uchun muvofiqlashtirilishi kerak.
Algoritmlarni bajarishga qodir bo'lgan mashinalarning turli "konstruksiyalari" taklif qilinishi mumkin. Eng illyustrativ sxema 1936 yilda ingliz matematigi Tyuring tomonidan taklif qilingan. Quyida ulardan birining tavsifi keltirilgan mumkin bo'lgan variantlar bunday mashinalarning ishlashi
Hujayralarga bo'lingan cheksiz bir o'lchovli lentani ko'rib chiqing. Biz tasmani faqat bitta yo'nalishda - o'ngda cheksiz deb hisoblaymiz, shunda eng chap hujayra mavjud.
Har bir katakda oxirgi alifbodan faqat bitta belgi bo'lishi mumkin. Biz belgini ataylab ajratib ko'rsatamiz va agar u ma'lum bir katakda yozilgan bo'lsa, unda bu katak "bo'sh" ekanligini aytamiz. Keyinchalik, biz har doim lentada bo'sh bo'lmagan belgilar soni cheklangan (lekin o'zboshimchalik bilan ko'p) bo'ladi, qolgan hujayralar esa bo'sh bo'ladi deb taxmin qilamiz.
Tasavvur qiling-a, maxsus qurilma - o'qish va yozish kallagi, har bir lenta katakchalarining ro'parasida joylashgan bo'lishi mumkin va tashqaridan berilgan buyruq bilan ushbu katakchada yozilgan belgini "o'chirish" va yangisini yozish. O'qish va yozish boshi buyruq bo'yicha bitta katakchani o'ngga yoki chapga siljitishi mumkin (agar u eng chap katakda bo'lmasa). Boshqarish moslamasidan o'qish va yozish boshiga buyruqlar yuboriladi, u o'z navbatida boshning qarshisida joylashgan lenta katakchasida belgi mavjudligi haqida boshdan signal oladi.
Boshqarish moslamasi cheklangan miqdordagi ichki holatlarga ega va diskret vaqt ichida ishlaydi. Boshqarish moslamasining kiritilishi - o'qish va yozish boshi tomonidan chiqarilgan belgilar, chiqish - boshning harakati uchun buyruqlar: bosh mos keladigan katakchaga qanday belgi yozishi va qayerga o'tishi kerak. Vaqt t momentida o'qish va yozish boshlari belgi yozilgan katakka qarama-qarshi (chapdan sanab) va boshqaruv moslamasi holatda bo'lsin. Boshqaruv moslamasi holat va kiritishga qarab belgi chiqaradi (shuning uchun bosh eski belgini o'chiradi va yangisini chop etadi), so'ngra P, L yoki C belgilaridan birini («o'ng»? «Chap») chiqaradi. , "to'xtash"), unga muvofiq bosh bir hujayrani o'ngga yoki chapga siljitadi yoki joyida qoladi. Shundan so'ng, boshqaruv moslamasi yangi holatga o'tadi (shuningdek, belgilar bilan noyob tarzda aniqlanadi).
Shunday qilib, vaqt momentida hujayraga belgi yoziladi, boshqaruv moslamasi holatda bo'ladi va o'qish va yozish boshi katakchaning qarshisida joylashgan bo'ladi (belgi P, L yoki C bo'lishiga qarab). . Shunday qilib, nazorat qilish moslamasi ikkita chiqish konvertori bo'lgan ketma-ket mashinadir: mashinaning kiritilishi - boshdan qabul qilingan belgi (kirish alifbosi); holatlar - alifbodan belgilar birinchi chiqish - alifbodan yozish uchun signal ikkinchi chiqish - boshni alifbodan siljitish uchun signal. Ushbu ketma-ket mashinaning ishlashi uchta jadval bilan aniqlanishi mumkin: avtomat jadvali va ikkita konvertor jadvali. Tyuring mashinasining ishlashini tavsiflashda ushbu jadvallarni bitta asosiy jadvalga birlashtirish odatiy holdir.
Turing mashinasi qanday ishlashini ko'rib chiqing.
Tyuring mashinasi hujayralarga bo'lingan cheksiz lenta va lenta bo'ylab harakatlanadigan karetka (o'quvchi-printer).
Shunday qilib, Tyuring mashinasi rasmiy ravishda ikkita alifbo to'plami bilan tavsiflanadi:
A = (a1, a2, a3, ..., an) - tashqi alifbo, dastlabki ma'lumotlarni yozish uchun ishlatiladi
Q = (q1, q2, q3,…, qm) - ichki alifbo, o'quvchi va chop etish moslamasining holatlar to'plamini tavsiflaydi.
Lentaning har bir katakchasi tashqi alifbodan A = (a0, a1, ..., an) belgisini o'z ichiga olishi mumkin (bizning holatda, A = (0, 1))
Tyuring mashinasining amaldagi harakatlari quyidagilardan iborat:
1) tashqi alifboning istalgan belgisini lenta katakchasiga yozing (ilgari bo'lgan belgining ustiga yoziladi)
2) qo'shni katakka o'tish
3) holatni ichki Q alifbosi belgisi bilan ko'rsatilganlardan biriga o'zgartirish
Turing mashinasi - bu stol bilan boshqariladigan mashina.
Jadvaldagi qatorlar tanlangan A alifbosining belgilariga, ustunlar esa avtomat Q = (q0, q1,…, qm) holatlariga mos keladi. Ishning boshida Tyuring mashinasi q1 holatidadir. q0 holati yakuniy holat bo'lib, unga kirgandan so'ng avtomat o'z ishini tugatadi.
Jadvalning qandaydir ai belgisiga va qj holatiga mos keladigan har bir katakda uch qismdan iborat buyruq mavjud
A alifbosidagi belgi
· Harakat yo'nalishi: ">" (o'ngga), "<» (влево) или «.» (на месте)
Mashinaning yangi holati

Yuqoridagi jadvalda A = (0, 1, _) alifbosi (3 ta belgidan iborat) va ichki alifbosi Q = (q1, q2, q3, q4, q0), q0 - vagonning to'xtab qolishiga sabab bo'lgan holat.
Keling, bir nechta vazifalarni hal qilish orqali ko'rib chiqaylik. Turing mashinasini veb-saytning YUKLASH bo'limida yuklab olishingiz mumkin.
Masala 1. A = (0, 1, _) bo‘lsin. Lentada katakchalar alifbodan quyidagi tartibda joylashgan belgilarni o'z ichiga oladi 0011011. Karet birinchi belgi ustida joylashgan. 0 ni 1 ga, 1 ni 0 ga almashtiradigan va karetani dastlabki holatiga qaytaradigan dastur yozish kerak.

Endi vagonning holatlarini aniqlaymiz. Men ularni "karetaning biror narsa qilishni istashlari" deb atayman.
q1) Vagon o‘ng tomonga ketishi kerak: agar u 0 ni ko‘rsa, uni 1 ga o‘zgartiradi va q1 holatda qoladi, 1 ni ko‘rsa, 0 ga o‘zgartiradi va q1 holatda qoladi, agar _ ni ko‘rsa, q1 holatda qoladi. orqaga ketadi 1 katak "boshqa narsani xohlaydi" , ya'ni q2 holatiga o'tadi. Keling, o'z fikrimizni ijrochi jadvaliga yozamiz. Sintaksis uchun dastur yordamiga qarang)

q2) Endi biz q2 “karetaning xohishi”ni tasvirlaymiz. Biz asl pozitsiyamizga qaytishimiz kerak. Buning uchun: agar biz 1 ni ko'rsak, biz uni qoldiramiz va q2 holatida qolamiz (belgilar qatorining oxiriga etish istagi bilan); agar biz 0 ni ko'rsak, biz uni qoldiramiz va q2 holatida chapga o'tishni davom ettiramiz; ko'ramiz _ - 1 katakcha o'ngga siljiydi. Muammo bayonotida talab qilinadigan joyda siz shu yerdasiz. q0 holatiga o'tamiz.

Dasturning ishini videoda tomosha qilishingiz mumkin:
Masala 2. Berilgan: 0 va 1 ning yakuniy ketma-ketligi (001101011101). Ularni ushbu ketma-ketlikdan keyin bo'sh katak orqali yozish kerak va bu ketma-ketlikda ularni 0 bilan almashtirish kerak. Masalan:
001101011101 dan biz 000000000000 1111111 ni olamiz.
Ko'rib turganingizdek, bu ketma-ketlikdan keyin ettita birlik yoziladi va ularning o'rnida nol bor.
Keling, mulohaza yuritishga o'taylik. Tashish uchun qanday holatlar va qancha kerakligini aniqlang.
q1) arra 1 - uni nolga o'rnating va boshqa holatga o'ting q2 (vagon bir o'tishda hammasini nolga o'zgartirmasligi uchun yangi holat kiritilgan)
q2) hech narsani o'zgartirmang, ketma-ketlikning oxiriga o'ting
q3) karetka bo‘sh katakchani ko‘rishi bilan o‘ngga bir qadam tashlab, bittasini chizadi, agar ko‘rsa, oxiridagi belgiga imzo qo‘yishga o‘tadi. Birlikni chizganimizdan so'ng, biz q4 holatiga o'tamiz
q4) hech narsani o‘zgartirmagan holda yozma birliklardan o‘tamiz. Ketma-ketlikni birlikdan ajratib turuvchi bo'sh katakka etib borishimiz bilan biz yangi q5 holatidan o'tamiz.
q5) bu holatda hech narsani o‘zgartirmagan holda ketma-ketlikning boshiga o‘tamiz. Biz bo'sh hujayraga etib boramiz, orqaga o'girilib, q1 holatiga boramiz
Karetaning q1 holatida shu ketma-ketlikning oxirigacha o'tib, bo'sh katakka duch kelganida q0 holatini qabul qiladi.
Biz quyidagi dasturni olamiz:

Quyidagi videoda Tyuring mashinasining ishini tomosha qilishingiz mumkin.