Tyuring mashinasining ishlashi

Teorema. Mashinalarning tarkibi T 1° T 2 mavjud.
1-savol={q 10, q 1,…, q n}
2-savol={q 20, q` 1 , …, q`n), keyin Q ni qurish uchun q 10 holatini olib tashlaymiz, uning nomini o'zgartiramiz q n +1 , bu ikkinchi mashinaning dastlabki holatiga to'g'ri keladi va boshqa barcha holatlar mavjud q` i = q n + 1 .
Turing hisoblash funktsiyalari:
f(x 1 …x n) funksiya chaqiriladi Turing hisoblash mumkin agar argument qiymatlari berilganda ushbu funktsiyaning qiymatini baholaydigan Tyuring mashinasi mavjud bo'lsa. f(x 1 …x n) funksiyasi natural sonlar to‘plamida aniqlanadi, lekin algoritmlar nazariyasi NÈ(0) natural sonlarning kengaytirilgan to‘plamini ko‘rib chiqadi.
F(x 1 ... x n) funksiyaning lentadagi argumentlari quyidagi so'z sifatida ifodalanadi:
Har bir argument ushbu argumentning qiymati qancha tayoqchaga to'g'ri keladi. Agar f funktsiyasi x 1 ... x n o'zgaruvchining berilgan qiymatlari to'plamida aniqlangan bo'lsa, Tyuring mashinasining ishlashi natijasida lentada ketma-ket yozilgan tayoqlar soni teng bo'lishi kerak. ushbu to'plamdagi funktsiyaning qiymatiga. Agar berilgan to'plamda f funksiya aniqlanmagan bo'lsa, u holda Tyuring mashinasi cheksiz ishlashi kerak.
Dastlabki konfiguratsiya - eng chap tayoqni o'qish.
1.6-rasm
1.6-rasmda quyidagi belgilar qo'llaniladi:
T 1, T 2 - Tyuring mashinalari;
ST 1, ST 2 - mos ravishda T 1 va T 2 mashinalarining buyruq tizimlari;
x - T 1 mashinasi uchun dastlabki ma'lumot;
T 1 (x) - T 1 mashinasining natijasi;
T 2 (T 1 (x)) - T 2 mashinasining ishining natijasi.
Masalan, ikkita mashinaning tarkibini ko'rib chiqaylik, ularning birinchisi nusxa ko'chirish operatsiyasini, ikkinchisi esa - unar kodda raqamlarni qo'shish operatsiyasini bajaradi. Mashinalarni birlashtirish sxemasi va olingan natijalar bilan lenta namunasi 1.7-rasmda ko'rsatilgan.

1.7-rasm
1.7-rasmda ko'rsatilgan kompozitsiya allaqachon ma'lum bo'lgan nusxa ko'chirish va qo'shish mashinalari yordamida sonni ikki barobarga oshirish operatsiyasini bajarishga imkon beradi. Shunday qilib, ma'lum operatsiyalar to'plamini (masalan, arifmetik operatsiyalar) echish uchun Tyuring mashinalarining ishlashi uchun algoritmlarni tuzgandan so'ng, murakkabroq muammolarni hal qilish uchun Tyuring mashinalarini tuzish mumkin. Shu bilan birga, umumiy algoritmni ishlab chiqish Tyuring mashinasida bajarish algoritmlari allaqachon ma'lum bo'lgan operatsiyalardan uning kompilyatsiyasiga qisqartiriladi. Ushbu yondashuv dasturlashda protseduralar va funktsiyalardan foydalanishga o'xshaydi.

Biroq, mashinalar tarkibidan foydalanish elementar amallarni bajarish algoritmlari ma'lum bo'lib, ulardan umumiy algoritm tuziladi. Shu sababli, ixtiyoriy muammolarni hal qilishda bu yondashuv yangi algoritmlarni ishlab chiqish va shunga mos ravishda turli xil boshqaruv bloklari bilan Tyuring mashinalarini ishlab chiqish zarurligini istisno qilmaydi. Universal Tyuring mashinasi yordamida boshqaruv blokining strukturasini o'zgartirmasdan istalgan algoritmni amalga oshirish mumkin.

1.2.2 Universal Tyuring mashinasi

