Tyuring mashinalari tarkibiga misollar. Turing mashinasida funktsiyalarni to'g'ri hisoblash
Tyuring mashinasi (MT) - mavhum ijrochi (mavhum hisoblash mashinasi).
Algoritmlar kombinatsiyasi - bu bir nechta berilganlardan yangi algoritmlarni qurish uchun bir qator aniq usullar uchun yaratilgan nom.
Algoritmlar kombinatsiyasi haqidagi teoremalar algoritmlarning umumiy nazariyasining muhim bo'limini tashkil qiladi. Tasdiqlangandan so'ng, ular keyinchalik ularni aniqlaydigan sxemalarni yozmasdan murakkab va noqulay algoritmlarning maqsadga muvofiqligini tekshirishga imkon beradi.
Tyuring mashinasi uchun algoritmlarning kombinatsiyasi Tyuring mashinalaridagi operatsiyalar bilan tavsiflanadi.
1. Kompozitsiya bilan ishlash.
M 1 va M 2 bir xil tashqi A« alifbosiga (a 0 ,a 1 ,...,a p ) ega Tyuring mashinalari boʻlsin. Ularning holatlari to'plamlarini mos ravishda Q1 "(q 0,q 1,...,q n) va Q2 "(q 0",q 1",...,q m" deb belgilaymiz.
Ta'rif.
M 1 va M 2 mashinalar tarkibi M=M 1 ×M 2 deb belgilangan mashina boʻlib, uning dasturi A alifbosi, Q« holatlar toʻplami (q 0,q 1,...,q n,q)ga ega. n+1,... ,q n+m) va M 1 va M 2 mashinalarining dasturlaridan quyidagicha olinadi: M 1 mashinasi dasturining hamma joyida, bu yerda q 1 (belgili “uchlik”lar mavjud. mashinaning yakuniy holati M 1), u q 0" belgisi bilan almashtiriladi (mashinaning dastlabki holati M 2); M 1 va M 2 mashinalari dasturlaridagi barcha boshqa belgilar o'zgarishsiz qoladi (oxir-oqibat, bularning barchasi M mashinasining barcha holatlarini qayta raqamlash qoladi: (q 0 ,q 1" ,q 2 ,...,q n ,q 0 " ,q 2" ,...,q m" )).
Kompozitsiya M 1 mashinasi sifatida «ishlay» boshlaydi, lekin M 1 mashinasi to'xtab qolishi kerak bo'lgan hollarda, q 1 ning q 0 ga almashtirilishi hisobiga M 2 mashinasining dasturiga o'tadi. Shubhasiz, kompozitsiya amali assotsiativ, lekin kommutativ emas.
Uning ishlashi T1 va T2 mashinalarining ketma-ket ishlashiga teng.
Rasmda n=1 va m=1 uchun superpozitsiya operatorini amalga oshiradigan Tyuring mashinalarining tarkibi ko'rsatilgan.
1-rasm.
Ta'rif.
Tyuring mashinasi M iteratsiyasi mashina deb ataladi
2. Tarmoqlanish operatsiyasi.
M 1, M 2 va M 3 bir xil tashqi alifbosi A« (a 0,a 1,...,a i,...,a j,...,a p) va shunga mos ravishda to‘plamlarga ega Tyuring mashinalari bo‘lsin. aytadi: Q1 " (q 0 ,q 1 ,...,q n ), Q2 " (q 0 " ,q 1 " ,...,q m " ), Q3 " (q 0 " , q 1 " ,.. .,q l").
Ta'rif.
M 1, M 2 va M3 Tyuring mashinalari ustidagi tarmoqlanish operatsiyasining natijasi Tyuring mashinasi M deb ataladi, uning dasturi M 1, M 2 va M 3 mashinalarining dasturlaridan quyidagicha olinadi: M1 mashinasi yoziladi, keyin M 2 va M 3 mashinalarining dasturlari tayinlanadi. Agar M1 mashinasining yakuniy q 1 holatida a i belgisi kuzatilsa, u holda boshqaruv M 2 mashinasiga o'tkaziladi, ya'ni. q 1 belgisi q 0" belgisi bilan almashtiriladi va M 2 mashinasi ishlay boshlaydi. Agar M 1 mashinasining yakuniy q 1 holatida a j belgisi kuzatilsa, u holda boshqaruv M 3 mashinasiga o'tkaziladi, ya'ni q 1 belgisi almashtiriladi. belgisi bilan q 0" va M 3 mashinasi ishlay boshlaydi. M 1 va M 2 mashinalari dasturlaridagi barcha boshqa belgilar o'zgarishsiz qoladi. M mashinasi o'z ishini yakuniy q 1 holatida yakunlaydi (xulosa qilib aytganda, M mashinasining holatlarini oxirigacha qayta raqamlashni amalga oshirish qoladi).
Tyuring M 1, M 2 va M3 dastgohlarida filial operatsiyasi natijasi quyidagicha belgilanadi:
Ikki harfli Tyuring mashinalari uchun (ikki harfli alifboli Tyuring mashinalari) ixtiyoriy M1, M2 va M3 Tyuring mashinalarida filial ishi quyidagicha belgilanadi:
bular. agar M1 mashinasi q 1 holatda ishlayotgan bo'lsa, a 0 belgisi kuzatilsa, u holda boshqaruv M2 mashinasiga, aks holda M3 mashinasiga o'tkaziladi.
3. Loop operatsiyasi.
M alifbosi A« (a 0 ,a 1 ,...,a p ) va Q« holatlar toʻplami (q 0 ,q 1 ,...,q n ) boʻlgan Tyuring mashinasi boʻlsin.
Ta'rif.
Loop operatsiyasining natijasi Tyuring mashinasi deb ataladi, uni (i=0,2,3,...,n; j=0,1,2,...,p; s=0,2, 3,..., n)
uning dasturi M mashinasi dasturidan q 1 belgisini q i a j ®q 1 a t r, rO(L,R,L), t=0,1,2,.. buyrug‘i natijasiga almashtirish orqali olinadi. .p, q s belgisi bilan.
2.4 Tyuring mashinasi variantlari
Turing mashinasi modeli kengaytirilishi mumkin. Tyuring mashinalarini ixtiyoriy miqdordagi lentalar va turli cheklovlarga ega ko'p o'lchovli lentalarni ko'rib chiqish mumkin. Biroq, bu mashinalarning barchasi Tyuring to'liq va oddiy Tyuring mashinasi tomonidan modellashtirilgan.
Bunday ekvivalentlikka misol sifatida har qanday MTni yarim cheksiz lentada ishlaydigan MTga qisqartirishni ko'rib chiqing.
Teorema: Har qanday Tyuring mashinasi uchun yarim cheksiz lentada ishlaydigan ekvivalent Tyuring mashinasi mavjud.
Isbot:
Keling, Yu. G. Karpovning isbotini ko'rib chiqaylik. Bu teoremaning isboti konstruktivdir, ya'ni biz har qanday Tyuring mashinasi uchun e'lon qilingan xususiyatga ega ekvivalent Tyuring mashinasini qurish mumkin bo'lgan algoritmni beramiz. Birinchidan, biz MT ishchi lentasining kataklarini tasodifiy raqamlaymiz, ya'ni lentada ma'lumotlarning yangi joyini aniqlaymiz:
1-rasm.
Keyin biz hujayralarni qayta raqamlaymiz va "*" belgisi MT lug'atida mavjud emas deb taxmin qilamiz:
1-rasm.
2.5 Turing hisoblanishi va qaror qabul qilinishi
Rekursiv funksiyalar, Tyuring mashinalari yoki oddiy Markov algoritmlari yordamida hisoblanuvchi funksiyalar sinflari mos kelishi yuqorida isbotlangan. Bu bizga "hisoblash algoritmi" tushunchasini tavsiflash usuliga o'zgarmas deb hisoblash imkonini beradi. Farqlar faqat algoritmik obyektlardan foydalanishda kuzatiladi. Agar rekursiv funktsiyalar uchun ob'ektlar sonlar va sonli funktsiyalar bo'lsa va hisoblash jarayoni superpozitsiya, rekursiya, minimallashtirish va iteratsiya operatorlari tomonidan aniqlansa, Tyuring mashinalari uchun bunday ob'ektlar tashqi va ichki xotira alifbosi belgilari va hisoblash. jarayon chiqish, o'tish va boshni harakatlantirish yordamida protokol bilan belgilanadi. Oddiy Markov algoritmi uchun bunday ob'ektlar so'zlar yoki belgilar ketma-ketligi bo'lib, hisoblash jarayoni belgilarning dastlabki ketma-ketligi tarkibi va tuzilishini kerakli natijaga o'zgartiradigan almashtirish qoidalari yoki mahsulotlar bilan belgilanadi.
Arifmetik (raqamli) funktsiya - bu qiymatlar diapazoni N to'plamning pastki to'plami bo'lgan funktsiya va uning aniqlanish sohasi N to'plamining elementi.
Algoritmik muammolar uchun x 1, x 2 argumentlarining butun son qiymatlariga qarab f(x 1, x 2, ..., x n) raqamli funktsiyani hisoblash algoritmini topish kerak bo'lgan odatiy holat. , ..., x n.
Agar funktsiya qiymatini hisoblash uchun uning argumentlari qiymatlari to'plamiga ruxsat beruvchi algoritm mavjud bo'lsa (yoki funktsiya berilgan to'plamda aniqlanmaganligini ko'rsatsa) f:N n →N funktsiyasini hisoblash mumkin deb ataymiz. Hisoblash funksiyasining ta'rifi algoritmning intuitiv kontseptsiyasidan foydalanganligi sababli, ko'pincha "hisoblash funksiyasi" atamasi o'rniga "intuitiv hisoblash funktsiyasi" atamasi qo'llaniladi. Shunday qilib, agar masalaga mos keladigan arifmetik funktsiya intuitiv ravishda hisoblash mumkin bo'lsa, ommaviy muammoning echimi bor.
Agar berilgan k 1 , k 2 , …, k n argumentlar uchun f(k 1, k 2, …, k n) ba'zi mavjud mexanik protsedura (algoritm) yordamida.
Algoritm tushunchasiga aniqlik kiritish o‘rniga, biz “hisoblash funksiyasi” tushunchasini aniqlashtirish haqida o‘ylashimiz mumkin. Odatda ular quyidagi sxema bo'yicha davom etadilar:
1. Aniq belgilangan funksiyalar sinfi kiritiladi.
2. Bu sinfdagi barcha funksiyalar hisoblash mumkinligiga ishonch hosil qiling.
3. Hisoblash funksiyalar sinfi kiritilgan funksiyalar sinfiga to‘g‘ri keladi degan gipotezani (tezisni) qabul qiling.
Agar funktsiyani hisoblaydigan algoritm mavjud bo'lsa, uni hisoblash mumkin deb ataladi. "Hisoblash qobiliyati" algoritmlar nazariyasining asosiy tushunchalaridan biri bo'lib, hisoblanayotgan funktsiya va algoritmga o'zgarmasdir. Hisoblash funksiyasi va algoritm o'rtasidagi farq funktsiya tavsifi va mustaqil argumentlar qiymatlarini hisobga olgan holda uning qiymatlarini hisoblash usuli o'rtasidagi farqdir.
Tyuringning ishi. Har qanday intuitiv algoritm Tyuring mashinasi yordamida amalga oshirilishi mumkin.
Tyuring tezislaridan kelib chiqadiki, agar algoritmik masalalar yuzaga kelsa, ularni Tyuring mashinalarini qurish, ya'ni algoritmning yetarlicha rasmiylashtirilgan tushunchasi asosida yechish kerak. Bundan tashqari, algoritmik masalalarda biz ko'pincha algoritmni qurish haqida emas, balki ba'zi maxsus tuzilgan funktsiyalarni hisoblash mumkinligi haqida gapiramiz.
Shuni ta'kidlash kerakki, bu holatlarda (0,|) alifbosidan foydalanish kifoya, bu erda 0 bo'sh belgidir. Masalan, natural sonlar, jumladan 0, bu alifboda quyidagicha kodlangan: 0 - |; 1 - ||; 2 -
N - ||…| (n + 1 marta). Qisman sonli n-lokal funksiya f(x1, x2, ..., xn) agar uni quyidagi ma'noda hisoblaydigan M mashinasi mavjud bo'lsa, Turing hisoblanuvchi deyiladi: 1. Agar argument qiymatlari to'plami bo'lsa.
O'Z-O'ZI QO'LLANISH MUAMMOSI
Turing mashinasining ta'rifiga ko'ra, bu uchlikdir T=
P: qi a a j a ® q r a a s a S t a , a = 1, 2, …, k , Qayerda S 1- R, S 2- L, S 3- C . (*)
Bunday holda, biz bir nechta umumiy alifbolar mavjudligini taxmin qilishimiz mumkin A 0 Va Q 0, qaysi belgilarda yozilgan a Va q barcha Turing mashinalari uchun. Keyin belgilar qi a, a j a, q r a, a s a, S t a alifbo belgilaridir A 0 Va Q 0.
Ushbu yondashuv barcha Tyuring mashinalarini raqamlash imkonini beradi, ya'ni har bir mashinaga ushbu mashinaga xos bo'lgan ma'lum bir raqam (kod) beriladi, bu orqali uni boshqa mashinalardan ajratib olish mumkin. Bu erda raqamlash usullaridan birini ko'rib chiqamiz.
Tyuring mashinalarining godeli raqamlanishi. Mayli p 1, p 2, p 3 , ... - o'sish tartibida joylashtirilgan tub sonlar ketma-ketligi, masalan, 2, 3, 5, 7, 11, 13, ...
Dastur bilan Tyuring mashinasi raqami (*) chaqirilgan raqam
n(T) = .
Misol
Funktsiyani amalga oshiradigan mashina S(x)= x + 1 , alifboda dasturga ega {0, } . Buni hisobga olgan holda ushbu dasturning soni a 0 = 0 , a 1= | raqam bo'ladi:.
n(T)= 2 1 3 1 5 1 7 1 11 1 13 1 17 0 19 0 23 1 29 3.
Shubhasiz, hamma natural sonlar Tyuring mashinasi raqamlari emas. Boshqa tomondan, agar n - ma'lum bir mashinaning soni, umumiy alifbolarda, keyin uning dasturi ushbu raqamdan noyob tarzda tiklanishi mumkin.
Avtomobil T, so'zga tegishli n(T)(ya'ni o'z raqamingizning kodiga), o'z-o'zidan qo'llaniladigan deb ataladi .
O'z-o'zidan qo'llaniladigan mashinalarni ham, o'z-o'zidan qo'llanilmaydigan mashinalarni ham qurish mumkin. Misol uchun, berilgan misoldagi mashina o'z-o'zidan qo'llaniladi. Avtomobil T, dasturning o'ng qismlarida (jadvalning tanasida) to'xtash belgisi bo'lmagan, hech qanday so'zga taalluqli emas va shuning uchun so'zga n(T).
O'z-o'zini qo'llash muammosi quyidagicha: har qanday Tyuring mashinasi berilganda, uning o'z-o'zidan qo'llanilishi yoki yo'qligini aniqlaydigan algoritmni ko'rsatish.
Tyuring tezisiga ko'ra, bunday algoritmni Tyuring mashinasi ko'rinishida izlash kerak. Ushbu mashina barcha Tyuring mashinalarining raqam kodlariga taalluqli bo'lishi kerak va sinovdan o'tayotgan mashinalarning kodlarini qayta ishlash natijasiga qarab, turli xil yakuniy konfiguratsiyalarga ega bo'lishi kerak.
Masalan, bu mashinani olaylik T kodga qo'llaniladi n(T * ) . Agar mashina T * o'z-o'zidan qo'llaniladi, so'ngra oxirgi mashina konfiguratsiyasi T kabi ko'rinadi a" q 0 | B", va agar mashina T * o'z-o'zidan qo'llanilmaydi, keyin mashinaning yakuniy konfiguratsiyasi T kabi ko'rinadi a" q 0 0 B ". Bu yerga a, B, a, B- so'zlar.
Teorema O'z-o'zini qo'llash muammosi algoritmik jihatdan hal etilmaydi, ya'ni yuqoridagi ma'noda bu masalani hal qiladigan Tyuring mashinasi yo'q.
Teoremadan kelib chiqadiki, o'z-o'zini qo'llash masalasini hal qiladigan umumiy algoritm mavjud emas. Muayyan maxsus holatlarda bunday algoritmlar mavjud bo'lishi mumkin.
Keling, ushbu teorema natijalaridan boshlang'ich so'z uchun qo'llanilishi mumkin bo'lgan muammoning hal qilinmasligini isbotlash uchun foydalanamiz.
Boshlang'ich so'zga qo'llanilishi muammosi quyidagicha: mashinaga ko'ra, algoritm yaratish T va so'z X o'rnatish bo'lardi, tegishli mashina T aytmoqchi X yoki yo'q (aks holda to'xtash muammosi mavjud).
Tyuring mashinalari nuqtai nazaridan, o'z-o'zini qo'llash muammosining formulasiga o'xshash, bu muammo quyidagicha tuzilgan: shaklning barcha so'zlariga mos keladigan mashinani qurish mumkinmi? n(T) 0 X , Qayerda T ixtiyoriy mashina, X – o'zboshimchalik so'z, va agar mashina T so'z uchun amal qiladi X a" q 0 |B" , va agar mashina T so'zga taalluqli emas X , yakuniy konfiguratsiyaga olib keladi a" q 0 0 B" . Bu yerga a" , B" Va a", B"- ixtiyoriy so'zlar.
Teorema Boshlang'ich so'zga qo'llanilishi muammosi algoritmik jihatdan hal etilmaydi, ya'ni yuqoridagi ma'noda bu masalani hal qiladigan Tyuring mashinasi yo'q.
Yuqorida aytib o'tilganidek, o'z-o'zini qo'llash muammosi uchun birinchi dastlabki qadam raqamlashdir. Shuning uchun quyida ushbu masala algoritmlar va uning uchta asosiy algoritmik modellari uchun izchil ko'rib chiqiladi va hal qilinadi.
Algoritmlarni raqamlash
Algoritmlarni raqamlash ularni tadqiq qilish va tahlil qilishda muhim rol o'ynaydi. Har qanday algoritmni chekli so'z sifatida ko'rsatish mumkin bo'lganligi sababli (ayrim alifbo belgilarining chekli ketma-ketligi sifatida ifodalanadi) va chekli alifbodagi barcha chekli so'zlar to'plami sanab bo'ladigan bo'lsa, u holda barcha algoritmlar to'plami ham sanab o'tiladi. Bu natural sonlar to‘plami va algoritmlar to‘plami o‘rtasida yakkama-yakka xaritalash mavjudligini, ya’ni har bir algoritmga raqam berish imkoniyatini bildiradi.
Algoritmlarni raqamlash ham barcha algoritmik hisoblab chiqiladigan funksiyalarni raqamlashdir va har qanday funksiya cheksiz sonli sonlarga ega bo‘lishi mumkin.
Raqamlashning mavjudligi algoritmlar bilan xuddi raqamlar bilan ishlashga imkon beradi. Raqamlash, ayniqsa, boshqa algoritmlar bilan ishlaydigan algoritmlarni o'rganishda foydalidir.
Boshlang'ich ob'ektlar to'plami X va kerakli ob'ektlar to'plami Y bilan ma'lum bir massa muammosi bo'lsin. Massa muammosining echimi mavjud bo'lishi uchun X va Y to'plamlarning elementlari konstruktiv ob'ektlar bo'lishi kerak. Binobarin, bu to'plamlarning elementlarini natural sonlar bilan raqamlash mumkin. X∈ X qandaydir boshlang'ich ob'ekt bo'lsin, uning sonini n(x) bilan belgilaymiz. Agar x asl ob'ekt uchun massa masalasida n(y) sonli kerakli y∈ Y ob'ektni olish kerak bo'lsa, u holda f arifmetik funksiyani aniqlaymiz: Nn →N f(n(x))=n bo'lsin. (y).
Ommaviy masalalar uchun arifmetik funktsiyalarni qurish misoli sifatida, massa masalalarini ko'rib chiqaylik.
1. Agar ] natural sonlar massivi berilgan bo‘lsa, unga 2x1, 3x2,... p(n)xn natural sonini berish mumkin, bunda p(n) n-tutq sondir. 5 uzunlikdagi massivni misol qilib olaylik:
] 2x13x25x37x411x5.
Bu raqamlash f arifmetik funksiyasini belgilaydi (masalan, f(73500) = f(22315372110) = 20315272113 = 4891425).
2. Har qanday ratsional son qandaydir natural songa ega. Muammoning kerakli ob'ektlari to'plamini raqamlash ahamiyatsiz:
("ha", "yo'q") a (1, 0). Berilgan massa muammosi uchun siz oldingi misoldagi texnikadan foydalanib, bitta argumentning arifmetik funktsiyasini qurishingiz mumkin yoki uchta argumentning funktsiyasini ko'rib chiqishingiz mumkin (asl uchlik elementlarining uchta soni).
3. Dastur matnlarini nomerlash quyidagicha amalga oshirilishi mumkin: har qanday dasturni 256-ariy sanoq sistemasida raqam yozuvchi sifatida qabul qilish mumkin (agar dasturni yozish uchun ASCII jadval belgilaridan foydalanilgan bo'lsa).
Ommaviy muammodan arifmetik funktsiyaga o'tish bizga ommaviy muammoning echimi mavjudligi haqidagi savolni arifmetik funktsiyaning qiymatlarini uning argumentidan hisoblashning samarali usuli mavjudligi haqidagi savolga kamaytirishga imkon beradi ( argumentlar).
Raqamlar to'plamini raqamlash
Algoritmlar nazariyasida bir nechta o'zgaruvchining funktsiyalarini o'rganishni bitta o'zgaruvchining funktsiyalarini o'rganishga qisqartirish imkonini beradigan texnika keng tarqaldi. U sonlar to‘plamini raqamlashga asoslangan bo‘lib, sonlar to‘plami va ularning raqamlari o‘rtasida bijektiv moslik mavjud bo‘lib, raqamlar to‘plamidan uning sonini va sondan sonlar to‘plamining o‘zini aniqlaydigan funksiyalar odatda rekursivdir. Masalan, ikkita mustaqil o'zgaruvchini (x, y) o'z ichiga olgan funktsiya uchun h(x, y) xaritalash quyidagicha bo'lishi mumkin:
1-rasm.
(x, y) juftlari qisman tartiblangan N(2) to‘plamni tashkil etsin. Agar h(x, y) = n berilgan bo'lsa, u holda teskari xaritalash mavjud: x = h -1 1 (n) va y= h -1 2 (n), ya'ni h(h -1 1 (n), h). -1 2 (n)) = n. Bu har qanday juftlik (x, y) uchun n raqamini hisoblash va aksincha, x va y qiymatlarini hisoblash uchun n raqamidan foydalanish imkonini beradi:
Ushbu qoidalardan foydalanib, siz h 2 (x, y, z) = h (h (x, y), z) = n uchliklarining raqamlanishini va aksincha, uchlik soni bo'yicha - qiymatlarni hisoblashingiz mumkin. x, y, z. Masalan, h 2 (x, y, z) = n bo'lsa, z= h -1 2 (n), y= h -1 2 (h -1 1 (n)), x= h -1 1 ( h -1 1 (n)), h 2 (x, y, z) = h(h(h -1 1 (h -1 1 (n)), h -1 2 (h -1 1 (n)) ), h -1 2 (n)). Uchlik (x, y, z) qisman tartiblangan N(3) to‘plamni hosil qiladi. Xuddi shunday, ixtiyoriy sonli raqamlar uchun bizda:
h n-1 (x1, x2,…, xn)=h(h…h(h(x1, x2), x3)… x n-1), xn). Agar h n-1 (x1, x2,…, xn)=m bo'lsa, xn = h -1 2 (m), x n-1 =h -1 2 (h -1 1 (m)), ... ................................, x2 = h -1 2 (h -1 1 (. .. h -1 1 (m)...)), x1 = h -1 2 (h (...h (m)...)).
N (1) , N (2) ,..., N (i) ,..., N(n) to‘plamlar to‘plamlarining raqamlanishiga ega bo‘lgan holda, bu yerda N (i) sonlar to‘plami (i) to‘plamidir, M = N (1) N (2) ... N (i) .. N(n) , bu yerda M N. Har qanday n N uchun bizda h(x1, x2,..., xn )= h(h n −1 (x1,x2,..., xn), n −1).
Agar h(x ,1x ,2..., x)n = m, u holda h n−1 (x ,1x ,2..., x)n = h -1 1 (m), n= h -1 2 (m)+1. Yuqoridagi formulalar yordamida siz x1, x2,…, xn qiymatlarini tiklashingiz mumkin.
Tegishli ma'lumotlar.
Tyuring mashinasining ta'rifi, ishlashi va ko'rsatish usullari
Tyuring mashinasi deganda quyidagi qismlardan tashkil topgan ma'lum bir faraziy (mavhum) mashina tushuniladi (3.1-rasm).
1) har ikki yo'nalishda cheksiz lenta, hujayralarga bo'lingan, ularning har birida alifbodan faqat bitta belgi, shuningdek bo'sh belgi l yozilishi mumkin;
2) boshqarish moslamasi (ishchi bosh), u istalgan vaqtda to'plamdagi holatlardan birida bo'lishi mumkin. Har bir shtatda bosh hujayraning qarshisida joylashgan bo'lib, unga alifbodan xat o'qishi (ko'rib chiqish) yoki yozishi mumkin. A.
Guruch. 3.1. Tyuring mashinasi
MT ning ishlashi elementar bosqichlar (tsikllar) ketma-ketligidan iborat. Har bir qadam quyidagi amallarni bajaradi:
1. ishchi bosh belgini o‘qiydi (ko‘rib chiqadi);
2. uning holatiga va kuzatilayotgan belgiga qarab, bosh belgi ishlab chiqaradi va uni kuzatilayotgan hujayraga yozadi (ehtimol =);
3. bosh bir hujayrani o'ngga siljitadi (R), chap (L) yoki joyida qoladi (E);
4. Bosh boshqa ichki holatga o'tadi. (ehtimol =).
Davlat boshlang'ich va yakuniy deb ataladi. Yakuniy holatga kirganda, mashina to'xtaydi.
MTning to'liq holati deyiladi konfiguratsiya . Bu lentaning katakchalari o'rtasida harflarning taqsimlanishi, ishlaydigan boshning holati va kuzatilayotgan hujayra. Konfiguratsiya aniq t ko‘rinishda yoziladi: , bu yerda kuzatilayotgan katakchaning chap tomonidagi pastki so‘z, kuzatilayotgan katakchadagi harf, o‘ngdagi pastki so‘z.
Dastlabki konfiguratsiya va yakuniy konfiguratsiya standart deb ataladi.
MT faoliyatini tavsiflashning 3 ta usuli mavjud:
Shaklning buyruqlar tizimi
Funktsional jadval;
O'tishlarning grafigi (diagrammasi).
Keling, ularni misollar bilan ko'rib chiqaylik.
1-misol. Alifbodagi ikki so‘zning birikmasini amalga oshiruvchi MT tuzing. Lentadagi so'zlar * belgisi bilan ajratiladi. Dastlabki konfiguratsiya standartdir.
MT buyruqlar tizimi quyidagicha ko'rinadi:
Davlatda bosh bo'sh belgigacha o'ngga o'tadi.
Eng o'ngdagi belgi o'chiriladi.
Agar birinchi so'z bo'sh bo'lsa, yulduzcha o'chiriladi.
O'ng so'z har bir belgi chapga bir pozitsiyaga siljiydi.
Standart yakuniy konfiguratsiyaga o'tish.
Funktsiyalar jadvali
| a | b | * | l | |
| - | ||||
| - | ||||
| - | ||||
| - |
Jadvaldagi chiziqlar l belgisini shtatlarda topib bo'lmasligini bildiradi.
|
|
|||
Yakuniy standart konfiguratsiya.
MT da lug'at funksiyasini hisoblashni quyidagicha tushunamiz. Dastlabki konfiguratsiyadagi lentaga a so'zi yozilsin. Agar qiymat aniqlansa, u holda chekli sonli qadamlar (tsikllar) mashina oxirgi konfiguratsiyaga o'tishi kerak, unda so'z lentada yozilgan. Aks holda, MT cheksiz ishlashi kerak.
MT dan foydalanib, raqamlar ustidagi arifmetik amallarning bajarilishini tavsiflash mumkin. Bunda raqamlar lentada qandaydir sanoq tizimining raqamlaridan tashkil topgan alifbodagi so'zlar sifatida taqdim etiladi va bu alifboga kiritilmagan maxsus belgi bilan ajratiladi, masalan, *. Eng ko'p qo'llaniladigan tizim -1 belgisidan iborat unary tizimdir. Lentadagi X raqami so'z bilan (yoki qisqartirilgan) alifboda yozilgan A=(1).
Agar konfiguratsiyani konfiguratsiyaga moslashtiradigan MT mavjud bo'lsa, raqamli funktsiyani to'g'ri hisoblash mumkin (yoki oddiygina Turing hisoblash mumkin). y, yoki aniqlanmagan bo'lsa, cheksiz ishlaydi.
2-misol. Unar kodda ikkita raqamni qo'shish amali.
Dastlabki konfiguratsiya:
Yakuniy konfiguratsiya: ya'ni. qo'shish aslida raqamni belgilashga to'g'ri keladi b raqamga a. Buning uchun birinchi 1 o'chiriladi va * 1 bilan almashtiriladi.
Biz MT ning tavsifini funktsional jadval shaklida beramiz:
| * | l | ||
| - | |||
| - | |||
| - |
MTni tavsiflashning yuqoridagi usullari amalda faqat oddiy algoritmlar uchun ishlatilishi mumkin, chunki murakkab bo'lganlar uchun tavsif juda og'ir bo'ladi. Xuddi shunday, faqat eng oddiy funksiyalar va superpozitsiya, ibtidoiy rekursiya va minimallashtirish operatorlaridan foydalangan holda rekursiv funktsiyalarni tavsiflash juda mashaqqatli bo'ladi. Demak, funktsiyaning ibtidoiy yoki qisman rekursivligi ibtidoiy yoki qisman rekursivligi isbotlangan boshqa funksiyalar yordamida isbotlanadi.
Xuddi shunday murakkab algoritmlar uchun Tyuring mashinalari mavjud MT yordamida tuzilishi mumkin. Ushbu qurilish MT tarkibi deb ataladi.
Keling, MT tarkibining 4 ta asosiy usulini tavsiflaymiz:
Ketma-ket kompozitsiya (superpozitsiya);
Parallel kompozitsiya;
Tarmoqlanish
Ketma-ket kompozitsiya mashinalar va hisoblash lug'ati funktsiyalari va alifboda A, mashina deb ataladi T, bu funktsiyani hisoblaydi. Ketma-ket kompozitsiya quyidagicha tasvirlangan:
va belgilangan.
Algoritmlarning chiziqli bo'limlarini tasvirlash uchun odatda ketma-ket kompozitsiyadan foydalaniladi.
Mashina yasash imkoniyati haqidagi teoremani isbotlash T, bu ikkita ixtiyoriy mashinaning ketma-ket tarkibi bo'lib, yakuniy holatni dastlabki holat bilan aniqlash orqali amalga oshiriladi.
3-misol. a so‘zini a*a so‘ziga va qo‘shish mashinasiga aylantiruvchi nusxa ko‘chirish mashinasi yordamida unar kodda 2*X ko‘paytirish algoritmini tuzing. Kerakli MT quyidagicha ko'rinadi:
| | | |
|||||||||||||
| | |
||||||||||||||
Parallel kompozitsiya mashinalar va hisoblash lug'at funktsiyalari va alifbolar A Va IN shunga ko'ra, mashina chaqiriladi T, bu lug'at funktsiyasini baholaydi. Bu erda belgi parallel MT tarkibidagi so'zlarni ajratish uchun ishlatiladi.
| |
va belgilanadi: .
Aslida, ikkita MTning parallel tarkibi turli alifbolardagi 2 so'zdan iborat so'zni kirish sifatida qabul qiladi va 2 so'zdan iborat so'zni chiqaradi, ya'ni. bir vaqtning o'zida va mustaqil ishlaydigan ikkita mashinani ifodalaydi.
Parallel kompozitsiyani amalga oshirish uchun ikki qavatli kamarli mashina ishlatiladi. Buning zarurati hisob va vaqt ketma-ket sodir bo'ladi, va, hisoblangan, masalan, birinchi, a ko'proq joy talab va so'z b talon mumkin, deb aslida tufaylidir. Ikki qavatli lenta mashinasi shunday ishlaydi: b so'zi ikkinchi qavatga yoziladi va birinchi qavatda o'chiriladi, birinchi qavatda hisoblab chiqiladi, ikkinchi qavatda hisoblab chiqiladi va keyin birinchi qavatga qayta yoziladi, ehtimol siljish bilan. .
Parallel kompozitsiyani amalga oshirish uchun n ishlatiladigan mashinalar n– pol lentasi.
Ikki qavatli lenta bilan MT buyrug'i quyidagicha yoziladi:, bu erda mos ravishda birinchi va ikkinchi qavatda yozilgan harflar.
4-misol. Ikkilik sanoq sistemasida mashinalar va hisoblash funksiyalarining parallel tarkibini amalga oshirish va a+b unar sistemada.
Kiritilgan so'z quyidagi shaklga ega: .
MT ning buyruqlar tizimi bilan ishlashini tavsiflaymiz:
B so'ziga o'ngga o'ting
b so'zini ikkinchi qavatga qayta yozish
A so‘ziga chapga siljiting
X raqamiga 1 qo'shish.
B so'ziga o'ngga o'ting.
Bir vaqtning o'zida raqamlarni qo'shish bilan 1-qavatga aholini ro'yxatga olish b a Va b.T mos ravishda. Buyruqlar tizimiga jingalak qavs ichidagi buyruqlar qo'shilgan
Butun MTning yakuniy holati.
Shuni ta'kidlash kerakki, barcha holatlarda, algoritm boshida, maxsus qiymatlar uchun manba ma'lumotlarini tekshirishni kiritish kerak (ko'pincha 0); bu talabga rioya qilmaslik tsiklga olib kelishi mumkin.
MT tarkibi murakkab algoritmlarni qurish uchun ishlatilishi mumkin. Savol tug'iladi: har qanday algoritmni MT kompozitsiyasi sifatida amalga oshirish mumkinmi? Bu savolga javob beradi Tyuringning ishi , Cherkov tezisining analogi: har bir algoritm Tyuring mashinalari yordamida amalga oshirilishi mumkin va aksincha, Tyuring mashinasi tomonidan amalga oshirilgan har bir jarayon algoritmdir.
Tyuring tezisi teorema emas, uni isbotlash mumkin emas, chunki unda norasmiy tushuncha mavjud " algoritm" Biroq, ko'p yillik matematik amaliyot bu tezisning ishonchli tasdig'idir: 50 yil davomida Tyuring mashinalari yordamida amalga oshirib bo'lmaydigan intuitiv ma'noda hech qanday algoritm topilmadi.
Ishning maqsadi: Tyuring mashinalari tarkibidan foydalangan holda algoritmlarni yozish bo'yicha amaliy ko'nikmalarga ega bo'lish.
Nazariy ma'lumotlar
MTni tavsiflashning yuqoridagi usullari amalda faqat oddiy algoritmlar uchun ishlatilishi mumkin, aks holda tavsif juda og'ir bo'ladi. Murakkab algoritmlar uchun Tyuring mashinalari allaqachon mavjud elementar MTlar yordamida tuzilishi mumkin va bu konstruktsiya deyiladi. tarkibi MT.
Keling, MT tarkibining 4 ta asosiy usulini tavsiflaymiz:
Ketma-ket kompozitsiya (superpozitsiya);
Parallel kompozitsiya;
Tarmoqlanish
1. Tyuring mashinalarining ketma-ket tarkibi
Ketma-ket kompozitsiya yoki superpozitsiya Tyuring mashinalari va 
Va 
alifboda A, bu mashina deyiladi M, funktsiyani hisoblash 
.
Ketma-ket kompozitsiya quyidagicha tasvirlangan:
va belgilanadi 
yoki 
.
2. Tyuring mashinalarining parallel tarkibi
Parallel kompozitsiya
avtomobillar 
Va 
, lug'at funktsiyalarini hisoblash 
Va 
alifbolarda A Va IN, shunga ko'ra, mashina chaqiriladi M, bu lug'at funktsiyasini baholaydi. Mana bu belgi 
parallel MT tarkibidagi so'zlarni ajratish uchun ishlatiladi.
Parallel kompozitsion MT 
Va 
quyidagicha tasvirlangan:
va belgilanadi: 
.
Aslida, ikkita MTning parallel tarkibi turli alifbolardagi 2 so'zdan iborat so'zni kirish sifatida qabul qiladi va 2 so'zdan iborat so'zni ham chiqaradi, ya'ni. bir vaqtning o'zida va mustaqil ishlaydigan ikkita mashinani ifodalaydi. Parallel kompozitsiyani amalga oshirish uchun ikki qavatli kamarli mashina ishlatiladi.
Ikki qavatli kamar mashinasi quyidagicha ishlaydi:
1) so'z 
lentaning ikkinchi qavatida qayta yozilgan va birinchisida o'chirilgan,
2) hisoblangan 
birinchi qavatda,
3) hisoblangan 
Ikkinchi qavatda
4)
birinchi qavatga qayta yozilgan, ehtimol, siljish bilan.
Ikki qavatli lentali MT buyrug'i quyidagicha yoziladi:
,
Qayerda 
- mos ravishda birinchi va ikkinchi qavatlarda yozilgan xatlar. Keling, so'zlarning uzunligini belgilaylik 
, mos ravishda, 
.
Keling, ikki qavatli lenta bilan Tyuring mashinasining ishlashini namoyish qilaylik. Umuman olganda, so'z uzunligi 
Va 
bir-biriga mos kelmaydi, lekin tasvirning soddaligi uchun biz ularni teng deb hisoblaymiz. Keyin ikki qavatli lenta bilan MT da 1)-4) bandlarini bajarish shu tarzda amalga oshiriladi:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Parallel kompozitsiyani amalga oshirish uchun n Tyuring mashinalari ishlatiladi n– pol lentasi.
3. Tyuring mashinalari kompozitsiyalarida tarmoqlanish yoki shartli o'tish
Tyuring mashinalari berilsa 
Va 
, lug'at funktsiyalarini hisoblash 
Va 
, va mashina 
, ba'zi bir predikatni baholaydi P(
)
qayta tiklash bilan (ya'ni so'zni o'chirmasdan
),
keyin tarmoqlanishni amalga oshirish uchun Tyuring mashinasini qurish mumkin 
, funktsiyani hisoblash:
Tyuring mashinalarining tarkibiy diagrammalarida tarmoqlanishi quyidagicha tasvirlangan:
va belgilanadi 
, Bu yerga 
- mashinaning ishlashi natijasi 
, agar predikat bo'lsa, "1" qiymatlarini olish P(
)=
”rost”
va agar predikat bo'lsa "0" P(
)=
“yolg'on”
,
- kirish so'zini nusxalashni amalga oshiradigan Turing mashinasi 
.
4 . Tyuring mashinalari tarkibidagi sikl
Velosiped tarkibida MT tarmoqlanish bilan bir xil tamoyillarga muvofiq amalga oshiriladi.
"Salom P(
)=
”rost”
, bajarish 
»,
Qayerda
- birinchi ijrodan oldin lentadagi so'z 
va keyingi ijrodan keyin .
Tsiklni tasvirlash uchun biz ba'zi belgilarni kiritamiz, keling:
- predikatni hisoblashni amalga oshiradigan Tyuring mashinasi P(
)
;
-MT, kirish so'zidan nusxa ko'chirishni amalga oshiradi 
;
–MT, tsiklda bajariladi va amalga oshiriladi 
;
–MT, sikldan chiqish va amalga oshirishda bajariladi 
.
Keyin Tyuring mashinalarining tsiklik tarkibini yoki tsiklini quyidagicha tasvirlash mumkin:
Turing mashinasi kompozitsiyalari bilan dasturlash:
1) detallar darajasidagi murakkab algoritmlarning blok-sxemalarini ularning bloklari elementar MT larga mos keladigan qilib qurish;
2) oddiy bloklarni amalga oshiradigan elementar MTlarni qurish;
3) elementar MTlarni MT tarkibiga birlashtirish.
Misol. Amalga oshiruvchi MT kompozitsiyasini yarating 
.
-Kirish so'zidan nusxa ko'chirishni amalga oshiradigan Tyuring mashinasi;
–MT, doimiy nolni o'rnatish funksiyasini amalga oshiradi;
–MT, qayta tiklash bilan hisoblash predikati 
;
– tanlash funksiyasini amalga oshiruvchi MT 
- o'sha argumentdan 
argumentlar;
–MT, argumentlarni qisqartirish funksiyasini amalga oshirish 
birlik kodda 1 ga (eng chap belgi o'chiriladi);
– MT, birlik kodda ikkita raqamni qo'shishni amalga oshiradi.
Shuni ta'kidlash kerakki, har qanday holatda ham, algoritmni bajarish boshida kiritilgan ma'lumotlarning to'g'riligini tekshirish kerak (masalan, bo'linish paytida argumentning 0 ga tengligi).
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 ishlashi natijasi;
T 2 (T 1 (x)) - T 2 mashinasining ishlashi natijasi.
Misol tariqasida ikkita mashinaning tarkibini ko'rib chiqamiz, ularning birinchisi nusxa ko'chirish amalini bajaradi, ikkinchisi esa unar kodda raqamlarni qo'shish operatsiyasini bajaradi. Mashinalarning kombinatsiyasining diagrammasi 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, Tyuring mashinalari uchun ma'lum operatsiyalar to'plamini (masalan, arifmetik operatsiyalar) echish uchun algoritmlarni tuzgandan so'ng, Tyuring mashinalarining kompozitsiyalarini yanada murakkab muammolarni hal qilish uchun tuzish mumkin. Bunday holda, umumiy algoritmni ishlab chiqish uni Tyuring mashinasida bajarish algoritmlari allaqachon ma'lum bo'lgan operatsiyalardan kompilyatsiya qilish bilan bog'liq. Bu yondashuv dasturlashda protsedura va funksiyalardan foydalanishga o'xshaydi.
Biroq, mashina tarkibidan foydalanish elementar amallarni bajarish algoritmlari ma'lum bo'lishini nazarda tutadi, ulardan umumiy algoritm tuziladi. Shuning uchun, o'zboshimchalik bilan muammolarni hal qilishda, bu yondashuv yangi algoritmlarni tuzish va shunga mos ravishda turli boshqaruv bloklari bilan Tyuring mashinalarini ishlab chiqish zaruratini 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 holatlar alifbosi, boshning boshlang'ich holati va mashinaning dastlabki holati ma'lum, shuningdek, mashinaning ishlash jadvali va dastlabki ma'lumotlarga ega lenta. ), keyin barcha ma'lumotlarni o'zgartirish qo'lda bosqichma-bosqich amalga oshirilishi mumkin, bu mashina uchun mo'ljallangan. Aslida, bu holda, Tyuring mashinasining simulyatsiyasi amalga oshiriladi.
Turing mashinasini modellashtirishda bajariladigan operatsiyalarni tahlil qilganda, modellashtirish har bir bosqichda quyidagi harakatlarni takrorlashdan iborat ekanligini aniqlash mumkin:
ÄBosh joylashgan lenta katakchasidagi belgini o'qish.
ÄMashinaning ishlash jadvalida buyruqni qidiring. Qidiruv mashinaning joriy holati va o'qilgan belgining qiymati asosida amalga oshiriladi.
ÄTasmaga yozilishi kerak bo'lgan buyruqdan belgini tanlash va uni yozib olish.
ÄBuyruqdan bosh harakati belgisini tanlang va uni harakatlantiring.
ÄBuyruqdan yangi mashina holatini tanlash va joriy holatni yangisiga o'zgartirish. Shundan so'ng keyingi bosqichga o'tish va ushbu bosqichlarni takrorlash.
|
|
 |
|||||
 |
|||||
1.8-rasm
Ushbu elementar harakatlarning tabiati shundan iboratki, ularning barchasi dastlabki mashinaning ishlashini taqlid qiladigan boshqa Tyuring mashinasi yordamida bajarilishi mumkin. Modellashtirishning mohiyati 1.8-rasmda tushuntirilgan.
Agar T mashinasida ST buyruq tizimi mavjud bo'lsa va X ma'lumoti bo'lgan lentani qayta ishlasa, u holda uning ishlashi o'zining SU buyruq tizimiga ega bo'lgan boshqa U mashinasi tomonidan simulyatsiya qilinishi mumkin. U mashinasining kirishini taqlid qilish uchun siz nafaqat X ma'lumoti bo'lgan lentani topshirishingiz 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 ishlash algoritmiga bog'liq emas. Har qanday boshqa Tyuring ishini simulyatsiya qila oladigan Tyuring mashinasi. mashina 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 operatsiyasi natijalari qayd etiladi.
Tartib zonasi joriy holatni qayd etadi Q t va joriy kirish belgisi X t, ma'lum bir tsiklda ma'lumotlar zonasi katagidan o'qiladi.
Buyruqlar zonasida simulyatsiya qilingan mashinaning buyruqlar tizimi mavjud. Buyruqlar guruhlarga bo'lingan. Birinchi guruhga Q 0 belgisi bilan boshlanadigan buyruqlar, ikkinchisiga Q 1 belgisi va boshqalar kiradi. Har bir guruh ichida buyruqlar X t belgisining qiymati bo'yicha tartiblanadi. Shunday qilib, lentadagi buyruqlar simulyatsiya qilingan mashinaning ishlash jadvalida joylashganidek joylashgan.
Lentadan ma'lumotni o'qish va lentaga yozish uchta bosh yordamida amalga oshiriladi: G d - ma'lumotlar boshi, G r - rejim boshi, G k - buyruq boshi. Har bir bosh kamarning o'z zonasi bo'ylab harakatlanishi mumkin.
UMT ishlay boshlashdan oldin, tegishli ma'lumotlar lentaning har bir zonasida yozilishi kerak. Boshlar har bir zonada chap belgining ustiga o'rnatilishi kerak.
UMT ning ishlashi tsikllarda sodir bo'ladi, har bir tsiklda simulyatsiya qilingan mashinaning bitta buyrug'ining bajarilishi simulyatsiya qilinadi. UMT ning ishlash grafigi 1.10-rasmda keltirilgan.
 |
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 k), (G d), (G r) - boshlardan biri tomonidan o'qilgan ma'lumot;
Q (G k) à (G r) - buyruq boshlig'i tomonidan ma'lumotlarni o'qish va bu ma'lumotlarni yozish
rejim boshi yordamida lenta rejimi zonasiga o'tkaziladi;
Q a yordamchi o'zgaruvchi bo'lib, 1 qiymatini oladi, es-
Gk va Gr 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 bo'ladimi
Q p - buyrug'i qachon bosh bo'lsa 1 qiymatini qabul qiladigan signal
chapga o'tish qo'mondonlik zonasi chegarasidan tashqariga chiqdi;
UMT ning har bir ish siklida quyidagi bosqichlar bajariladi:
buyruq zonasini qidiring;
zonada jamoa qidiryapsiz;
u buyruq bajarilishini simulyatsiya qilish.
Buyruqlar zonasini izlash 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 boshning besh qadami o'ngga amalga oshiriladi (U 0 - U 4 holatlar). Agar Q t va Q i belgilar mos kelsa, buyruq 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 zonasining X t belgisi ustiga, buyruq boshi esa joriy buyruqdagi X i belgisi ustiga joylashtiriladi.
Zonadagi buyruqni qidirish buyruqlar zonasini qidirishga o'xshaydi. Bunday holda, buyruq boshi X t va X i belgilar solishtirilgunga qadar o'ng besh qadamga (U 5 - U 9 holatlari) o'tadi.
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 ma'lumotlar zonasiga o'rniga ma'lumotlar boshi yordamida yoziladi. ilgari o'qilgan belgi X t . Buyruq boshining keyingi bosqichi o'ngga o'tgandan so'ng topilgan buyruqdan ma'lumotlar boshining harakatlanuvchi belgisi (Y d) o'qiladi va ma'lumotlar boshi ushbu belgiga (R, L) mos ravishda harakatlanadi. Uning ostida keyingi qayta ishlangan belgi (X t +1) joylashgan bo'lib, u rejim boshi yordamida keyingi siklni tayyorlash uchun rejim zonasiga yoziladi. Keyinchalik, buyruq va rejim boshlari keyingi holat Q t +1 (holatlar
U 14, U 15). U 16 holatida eritmani tugatish sharti tekshiriladi. Agar keyingi holat belgisi modellashtirilgan mashinaning yakuniy holati belgisiga (Q z) to‘g‘ri kelmasa, u holda masalaning yechimi tugallanmagan va U 17 holatda buyruq boshi o‘zining 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.
Q t va Q z belgilari bir-biriga to‘g‘ri kelganda masalaning yechimi tugaydi va UMT yakuniy U z holatiga o‘tadi.
UMT ning ishlash jarayonini tahlil qilganda, muhim xulosaga kelish mumkinki, UMT ning ishlash algoritmi simulyatsiya qilingan Tyuring mashinasi qanday aniq muammoni hal qilishiga bog'liq emas. Shuning uchun, turli mashinalarni modellashtirishda UMT boshqaruv blokining tuzilishi o'zgarmaydi, ya'ni. hal qilinayotgan vazifalarga bog'liq emas. Shuning uchun ham UMT haqiqatdan ham universal mashina bo'lib, uning yordamida istalgan algoritmni tuzilishini o'zgartirmasdan bajarishingiz mumkin.
Keyingi UMT buyrug'ini tanlash va uni bajarish jarayoni lenta katakchalarini ketma-ket sanab o'tish bilan bog'liq bo'lganligi sababli, UMTda muammolarni hal qilish juda ko'p vaqtni talab qiladi. Shuning uchun Tyuring mashinasi, shu jumladan universal ham hech qachon qurilmagan, ammo unda zamonaviy kompyuterlarning analogini ko'rish qiyin emas. Shunday qilib, UMT buyruq zonasidagi buyruqlar tizimi mashina dasturiga o'xshash bo'lib, Q t va X t belgilar juftligi mashina buyrug'ining manzili rolini o'ynaydi.
Biroq, Tyuring mashinasi algoritmlarni tavsiflash uchun juda qulay vosita bo'lib, algoritmlar nazariyasida keng qo'llaniladi.
Nazorat savollari
ü1.Tyuring mashinalarining tarkibi qanday?
ü2.Tyuring mashinalarining tarkibi nima uchun ishlatiladi?
ü3.Bir Tyuring mashinasi boshqa mashinaning ishini simulyatsiya qila oladimi?
Turing?
ü4.Bu holatda qanday harakatlar bajariladi?
ü5.Universal Tyuring mashinasining tuzilishini tushuntiring?
ü6.UMT lentasi sohalarida qanday ma’lumotlar qayd etilgan?
ü7.Tyuring mashinasining buyruqlar tizimi nima?
ü8.UMT ish sikli qanday bosqichlarni o‘z ichiga oladi?
ü9.“Buyruqlar zonasini qidirish” qadamining mazmunini tushuntiring.
ü10.“Buyruqni bajarish” qadamining mazmunini tushuntiring.
ü11.Axborotni qayta ishlash jarayoni qanday xususiyatlardan foydalanadi
Diagramma grafikga o'xshaydi:
Mashina jadvali qiymati
1-jadval
Tyuring mashinalarida ba'zi operatsiyalar
Turing mashinasining ishlashi to'liq kirish ma'lumotlari va buyruqlar tizimi bilan belgilanadi. Biroq, ma'lum bir mashina muammoni qanday hal qilishini tushunish uchun, qoida tariqasida, mashina uchun berilgan turdagi mazmunli tushuntirishlarga ehtiyoj bor. 
. Ushbu tushuntirishlar ko'pincha blok diagrammalar va ba'zi Tyuring mashinasi operatsiyalari yordamida yanada rasmiy va aniqroq bo'lishi mumkin. Eslatib o'tamiz, funktsiyalar tarkibi 
Va 
funksiya deb ataladi 
, foydalanilganda olinadi 
hisoblash natijasiga 
. Uchun 
bunda aniqlandi 
uchun zarur va yetarlidir 
belgilandi 
, A 
belgilandi 
.
Teorema 1. Agar 
Va 
Turing hisoblash mumkin, keyin ularning tarkibi 
Turing tomonidan ham hisoblash mumkin.
Mayli 
- hisoblash mashinasi 
, A 
- hisoblash mashinasi 
, va mos ravishda ularning holatlari to'plami 
Va 
.
Keling, avtomobilning o'tish sxemasini tuzamiz 
diagrammalardan 
Va 
quyidagicha: biz boshlang'ich tepalikni aniqlaymiz 
mashina diagrammalari 
terminal uchi bilan 
mashina diagrammalari 
(buyruqlar tizimlari uchun bu buyruqlar tizimiga teng 
buyruq tizimiga tayinlangan 
va buning uchun 
jamoalarda 
bilan almashtiring 
). Biz diagramma olamiz ( 
) davlatlar. Dastlabki holat 
e'lon qilamiz 
va yakuniy 
. Belgilanishning soddaligi uchun biz taxmin qilamiz 
Va 
bitta o'zgaruvchining raqamli funktsiyalari.
Mayli 
belgilangan. Keyin 
Va
. Avtomobil 
o'rniga farqi bilan bir xil konfiguratsiyalar ketma-ketligidan o'tadi 
yilda bo'lib o'tadi 
. Ushbu konfiguratsiya mashina uchun standart dastlabki konfiguratsiyadir 
, Shunung uchun 
. Ammo barcha jamoalardan beri 
tarkibida mavjud 
, Bu
va shuning uchun 
. Agar 
demak, aniqlanmagan 
yoki 
to'xtamaydi va shuning uchun mashina 
to'xtamaydi. Shunday qilib, mashina 
hisoblab chiqadi 
.
Mashina shunday qurilgan 
biz uni mashinalar tarkibi deb ataymiz 
Va 
va belgilang 
(yoki 
(
)), shuningdek blok diagrammada tasvirlangan:
Tyuring mashinalarining tarkibi
Mayli 
,
,
- bir xil tashqi alifboga ega uchta Tyuring mashinasi 
, ichki davlat alifbolari bilan 
,
,
va dasturlar 
,
,
mos ravishda.
Tarkibi
avtomobillar 
Va 
chaqirdi mashinaT
, uning dasturi to'plamlar birlashmasi 
Va
, Qayerda 
dan olingan buyruqlar to'plamini bildiradi 
hammasini almashtirish 
yoqilgan 
.
Tyuring mashinalaridan tarmoqlanish
Tarmoqli mashinalar
,
,
tomonidan 
, ramziy ma'noda
chaqirdi mashinaT
, uning dasturi quyidagicha olinadi: dan 
jamoalar bundan mustasno 
Va 
Uchun 
, natijada olingan to'plam chaqiriladi 
; Keyin.
Universal Tyuring mashinasi
Turing mashinasining buyruqlar tizimi ma'lum bir qurilmaning ishlashini tavsifi sifatida ham, dastur sifatida ham talqin qilinishi mumkin, ya'ni. aniq natijaga olib keladigan ko'rsatmalar to'plami. Misollarni tahlil qilishda ikkinchi talqin beixtiyor qabul qilinadi, ya'ni. biz har qanday Tyuring mashinasining ishini takrorlay oladigan mexanizm sifatida harakat qilamiz. Hamma buni xuddi shunday qilishiga ishonch (agar ular xato qilmasa, aytmoqchi, bu Tyuring mashinasi ishlaganda ham taxmin qilinadi) bu tyuring ishini takrorlash algoritmining mavjudligiga ishonchdir. ma'lum bir dasturga muvofiq mashina, ya'ni. buyruq tizimi. Darhaqiqat, bunday algoritmning og'zaki tavsifini berish qiyin emas. Uning asosiy harakati tsiklik ravishda takrorlanadi va quyidagilardan iborat: "Joriy konfiguratsiya uchun 
buyruqlar tizimida chap tomoni bilan buyruqni toping 
. Agar ushbu buyruqning o'ng tomoni forma bo'lsa 
, keyin joriy konfiguratsiyada almashtiring 
yoqilgan 
(konfiguratsiya paydo bo'ladi 
); agar o'ng tomonda shakl bo'lsa 
, keyin almashtiring 
yoqilgan 
. Algoritmning og'zaki tavsifi noto'g'ri bo'lishi mumkin va uni rasmiylashtirish kerak. Hozirgi vaqtda Tyuring mashinasi algoritm tushunchasini shunday rasmiylashtirish sifatida muhokama qilinayotganligi sababli, tasvirlangan takror ishlab chiqarish algoritmini amalga oshiruvchi Tyuring mashinasini qurish muammosi qo'yilishi tabiiy. Bitta o'zgaruvchining funktsiyalarini hisoblaydigan Tyuring mashinalari uchun bu muammoning formulasi quyidagicha: Tyuring mashinasini qurish 
, har qanday mashina uchun ikkita o'zgaruvchining funktsiyasini hisoblash 
buyruq tizimi bilan 
, Agar 
belgilangan (ya'ni, agar mashina 
dastlabki ma'lumotlarda to'xtaydi 
) Va 
to'xtamaydi, agar 
to'xtamaydi. Biz ushbu xususiyatga ega bo'lgan har qanday mashinani chaqiramiz universal Tyuring mashinasi. Ushbu formulani har qanday sonli o'zgaruvchilarga umumlashtirish qiyin emas.
Universal mashinani qurishda paydo bo'ladigan birinchi muammo 
, bunga sabab bo'ladi 
boshqa har qanday Turing mashinasi kabi, sobit alifboga ega bo'lishi kerak 
va qat'iy holatlar to'plami 
. Shuning uchun, buyruq tizimi 
va ixtiyoriy mashinaning dastlabki ma'lumotlari 
uni faqat mashina kamariga o'tkaza olmaysiz 
(har doim mashina bor 
, alifbolar 
Va 
bu kuch jihatidan ustundir 
Va 
yoki oddiygina u bilan mos kelmaydi).
Yechim belgilarni olishdir 
Va 
alifbodagi belgilar bilan kodlangan 
. Mayli 
,
. Biz har doim buni taxmin qilamiz 
Va 
(bu ikki belgi har doim raqamlar bilan ishlaydigan har qanday mashinaning alifbosida bo'ladi). Keling, kodlarni belgilaylik 
Va 
orqali 
Va 
va ularni quyidagicha belgilang 
; boshqa hech kim uchun 
; yakuniy holat uchun 
, Agar 
. Kod 
bu mashina uchun 
har doim uzunlikka ega (format) 
, va kod 
- format 
. Belgilar 
,
kiraylik 
, ya'ni. 
,
,
. Belgilar kodi 
, bu so'zni tashkil etuvchi belgilarning kodlari bilan tuzilgan, biz belgilaymiz 
. Shunday qilib, universal mashina muammosini shakllantirish yakuniy takomillashtirildi 
har qanday mashina uchun bu haqiqatga to'g'ri keladi 
va so'zlar 
alifbo 
.
Universal Tyuring mashinasining mavjudligi ko'rsatmalar tizimi ekanligini anglatadi 
har qanday mashina 
ikki shaklda talqin qilinishi mumkin: yoki asl qurilmaning ishlashining tavsifi sifatida 
, yoki universal mashina uchun dastur sifatida 
. Boshqarish tizimini loyihalashtirgan zamonaviy muhandis uchun bu holat tabiiydir. U yaxshi biladiki, har qanday boshqarish algoritmini apparatda - tegishli sxemani qurish orqali yoki dasturiy ta'minotda - universal boshqaruvchi kompyuter dasturini yozish orqali amalga oshirish mumkin.
Ammo shuni tushunish kerakki, universal algoritmik qurilma g'oyasi uni amalga oshirishning zamonaviy texnik vositalarini (elektronika, qattiq jismlar fizikasi va boshqalar) ishlab chiqish bilan mutlaqo bog'liq emas va texnik emas, balki matematik faktdir. , texnik vositalardan mustaqil bo'lgan mavhum matematik atamalar bilan tasvirlangan va bundan tashqari, juda oz sonli juda elementar boshlang'ich tushunchalarga asoslangan. Algoritmlar nazariyasi bo'yicha fundamental ishlar (xususan, Tyuring ishi) 30-yillarda, zamonaviy kompyuterlar yaratilgunga qadar paydo bo'lganligi xarakterlidir.
Ushbu ikki tomonlama talqin mavhum darajada ikkita muhandislikni amalga oshirish variantlarining asosiy ijobiy va salbiy tomonlarini saqlaydi. Maxsus mashina 
ancha tez ishlaydi; bundan tashqari, mashinaning boshqaruv moslamasi 
juda og'ir (ya'ni holatlar va buyruqlar soni ko'p). Biroq, uning qiymati doimiy bo'lib, tuzilganidan keyin o'zboshimchalik bilan katta algoritmlarni amalga oshirish uchun mos keladi. Kerakli bo'lgan narsa - bu nazorat moslamasidan ko'ra tabiiy ravishda arzonroq va sodda qurilgan deb hisoblangan katta hajmli lenta. Bundan tashqari, algoritmni o'zgartirganda, siz yangi qurilmalarni qurishingiz shart emas, faqat yangi dastur yozishingiz kerak.