Turing mashinalari nima? Tyuring mashinasining tavsifi. Yarim cheksiz lentada ishlaydigan Tyuring mashinasi

Tyuring mashinasi 20-asrning eng qiziqarli va hayajonli intellektual kashfiyotlaridan biridir. Bu hisoblashning oddiy va foydali mavhum modeli (kompyuter va raqamli) bo'lib, har qanday kompyuter vazifasini amalga oshirish uchun etarlicha umumiydir. Oddiy tavsifi va matematik tahlili tufayli u nazariy kompyuter fanining asosini tashkil qiladi. Ushbu tadqiqot raqamli kompyuterlar va hisob-kitoblarni chuqurroq tushunishga olib keldi, jumladan, umumiy foydalanuvchi kompyuterlarida hal etilmaydigan ba'zi hisoblash muammolari mavjudligini anglash.

Bu nima va uni kim yaratgan

Alan Turing kompyuter bilan bir xil asosiy imkoniyatlarga ega bo'lgan mexanik qurilmaning eng ibtidoiy modelini tasvirlashga harakat qildi. Turing mashinani birinchi marta 1936 yilda London Matematik Jamiyatining Proceedings jurnalida paydo bo'lgan "Hisoblash mumkin bo'lgan raqamlar to'g'risida" kitobida tasvirlab bergan.

Tyuring mashinasi - bu o'qish / yozish kallagidan (yoki "skaner") iborat bo'lgan hisoblash qurilmasi bo'lib, u orqali qog'oz tasmasi o'tadi. Lenta kvadratlarga bo'linadi, ularning har biri bitta belgini - "0" yoki "1" ni olib yuradi. Mexanizmning maqsadi shundaki, u ham kirish va chiqish vositasi, ham hisob-kitoblarning oraliq bosqichlari natijalarini saqlash uchun ishchi xotira sifatida ishlaydi.

Qurilma nimadan yasalgan?

Har bir bunday mashina ikkita komponentdan iborat:

1. Cheksiz lenta. U har ikki yo'nalishda ham cheksiz bo'lib, hujayralarga bo'linadi.
2. Mashina boshqariladigan dastur, ma'lumotlarni o'qish va yozish uchun skaner boshidir. U har qanday vaqtda ko'plab shtatlardan birida bo'lishi mumkin.

Har bir mashina ikkita chekli ma'lumotlar seriyasini bog'laydi: kirish belgilarining alifbosi A = (a0, a1, ..., am) va holatlar alifbosi Q = (q0, q1, ..., qp). q0 holati passiv deb ataladi. Taxminlarga ko'ra, qurilma urilganda o'z ishini tugatadi. q1 holati boshlang'ich holat deb ataladi - mashina o'z hisob-kitoblarini uning boshida bo'lgan holda boshlaydi. Kiritilgan so'z lentaga har bir pozitsiyada ketma-ket bitta harf joylashtiriladi. Uning ikkala tomonida faqat bo'sh hujayralar mavjud.

Mexanizm qanday ishlaydi

Tyuring mashinasi hisoblash qurilmalaridan tubdan farq qiladi - uning saqlash qurilmasi cheksiz lentaga ega, raqamli qurilmalar uchun esa bunday qurilma ma'lum uzunlikdagi chiziqqa ega. Har bir vazifa sinfi faqat bitta qurilgan Tyuring mashinasi tomonidan hal qilinadi. Boshqa turdagi vazifalar yangi algoritm yozishni o'z ichiga oladi.

Tekshirish moslamasi bitta holatda bo'lib, lenta bo'ylab istalgan yo'nalishda harakatlanishi mumkin. U hujayralarga yozadi va ulardan oxirgi alifbodagi belgilarni o'qiydi. Ko'chirish paytida bo'sh element ajratiladi, u kirish ma'lumotlarini o'z ichiga olmaydigan pozitsiyalarni to'ldiradi. Turing mashinasi uchun algoritm boshqaruv qurilmasi uchun o'tish qoidalarini belgilaydi. Ular yozishni o'qish boshiga quyidagi parametrlarni o'rnatadilar: katakka yangi belgi yozish, yangi holatga o'tish, lenta bo'ylab chapga yoki o'ngga siljitish.

