Tyuring mashinasi

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 holder.
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.

Tyuring mashinasi" simulyatori - universal ijrochining (mavhum hisoblash mashinasi) o'quv modeli bo'lib, 1936 yilda A. Tyuring tomonidan algoritm tushunchasini aniqlashtirish uchun taklif qilingan. Tyuring tezislariga ko'ra, har qanday algoritm Tyuring mashinasi uchun dastur sifatida yozilishi mumkin. Tyuring mashinasi o'z imkoniyatlari bo'yicha Post mashinasi va oddiy Markov algoritmlariga teng ekanligi isbotlangan.

Tyuring mashinasi karetkadan (o'qish va yozish kallagi) va hujayralarga bo'lingan cheksiz lentadan iborat. Lentaning har bir katagida A = (0, 1,..., N) alifbosidagi belgi bo'lishi mumkin. Har qanday alifboda bo'sh joy mavjud bo'lib, u 0 yoki l bilan belgilanadi. Buyruqlarni kiritishda bo'sh joy pastki chiziq "_" bilan almashtiriladi.
Turing mashinasi - bu stol bilan boshqariladigan mashina. Jadvaldagi qatorlar tanlangan A alifbosining belgilariga, ustunlar esa avtomat Q = (q 0, q 1,…, q M) holatlariga mos keladi. Ishning boshida Tyuring mashinasi q 1 holatda bo'ladi. q 0 holati yakuniy holat: unga kirgandan so'ng avtomat o'z ishini tugatadi.
Jadvalning qaysidir a i belgisiga va q j holatiga mos keladigan har bir katakda uchta qismdan iborat buyruq mavjud:

1. 
   A alifbosidagi belgi;
   
2. 
   harakat yo'nalishi:> (o'ngda),
   
3. 
   mashinaning yangi holati
   

YANGILIKLAR

1.