2-amaliy mashg’ulot: tyuring mashinasi

Turing mashinasini ishlash jarayoni

Tyuring mashinasi katakchalarga 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), "<» (chapga) yoki «.» (joyida) 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.

TYURING MASHINASIga doir masalalar

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.