Harakat xususiyatlari

Tyuring mashinasi, boshqa hisoblash tizimlari kabi, o'ziga xos xususiyatlarga ega va ular algoritmlarning xususiyatlariga o'xshaydi:

1. diskretlik. Raqamli mashina keyingi bosqichga o'tadi n+1 oldingisi tugagandan keyingina. Har bir tugallangan qadam n+1 bo'lishini belgilaydi.
2. Aniqlik. Qurilma bir xil hujayra uchun faqat bitta amalni bajaradi. U alifbodagi belgiga kiradi va bitta harakatni amalga oshiradi: chap yoki o'ng.
3. Qat'iylik. Mexanizmdagi har bir pozitsiya berilgan sxemaning yagona variantiga mos keladi va har bir bosqichda harakatlar va ularni bajarish ketma-ketligi aniq.
4. Samaradorlik. Har bir qadam uchun aniq natija Turing mashinasi tomonidan aniqlanadi. Dastur algoritmni bajaradi va cheklangan miqdordagi bosqichlarda q0 holatiga o'tadi.
5. Ommaviy xarakter. Har bir qurilma alifboga kiritilgan ruxsat etilgan so'zlar bo'yicha aniqlanadi.

Tyuring mashinasining vazifalari

Algoritmlarni echishda ko'pincha funktsiyani amalga oshirish talab qilinadi. Hisoblash uchun zanjir yozish imkoniyatiga qarab, funktsiya algoritmik hal qilinadigan yoki hal etilmaydigan deb ataladi. Natural yoki ratsional sonlar to'plami sifatida mashina uchun chekli N alifbosidagi so'zlar, B to'plamining ketma-ketligi ko'rib chiqiladi - B=(0,1) ikkilik kod alifbosi doirasidagi so'zlar. Shuningdek, hisoblash natijasi algoritm "muzlatish" paytida yuzaga keladigan "aniqlanmagan" qiymatni hisobga oladi. Funktsiyani amalga oshirish uchun chekli alifboda rasmiy til mavjudligi va to'g'ri tavsiflarni tanib olish muammosi hal qilinishi muhimdir.

Qurilma dasturiy ta'minot

Turing mexanizmi uchun dasturlar jadvallarda joylashgan bo'lib, unda birinchi qator va ustun tashqi alifboning belgilarini va avtomatning mumkin bo'lgan ichki holatlarining qiymatlarini o'z ichiga oladi - ichki alifbo. Jadvalli ma'lumotlar Tyuring mashinasi qabul qiladigan buyruqlardir. Muammoni hal qilish shu tarzda davom etadi: u joylashgan katakdagi bosh tomonidan o'qilgan xat va avtomat kallagining ichki holati buyruqlardan qaysi biri bajarilishi kerakligini aniqlaydi. Xususan, bunday buyruq jadvalda joylashgan tashqi alifbo va ichki alifbo belgilarining kesishmasida joylashgan.

Hisoblash uchun komponentlar

Bitta aniq muammoni hal qilish uchun Tyuring mashinasini qurish uchun uning quyidagi parametrlarini aniqlash kerak.

tashqi alifbo. Bu A belgisi bilan belgilanadigan ba'zi chekli belgilar to'plami bo'lib, uning tarkibiy elementlari harflar deb ataladi. Ulardan biri - a0 - bo'sh bo'lishi kerak. Masalan, ikkilik sonlar bilan ishlaydigan Tyuring qurilmasining alifbosi quyidagicha ko'rinadi: A = (0, 1, a0).

Lentaga yozib olingan harf-ramzlarning uzluksiz zanjiri so'z deyiladi.