Agar ba'zi Tyuring mashinasi berilgan bo'lsa (ya'ni, kirish, chiqish signallari va holatlarning alifbolari, boshning boshlang'ich holati va mashinaning dastlabki holati, shuningdek, mashinaning ishlash jadvali va dastlabki ma'lumotlarga ega lenta) ma'lum), keyin ushbu mashina uchun mo'ljallangan barcha ma'lumotlarni o'zgartirishni qo'lda bajarish mumkin. Aslida, bu holda, Tyuring mashinasini simulyatsiya qilish amalga oshiriladi.
Tyuring mashinasini simulyatsiya qilishda bajariladigan operatsiyalarni tahlil qilganda, simulyatsiya har bir bosqichda quyidagi harakatlarni takrorlashga qisqartirilishini aniqlash mumkin:
ÄBosh joylashgan lenta katakchasidagi belgini o'qish.
ÄMashinaning ishlash jadvalida buyruqni qidiring. Qidiruv mashinaning joriy holati va o'qilgan belgining qiymati bilan amalga oshiriladi.
ÄBuyruqdan lentaga yoziladigan belgini tanlang va uni yozing.
ÄBuyruqdan bosh harakati belgisini tanlash va uni harakatlantirish.
ÄBuyruqdan mashinaning yangi holatini tanlash va joriy holatni yangisiga o'zgartirish. Shundan so'ng keyingi bosqichga o'tish va bu bosqichlarni takrorlash.

ST

SU

1.8-rasm
Ushbu elementar operatsiyalarning tabiati shundaki, ularning barchasi dastlabki mashinaning ishlashini taqlid qiladigan boshqa Tyuring mashinasi tomonidan bajarilishi mumkin. Modellashtirishning mohiyati 1.8-rasmda tushuntirilgan.

Agar T mashinasida ST ko'rsatmalar to'plami bo'lsa va X ma'lumotli lentani qayta ishlasa, u holda uning ishlashini o'zining SU ko'rsatmalar to'plamiga ega bo'lgan boshqa U mashinasi simulyatsiya qilishi mumkin. Simulyatsiya uchun U mashinasining kirishida nafaqat X ma'lumoti bo'lgan lentani taqdim etish kerak , balki buyruq tizimi (ish stoli) ST. Ushbu buyruq tizimi dastlabki ma'lumot bilan bir xil lentaga yozilishi mumkin.

1.9-rasm
Simulyatsiya mashinasining muhim xususiyati shundaki, uning buyruq tizimi SU (va shunga mos ravishda boshqaruv blokining tuzilishi) simulyatsiya qilingan T mashinasining algoritmiga bog'liq emas. Har qanday boshqa Tyuring mashinasining ishini simulyatsiya qila oladigan Tyuring mashinasi. universal deb ataladi. Universal Tyuring mashinasi (UMT) tuzilishining varianti 1.9-rasmda keltirilgan.

UMT tasmasi uchta zonaga bo'lingan: ma'lumotlar zonasi, rejim zonasi va buyruq zonasi.
Ma'lumotlar zonasi simulyatsiya qilingan Turing mashinasi tomonidan qayta ishlanishi kerak bo'lgan dastlabki ma'lumotlarni o'z ichiga oladi. Xuddi shu zonada UMT ishining natijalari qayd etiladi.
Tartib zonasi ma'lum bir siklda ma'lumotlar zonasi yacheykasidan o'qilgan joriy holat Q t va joriy kirish belgisi X t ni o'z ichiga oladi.
Buyruqlar zonasida simulyatsiya qilingan mashina uchun buyruqlar tizimi mavjud. Buyruqlar guruhlarga ajratilgan. Birinchi guruhga Q 0 belgisidan boshlanadigan buyruqlar kiradi, ikkinchisi - Q 1 belgisi bilan va hokazo. Har bir guruh ichida buyruqlar X t belgisining qiymati bo'yicha tartiblanadi. Shunday qilib, lentadagi buyruqlar simulyatsiya qilingan mashinaning ishlash jadvaliga joylashtirilganidek tartibga solinadi.
Lentadan ma'lumotni o'qish va lentaga yozish uchta bosh yordamida amalga oshiriladi: D d - ma'lumotlar boshi, G r - rejim boshi, G c - buyruq boshi. Har bir bosh lentaning o'z zonasida harakatlanishi mumkin.
UMT ishi boshlanishidan oldin, lentaning har bir zonasida tegishli ma'lumotlar yozilishi kerak. Boshlar har bir zonada chap belgining ustiga o'rnatilishi kerak.
UMT ishi tsikllarda sodir bo'ladi, har bir tsiklda simulyatsiya qilingan mashinaning bitta buyrug'ining bajarilishi simulyatsiya qilinadi. UMT ish grafigi 1.10-rasmda ko'rsatilgan.

1.10-rasm

