Tyuring mashinasi

shundayki”, Ya'ni, muallif undan foydalanishning barcha mumkin bo'lgan oqibatlari, jumladan, ma'naviy va moddiy yo'qotishlar, uskunaning ishdan chiqishi, jismoniy va ruhiy jarohatlar uchun hech qanday javobgarlikni o'z zimmasiga olmaydi.
Dasturni boshqa veb-saytlarga joylashtirishda manbaga havola talab qilinadi.

1. 
   1) har qanday shaklda materiallarni nashr qilish, shu jumladan boshqa veb-saytlarda materiallarni joylashtirish;
   
2. 
   2) to'liq bo'lmagan yoki o'zgartirilgan materiallarni tarqatish;
   
3. 
   3) materiallarni har qanday ommaviy axborot vositalarida to'plamlarga kiritish;
   
4. 
   4) materiallarni sotish yoki boshqa foydalanishdan tijorat foyda olish.
   

Materiallarni yuklab olish orqali siz ushbu litsenziya shartnomasi shartlarini qabul qilganligingizni bildirasiz.
Arxivni ochgandan so'ng, dastur ishlaydi va qo'shimcha o'rnatishlarni talab qilmaydi.
Xozirgi zamon informatika fanining eng muhim savollaridan biri bu, uning yordamida har qanday rasmiy ijrochiga taqlid qilish mumkin bo'lgan rasmiy ijrochining mavjudligidir. bu savolga javobni deyarli bir vaqtning o'zida ikkita taniqli olim - A. Turing va E. Post oldi. Ular taklif qilgan ijrochilar bir-biridan farq qilar edi, biroq ular bir-biriga taqlid qilishlari, eng muhimi, har qanday rasmiy ijrochining ishiga taqlid qilishlari mumkinligi ma'lum bo'ldi.
Rasmiy pudratchi nima? Bu nimani anglatadi - bir rasmiy ijrochi boshqa rasmiy ijrochining ishiga taqlid qiladimi? Agar siz kompyuter o'yinlarini o'ynagan bo'lsangiz, ekrandagi narsalar o'yinchining buyruqlariga shubhasiz bo'ysunadi. Har bir ob'ekt tegishli buyruqlar to'plamiga ega. Shu bilan birga, kompyuterning o'zi ijrochi bo'lib, virtual emas, balki haqiqiydir. Shunday qilib, bir rasmiy ijrochi boshqa rasmiy ijrochining ishiga taqlid qiladi.
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-saytdagi bo'limda 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. 1 katakni orqaga qaytaradi "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.