Avtomat - bu inson aralashuvisiz ishlaydigan qurilma. Turing mashinasida u muammolarni hal qilish uchun bir necha xil holatlarga ega va ma'lum sharoitlarda u bir pozitsiyadan ikkinchisiga o'tadi. Bunday tashish holatlari to'plami ichki alifbodir. Q=(q1, q2...) kabi harf belgisi mavjud. Bu pozitsiyalardan biri - q1 - boshlang'ich, ya'ni dasturni ishga tushiruvchi bo'lishi kerak. Yana bir zarur element - bu oxirgi holat bo'lgan q0 holati, ya'ni dasturni tugatuvchi va qurilmani to'xtash holatiga o'tkazadi.

O'tish stoli. Ushbu komponent mashinaning joriy holatiga va o'qilayotgan belgining qiymatiga qarab, qurilma vagonining xatti-harakati uchun algoritmdir.

Avtomat uchun algoritm

Turing qurilmasini ish paytida tashish 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'sh joyni almashtirish.
2. Bir qadam katakchani chapga yoki o'ngga siljiting.
3. Ichki holatingizni o'zgartiring.

Shunday qilib, har bir belgi yoki pozitsiya juftligi uchun dasturlarni yozishda uchta parametrni aniq tasvirlash kerak: a i - tanlangan A alifbosining elementi, vagonning siljish yo'nalishi ("←" chapga, "→" o'ngga, "nuqta" - harakat yo'q) va q k - qurilmaning yangi holati. Misol uchun, "q1" buyrug'i bilan mashinaning yangi holatini ko'rsatish buyrug'i "q12". chapga bir qadam katakchaga o'ting va q 2" holatiga o'ting.

Tyuring mashinasi: misollar

1-misol Vazifa lentada joylashgan berilgan sonning oxirgi raqamiga bitta qo'shadigan algoritmni qurishdir. Kirish ma'lumotlari - so'z - lentada ketma-ket hujayralarga yozilgan butun o'nlik sonning raqamlari. Dastlabki vaqtda qurilma eng o'ngdagi belgi - raqamning raqamiga qarama-qarshi joylashgan.

Yechim. Agar oxirgi raqam 9 bo'lsa, u 0 bilan almashtirilishi va oldingi belgiga bitta qo'shilishi kerak. Berilgan Turing qurilmasi uchun bu holda dastur quyidagicha yozilishi mumkin:

Bu erda q 1 - raqamni o'zgartirish holati, q 0 - to'xtash. Agar q 1 da avtomat 0..8 qatordagi 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 tuzatsa, u holda uni 0 bilan almashtiradi, so'ngra q 1 holatida to'xtab, chapga o'tadi. Ushbu harakat qurilma 9 dan kichik raqamni tuzatmaguncha davom etadi. Agar barcha belgilar 9 ga teng bo'lsa, ular nolga almashtiriladi, eng yuqori 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 Ochilish va yopish qavslarini bildiruvchi bir qator belgilar berilgan. Bir juft o'zaro qavslarni, ya'ni bir qatorda joylashgan elementlarni - "()" olib tashlaydigan Turing qurilmasini qurish kerak. Masalan, boshlang'ich ma'lumotlar: ") (() (()", javob quyidagicha bo'lishi kerak: ") .. ((". Yechim: q 1 da bo'lgan mexanizm, satrning eng chap elementini tahlil qiladi.