1.10-rasmda quyidagi belgilar qo'llaniladi:
Q G dan P gacha (G dan L, G r P, G r L, G d P, G d L) - boshlardan birini harakatlantirish
o'ng yoki chap;
Q (G to), (G d), (G r) - boshlardan biri tomonidan o'qilgan ma'lumot;
Q (G to) à (G r) - buyruq boshlig'i tomonidan ma'lumotlarni o'qish va bu ma'lumotlarni yozish
rejim boshini lenta rejimi maydoniga ishlatish;
Q a yordamchi o'zgaruvchi bo'lib, 1 qiymatini oladi, es-
G to va G r boshlari tomonidan o'qilgan belgilar mos keladimi;
Q in - 1 qiymatini qabul qiluvchi yordamchi o'zgaruvchi, es-
joriy (Q t) va yakuniy (Q z) holatlarning belgilari bir xil bo'ladimi
Q p - bu buyruq bo'lsa, 1 qiymatini qabul qiladigan signal
chapga o'tish qo'mondonlik zonasi chegaralaridan tashqariga chiqdi;
Har bir UMT siklida quyidagi bosqichlar bajariladi:
u buyruq zonasini qidiring;
zonada jamoa qidiryapsiz;
u buyruq bajarilishini simulyatsiya qilish.
Buyruqlar zonasini qidirish rejim zonasidan joriy Q t holatini buyruqlar zonasida birinchi buyruq boshida qayd etilgan Q i holati bilan solishtirishdan boshlanadi. Agar bu holatlar teng bo'lmasa, u holda buyruq boshi keyingi buyruqning boshiga o'tadi, buning uchun o'ngga besh bosh qadam bajariladi (U 0 - U 4 holatlar). Agar Q t va Q i belgilar mos kelsa, buyruqlar boshi kerakli zonaning birinchi buyrug'ining boshida bo'ladi. Keyinchalik, rejim zonasining Q t va X t belgilariga mos keladigan buyruqni qidirish boshlanadi. Buning uchun rejim boshi rejim zonasi belgisi X t, buyruq boshi esa joriy buyruqdagi X i belgisi ustiga o‘rnatiladi.
Zonadagi jamoani qidirish xuddi jamoa zonasini qidirish bilan bir xil tarzda amalga oshiriladi. Bunda buyruq boshi X t va X i belgilar solishtirilgunga qadar besh qadamda (U 5 - U 9 holatlari) o'ngga siljiydi.
Buyruqning bajarilishi (U 10 - U 17 holatlari) buyruq boshini bir qadam o'ngga siljitish bilan boshlanadi, shundan so'ng topilgan buyruqdan o'qilgan Y t belgisi avval o'qilgan X belgisi o'rniga ma'lumotlar boshi yordamida ma'lumotlar zonasiga yoziladi. t . Buyruq boshining keyingi bosqichi o'ngga o'tgandan so'ng, topilgan buyruqdan ma'lumotlar boshi harakati belgisi (Y d) o'qiladi va ma'lumotlar boshi ushbu belgiga (P, L) mos ravishda harakatlanadi. Uning ostida navbatdagi qayta ishlangan belgi (X t +1) joylashgan bo'lib, u keyingi siklni tayyorlash uchun rejim boshi yordamida rejim zonasiga yoziladi. Keyinchalik, buyruq va rejim boshlari rejim zonasiga keyingi holat Q t +1 yozilishi uchun o'rnatiladi (holatlar).
U 14 , U 15). U 16-davlatda qarorni bekor qilish sharti tekshiriladi. Agar keyingi holat belgisi simulyatsiya qilingan mashinaning yakuniy holati belgisiga (Q z) mos kelmasa, u holda masalaning yechimi tugallanmagan va U 17 holatda buyruq boshi dastlabki holatiga o‘tadi ( birinchi zonaning birinchi buyrug'ining boshiga). Bunday holda, UMT keyingi tsiklni bajarishga tayyor, ya'ni. keyingi buyruqning bajarilishini simulyatsiya qilish uchun.
Agar Q t va Q z belgilari mos kelsa, masalaning yechimi tugaydi va UMT yakuniy U z holatiga o'tadi.
UMT operatsiya jarayonini tahlil qilganda, UMT operatsiyasining algoritmi simulyatsiya qilingan Tyuring mashinasi qanday muammoni hal qilishiga bog'liq emasligi haqida muhim xulosa chiqarish mumkin. Shuning uchun, turli xil mashinalarni simulyatsiya qilishda UMT boshqaruv blokining tuzilishi o'zgarmaydi, ya'ni. hal qilinishi kerak bo'lgan vazifalarga bog'liq emas. Shuning uchun UMT haqiqatan ham universal mashina bo'lib, uning yordamida har qanday algoritmni tuzilishini o'zgartirmasdan bajarish mumkin.
Keyingi UMT buyrug'ini tanlash va uning bajarilishi lenta kataklarini ketma-ket sanab o'tish bilan bog'liq bo'lganligi sababli, UMT bo'yicha masalalarni hal qilish juda ko'p vaqtni talab qiladi. Shuning uchun Tyuring mashinasi, shu jumladan universali ham hech qachon qurilmagan, ammo unda zamonaviy kompyuterlarning analogini ko'rish oson. Shunday qilib, UMT buyruq zonasidagi buyruqlar tizimi mashina dasturiga o'xshaydi, Q t va X t belgilar juftligi esa mashina buyrug'ining manzili rolini o'ynaydi.
Biroq, Tyuring mashinasi algoritmlarni tavsiflash uchun juda qulay vosita bo'lib, algoritmlar nazariyasida keng qo'llaniladi.