q 1 holati: agar “(” belgisi uchrasa, o‘ngga siljiting va q 2 holatiga o‘ting; agar “a 0” belgilangan bo‘lsa, to‘xtating.

q 2 holat: juftlik mavjudligi uchun “(” qavs tahlil qilinadi, mos kelsa, “)” olinishi kerak. Agar element juft bo'lsa, u holda chapga vagonga qaytishni bajaring va q 3 ga o'ting.

q 3 holati: avval “(”, keyin esa “)” belgisini o‘chiring va q 1 ga o‘ting.

1920-yillardan keyingi ifoda Hisoblash mashinasi ishlagan har qanday mashinalarga ishora qiladi inson kompyuteri, ayniqsa, Cherkov-Tyuring tezisining samarali usullariga ko'ra ishlab chiqilganlar. Ushbu tezis quyidagicha tuzilgan: "Har qanday algoritm mos keladigan Tyuring mashinasi yoki qisman rekursiv ta'rif ko'rinishida berilishi mumkin va hisoblanuvchi funktsiyalar sinfi qisman rekursiv funktsiyalar sinfiga va Tyuring mashinalarida hisoblanadigan funktsiyalar sinfiga to'g'ri keladi". Boshqacha qilib aytganda, Cherc-Tyuring tezisi elektron kompyuterlar kabi mexanik hisoblash qurilmalarining tabiati haqidagi gipoteza sifatida aniqlanadi. Har qanday hisoblash mumkin bo'lgan kompyuterda, agar u etarli vaqt va saqlash joyiga ega bo'lsa, amalga oshirilishi mumkin.

Cheksizlikni hisoblashda ishlaydigan mexanizmlar analog tip deb nomlandi. Bunday mexanizmlardagi qiymatlar doimiy raqamli qiymatlar bilan ifodalangan, masalan, milning burilish burchagi yoki elektr potentsialidagi farq.

Analog mashinalardan farqli o'laroq, raqamli mashinalar raqamli qiymatning holatini ifodalash va har bir raqamni alohida saqlash qobiliyatiga ega edi. Raqamli mashinalar tasodifiy xotira qurilmasi ixtiro qilinishidan oldin turli protsessorlar yoki relelardan foydalangan.

Ism Hisoblash mashinasi 1940-yillardan boshlab kontseptsiya bilan almashtirila boshlandi kompyuter. Bu kompyuterlar kotiblar qilgan hisob-kitoblarni bajarishga qodir edi. Qiymatlar endi jismoniy xususiyatlarga bog'liq bo'lmaganligi sababli (analog mashinalarda bo'lgani kabi), raqamli apparatga asoslangan mantiqiy kompyuter tasvirlanishi mumkin bo'lgan hamma narsani qila oldi. sof mexanik tizim .

Tyuring mashinalari hisoblash qobiliyatining chegaralarini hisobga olgan holda, nimani hisoblash mumkinligini matematik tarzda rasmiy ravishda aniqlash uchun mo'ljallangan. Agar Turing mashinasi vazifani bajara olsa, u holda bu vazifa Turing hisoblanishi mumkin deyiladi. Turing asosan nima hisoblash mumkinligini aniqlay oladigan mashinani loyihalashga e'tibor qaratdi. Tyuring, agar sonning taxminiyligini hisoblay oladigan Tyuring mashinasi mavjud ekan, bu qiymatni hisoblash mumkin degan xulosaga keldi. Bundan tashqari, Tyuring mashinasi AND, OR, XOR, NOT va "Agar-Then-Else" kabi mantiqiy operatorlarni sharhlashi mumkin.

Tyuring mashinasi quyidagi ob'ektlar to'plamidir

• 1) tashqi alifbo A=(a 0 , a 1 , …, a n );
• 2) ichki alifbo Q=(q 1 , q 2 ,…, q m ) - holatlar toʻplami;
• 3) boshqaruv belgilar to'plami (P, L, S)
• 4) har bir diskret vaqtda A alifbosidan faqat bitta belgini o'z ichiga olishi mumkin bo'lgan kataklarga bo'lingan har ikki yo'nalishdagi cheksiz lenta;
• 5) ko'p shtatlardan birida bo'lishga qodir boshqaruv moslamasi

Bo'sh katakning belgisi tashqi alifboning harfi, 0 dir.

Holatlar orasida dastlabki q 1, ya’ni mashina ishlay boshlaydigan holat va mashina bir marta to‘xtab qolgan yakuniy (yoki to‘xtash holati) q 0 farqlanadi.

Boshqarish moslamasi lentada chapga va o‘ngga harakatlanishi, A alifbosi belgilarini lenta katakchalariga o‘qish va yozishi mumkin.Boshqaruv moslamasi quyidagi shaklga ega bo‘lgan buyruqlar bo‘yicha ishlaydi.

q i a j > a p X q k

Yozib olish quyidagilarni bildiradi: agar boshqaruv moslamasi q i holatda bo‘lsa va kuzatilayotgan katakchada a j harfi yozilgan bo‘lsa, u holda (1) j o‘rniga p harfi yacheykaga yoziladi, (2) mashina hozirgina ko‘rilgan hujayradan keyingi o‘ng katakchani ko‘rishga o‘tadi, agar X= P bo‘lsa yoki keyingi chap katakcha ko‘rinishiga o‘tadi, agar X= L bo‘lsa, xuddi shu yacheykani ko‘rishni davom ettirsa, yoki X= L ni ko‘rishni davom ettirsa, (3) davlatga ketadi q k.

Mashinaning ishlashi, sharti bo'yicha, uning ma'lum bir momentdagi holati q bilan va shu daqiqada ko'rib chiqilayotgan hujayraning a mazmuni bilan to'liq aniqlanganligi sababli, har bir mumkin bo'lgan q i a j konfiguratsiyasi uchun aynan bitta qoida mavjud. Faqat mashina to'xtab qolgan oxirgi holat uchun qoidalar yo'q. Shuning uchun tashqi alifbosi A=(a0, a1, …, an) va ichki alifbosi Q=(q1, q2,…, qm) boʻlgan Tyuring mashinasi dasturida m (n+ 1) dan ortiq boʻlmagan koʻrsatmalar mavjud.

A alifbosidagi yoki Q alifbosidagi yoki A Q alifbosidagi so'z mos keladigan alifbodagi harflarning har qanday ketma-ketligidir. K-konfiguratsiya deganda, bu bosqichda qaysi katakcha ko'rilayotganini va mashinaning qanday holatda ekanligini ko'rsatuvchi k-qadam boshida hosil bo'lgan ma'lumot (yoki k-bosqich boshida lentaga yozilgan A alifbosidagi so'z) bilan mashina lentasi tasvirini tushunamiz. Faqat cheklangan konfiguratsiyalar mantiqiy, ya'ni. tasmaning barcha kataklari, cheklangan sondan tashqari, bo'sh bo'lganlar. Agar mashinaning holati yakuniy bo'lsa, konfiguratsiya yakuniy deb ataladi.

Agar Tyuring mashinasining yakuniy bo'lmagan konfiguratsiyasi boshlang'ich sifatida tanlansa, u holda mashinaning vazifasi yakuniy konfiguratsiyaga erishilgunga qadar mashina dasturiga muvofiq dastlabki konfiguratsiyani ketma-ket (bosqichma-bosqich) o'zgartirishdan iborat. Shundan so'ng, Tyuring mashinasining ishi tugallangan deb hisoblanadi va ishning natijasi erishilgan yakuniy konfiguratsiyadir.

A (a 0 ) = (a 1 , ..., a n ) alifbosidagi boʻsh boʻlmagan b soʻz lentaning ketma-ket yacheykalariga yozilsa, qolgan barcha katakchalar boʻsh boʻlsa va mashina b soʻzi yozilgan soʻzlardan eng chap yoki oʻngdagi katakchalarni skanerdan oʻtkazsa, standart holatda mashina tomonidan qabul qilinadi, deb aytamiz. Agar standart holatda so'zni idrok etuvchi mashina q 1 boshlang'ich holatda bo'lsa (mos ravishda to'xtash holatida q 0) standart pozitsiya boshlang'ich (yakuniy) deb ataladi.

Agar b so'zini qayta ishlash Tyuring mashinasini yakuniy holatga keltirsa, u b ga tegishli deb aytiladi, aks holda u b ga taalluqli emas (mashina cheksiz ishlaydi)

Bir misolni ko'rib chiqing:

Tashqi alifbosi A \u003d (0, 1) (bu erda 0 - bo'sh katakning belgisi), Q \u003d (q 0, q 1, q 2) ichki holatlar alifbosi va quyidagi funktsional diagramma (dastur) bilan Tyuring mashinasi berilgan:

q 1 0 > 1 L q 2;

q 1 1 > 0 S q 2 ;

q 2 0 > 0 P q 0 ;

q 2 1 > 1 C q 1;

Bu dasturni jadval yordamida yozish mumkin

Birinchi bosqichda buyruq ishlaydi: q 1 0 > 1 L q 2 (boshqaruv moslamasi q1 holatda, nazorat qilinadigan katakchada esa 0 harfi yoziladi, katakka 0 o‘rniga 1 yoziladi, bosh chapga siljiydi, boshqaruv moslamasi q2 holatiga o‘tadi), natijada mashinada quyidagi konfiguratsiya hosil bo‘ladi:

Nihoyat, q 2 0 > 0 P q 0 buyrug'i bajarilgandan so'ng, konfiguratsiya yaratiladi.

Ushbu konfiguratsiya yakuniy hisoblanadi, chunki mashina to'xtatilgan holatda q 0 .

Shunday qilib, asl so'z 110 mashina tomonidan 101 so'ziga qayta ishlanadi.

Olingan konfiguratsiyalar ketma-ketligi qisqaroq yozilishi mumkin (nazorat qilinadigan katakning mazmuni hozirda mashina joylashgan davlatning o'ng tomoniga yoziladi):

11q 1 0 => 1 q 2 11 => 1q 1 11 => 1q 2 01 => 10q 0 1

Turing mashinasi A Q alifbosidagi so'zlarni o'zgartirish uchun qandaydir qoida (algoritm) dan boshqa narsa emas, ya'ni. konfiguratsiyalar. Shunday qilib, Tyuring mashinasini aniqlash uchun uning tashqi va ichki alifbolarini, dasturini ko'rsatish va qaysi belgilar bo'sh katak va yakuniy holatni bildirishini ko'rsatish kerak.

1936 yilda Alan Tyuring algoritm tushunchasiga aniqlik kiritishni taklif qildi mavhum universal ijrochi. Uning mavhumligi shundaki, u haqiqiy kompyuter emas, balki mantiqiy hisoblash konstruksiyasidir. “Umumjahon ijrochi” atamasi bu ijrochi har qanday boshqa ijrochiga taqlid qila olishini bildiradi. Masalan, haqiqiy kompyuterlar bajaradigan amallarni universal bajaruvchida simulyatsiya qilish mumkin. Natijada, Turing tomonidan ixtiro qilingan hisoblash konstruktsiyasi chaqirildi Turing mashinasi.
Bundan tashqari, universal ijrochi muayyan vazifa uchun algoritm mavjudligi yoki yo'qligini isbotlay olishi kerak deb taxmin qilinadi.

Turing mashinasi nima?

Tyuring mashinasi har ikki yoʻnalishda ham cheksiz boʻlgan, yacheykalarga boʻlingan lenta va dastur tomonidan boshqariladigan avtomat (bosh)dan iborat.
Turing mashinalari uchun dasturlar jadval ko'rinishida yoziladi, bu erda birinchi ustun va qatorda tashqi alifbo harflari va avtomatning mumkin bo'lgan ichki holatlari (ichki alifbo) mavjud. Jadvalning mazmuni Turing mashinasi uchun ko'rsatmalardir. Hujayrada bosh o'qiydigan xat (u hozir joylashgan) va boshning ichki holati qaysi ko'rsatmani bajarish kerakligini aniqlaydi. Buyruq jadvaldagi tashqi va ichki alifbo belgilarining kesishishi bilan aniqlanadi.

Muayyan Tyuring mashinasini belgilash uchun uning quyidagi komponentlarini tavsiflash talab qilinadi:

• tashqi alifbo. Elementlari harflar (ramzlar) deb ataladigan chekli to'plam (masalan, A). Ushbu alifbodagi harflardan biri (masalan, 0) bo'sh belgi bo'lishi kerak.
• ichki alifbo. Bosh (avtomat) holatlarining chekli to'plami. Holatlardan biri (masalan, q 1) boshlang'ich bo'lishi kerak (dasturni ishga tushirish). Yana bir holat (q 0) yakuniy (dasturni tugatish) - to'xtash holati bo'lishi kerak.
• O'tish stoli. Avtomatning (boshning) holatiga va o'qilgan xarakteriga qarab xatti-harakatlarining tavsifi.

Tyuring mashinasining avtomati o'z ish jarayonida quyidagi harakatlarni bajarishi mumkin:

• Hujayraga tashqi alifbo belgisini yozing (shu jumladan bo'sh), undagini almashtiring (shu jumladan bo'sh).
• Bir katakchani chapga yoki o'ngga siljiting.
• Ichki holatingizni o'zgartiring.

Turing mashinasi uchun bitta buyruq bu uchta komponentning o'ziga xos birikmasidir: katakka qanday belgi yozish (mashina tepasida joylashgan), qaerga o'tish va qaysi holatga o'tish bo'yicha ko'rsatmalar. Garchi buyruq barcha komponentlarni o'z ichiga olmaydi (masalan, belgini o'zgartirmang, harakat qilmang yoki ichki holatni o'zgartirmang).

Turing mashinasi misol

Aytaylik, lentada #, $, 1 va 0 belgilaridan iborat so'z bor. Siz barcha # va $ belgilarini nolga almashtirmoqchisiz. Ishga tushirish vaqtida bosh chap tomonda so'zning birinchi harfi ustida joylashgan. Dastur bosh so'zning eng o'ngdagi harfidan keyin bo'sh belgi ustida bo'lganda tugaydi.
Eslatma: so'zning uzunligi va belgilar ketma-ketligi muhim emas. Rasmda ma'lum bir holat uchun buyruqlarni bajarish ketma-ketligiga misol ko'rsatilgan. Agar lentada boshqa so'z bo'lsa, u holda buyruqlar ketma-ketligi boshqacha bo'ladi. Shunga qaramay, Turing mashinasi uchun ushbu dastur (rasmda - chapdagi jadval) tasvirlangan tashqi alifboning har qanday so'zlariga qo'llaniladi (algoritmning bir xil turdagi barcha vazifalarga qo'llanilishi xususiyati kuzatiladi - ommaviy belgi).

Siz dasturni murakkablashtirishingiz mumkin. Aytaylik, bosh birinchisidan yuqorida emas, balki so'zning har qanday belgisi ustida joylashgan. Keyin berilgan Tyuring mashinasi uchun dastur shunday bo'lishi mumkin (yoki boshqacha bo'lishi mumkin):

Bu erda bosh bo'sh belgidan oshib ketguncha chapga siljiydi. Shundan so'ng, mashina q 2 holatiga kiradi (uning buyruqlari oldingi dasturning q 1 buyruqlari bilan bir xil).

Zamonaviy informatika fanining eng muhim savollaridan biri bu 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 olgan. Ular taklif qilgan ijrochilar bir-biridan farq qilar edi, lekin ular bir-biriga taqlid qilishlari, eng muhimi, har qanday rasmiy ijrochining ishiga taqlid qilishlari mumkinligi ma'lum bo'ldi.

Rasmiy ijrochi nima? Bir rasmiy ijrochi boshqa rasmiy ijrochining ishiga taqlid qilishi nimani anglatadi? 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 mashinasining 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 yozib olish uchun ishlatiladi.

Q=(q1, q2, q3,…, qm) — ichki alifbo, oʻquvchi-printerning holatlar toʻplamini tavsiflaydi.

Har bir lenta katakchasi tashqi alifbodan A = (a0,a1,…,an) belgisini o'z ichiga olishi mumkin (bizning holatda, A=(0, 1))

Tyuring mashinasining amaldagi harakatlari:

1) tashqi alifboning istalgan belgisini lenta katakchasiga yozing (ilgari bo'lgan belgining ustiga yoziladi)

2) keyingi katakka o'tish

3) holatni ichki Q alifbosi belgisi bilan ko'rsatilganlardan biriga o'zgartirish

Turing mashinasi - bu stol tomonidan boshqariladigan avtomat.

Jadvaldagi qatorlar tanlangan A alifbosi belgilariga, ustunlar esa avtomat Q = (q0,q1,…,qm) holatlariga mos keladi. Operatsiya boshida Tyuring mashinasi q1 holatda. q0 holati yakuniy holat bo'lib, unga kirgandan so'ng avtomat o'z ishini tugatadi.

Jadvalning qaysidir ai belgisiga va qandaydir qj holatiga mos keladigan har bir katakda uch qismdan iborat buyruq mavjud.
alifbosidagi belgi A
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 muammolarni hal qilishni ko'rib chiqaylik. Turing mashinasini veb-saytdagi bo'limda yuklab olishingiz mumkin.

Masala 1. A=(0, 1, _) bo‘lsin. Lentada hujayralar 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 yuk tashish holatlarini aniqlaymiz. Men ularni "vagonning biror narsa qilish istagi" deb atayman.

q1) Vagon o‘ng tomonga ketishi kerak: agar 0 ni ko‘rsa, 1 ga o‘zgartiradi va q1 holatda qoladi, 1 ni ko‘rsa, 0 ga o‘zgartiradi va q1 holatda qoladi, _ ni ko‘rsa, 1 katak orqaga “boshqa narsani xohlaydi”, ya’ni q2 holatiga o‘tadi. Keling, o'z fikrimizni ijrochi jadvaliga yozamiz. Sintaksis uchun dasturning yordamiga qarang.)

q2) Endi q2 “karetning xohishi”ni tasvirlaymiz. Biz asl holatiga qaytishimiz kerak. Buning uchun: agar biz 1 ni ko'rsak, uni qoldiring va q2 holatida qoling (belgilar seriyasining oxiriga etish istagi bilan); agar biz 0 ni ko'rsak, biz uni qoldiramiz va q2 holatida chapga o'tishni davom ettiramiz; qarang _ - 1 katak bilan o'ngga siljiydi. Bu erda muammoning holatida talab qilinadigan joydasiz. q0 holatiga o'tamiz.

Videoda dasturni amalda ko'rishingiz mumkin:

Masala 2. Berilgan: 0 va 1 ning chekli 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 etti birlik yozilgan va ularning o'rnida nollar mavjud.

Keling, muhokamaga o'taylik. Keling, vagonga qanday holatlar kerakligini va qanchaligini aniqlaymiz.

q1) arra 1 - uni nolga to'g'rilab, 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 bittasini ko‘rsa, oxiridagi belgiga imzo qo‘yishga o‘tadi. Men birlikni chizishim bilanoq, biz q4 holatiga o'tamiz

q4) hech narsani o‘zgartirmagan holda yozma birliklardan o‘ting. Ketma-ketlikni bittadan ajratib turadigan 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 o'tamiz

Tashish berilgan ketma-ketlikning oxirigacha q1 holatda o‘tib, bo‘sh katakka duch kelganida q0 holatini oladi.

Biz quyidagi dasturni olamiz:

Quyidagi videoda Tyuring mashinasining harakatini tomosha qilishingiz mumkin.