Tyuring mashinasining ishlashi

3. Velosipedda harakatlanish.
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 mashinaning dasturidan q i a j ®q 1 a t r, rn(L,R,L), t=0,1,2,...p buyrug‘ini q 1 belgisi bilan almashtirib olinadi. q lar natijada e.
2.4 Tyuring mashinasi variantlari
Turing mashinasi modeli kengaytmalarga ruxsat beradi. Tyuring mashinalarini ixtiyoriy sonli lentalar va turli cheklovlarga ega ko'p o'lchovli lentalarni ko'rib chiqish mumkin. Biroq, bu mashinalarning barchasi Tyuring tugallangan va oddiy Tyuring mashinasi tomonidan modellashtirilgan.
Bunday ekvivalentlikka misol sifatida har qanday MTni yarim cheksiz lentada ishlaydigan MT ga qisqartirishni ko'rib chiqing.
Teorema: Har qanday Tyuring mashinasi uchun yarim cheksiz lentada ishlaydigan ekvivalent Tyuring mashinasi mavjud.
Isbot:
Yu. G. Karpovning isbotini ko'rib chiqaylik. Bu teoremaning isboti konstruktivdir, ya'ni biz algoritmni beramiz, uning yordamida har qanday Tyuring mashinasi uchun xossasi e'lon qilingan ekvivalent Tyuring mashinasini qurish mumkin. Birinchidan, biz MT ishchi lentasining hujayralarini o'zboshimchalik bilan raqamlaymiz, ya'ni lentadagi ma'lumotlarning yangi joylashishini aniqlaymiz:
1-rasm.
Keyin biz hujayralarni qayta raqamlaymiz va "*" belgisi MT lug'atida mavjud emas deb taxmin qilamiz:

1-rasm.
2.5 Turingning hisoblanishi va qaror qabul qilinishi
Rekursiv funksiyalar, Tyuring mashinalari yoki oddiy Markov algoritmlari yordamida hisoblanuvchi funksiyalar sinflari mos kelishi yuqorida isbotlangan. Bu esa “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 bosh harakati yordamida protokol bilan belgilanadi. Oddiy Markov algoritmi uchun bunday ob'ektlar so'zlar yoki belgilar ketma-ketligi bo'lib, hisoblash jarayoni almashtirish qoidalari yoki asl belgilar ketma-ketligi tarkibi va tuzilishini kerakli natijaga o'zgartiradigan mahsulotlar bilan belgilanadi.
Arifmetik (sonli) funksiya deb diapazoni N to‘plamning kichik to‘plami, aniqlanish sohasi N to‘plamning elementi bo‘lgan funksiyaga aytiladi.
Algoritmik muammolar uchun x 1 , x 2 , …, argumentlarning butun qiymatlariga qarab f(x 1 , x 2 , …, x n) raqamli funktsiyani hisoblash algoritmini topish kerak bo'lganda odatiy holat. x n.
Agar funktsiya qiymatini hisoblash uchun uning argumentlarining har qanday qiymatlari to'plamiga ruxsat beruvchi algoritm mavjud bo'lsa (yoki funktsiya ushbu to'plamda aniqlanmaganligini ko'rsatsa) f:N n →N funktsiyasini hisoblash mumkin deb ataymiz. Hisoblash funksiyasining ta'rifi algoritmning intuitiv kontseptsiyasidan foydalanganligi sababli, "hisoblash funksiyasi" atamasi o'rniga "intuitiv hisoblash funktsiyasi" atamasi ko'pincha ishlatiladi. Shunday qilib, agar ushbu masalaga mos keladigan arifmetik funktsiya intuitiv ravishda hisoblansa, ommaviy muammoning yechimi bor.
Agar argumentlarning k 1 , k 2 , …, k n berilgan qiymatlari uchun f(k 1) funksiyaning qiymatini topish mumkin bo‘lsa, f(x 1 , x 2 , …, x n) funksiya samarali hisoblangan deb ataladi. , k 2 , …,k n) ba'zi mavjud mexanik protsedura (algoritm) yordamida.
Algoritm tushunchasiga aniqlik kiritish o‘rniga, “hisoblash funksiyasi” tushunchasini takomillashtirishni ko‘rib chiqish mumkin. Odatda, ular quyidagi tarzda harakat qilishadi:
1. Aniq belgilangan funksiyalar sinfi kiritiladi.
2. Bu sinfdagi barcha funksiyalar hisoblash mumkinligiga ishonch hosil qiling.
3. Hisoblash funksiyalari sinfi kiritilgan funksiyalar sinfi bilan mos keladi degan gipotezani (tezisni) qabul qiling.
Funktsiyani hisoblaydigan algoritm mavjud bo'lsa, uni hisoblash mumkin deb ataladi. "Hisoblash qobiliyati" algoritmlar nazariyasining asosiy tushunchalaridan biri bo'lib, hisoblangan 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, u holda ularni Tyuring mashinalarini qurish asosida yechish kerak, ya'ni algoritmning formallashtirilgan tushunchasi yetarli. Bundan tashqari, algoritmik masalalarda gap ko'pincha algoritmni qurish haqida emas, balki maxsus usulda tuzilgan ba'zi funktsiyalarni hisoblash mumkinligi haqida gap boradi.
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 mahalliy funktsiya f(x1 , x2 , …, xn) agar uni quyidagi ma'noda hisoblaydigan M mashinasi mavjud bo'lsa, Turing hisoblash mumkin deb ataladi: 1. Agar argument qiymatlari to'plami bo'lsa. f funktsiyaning ta'rif sohasiga tegishli bo'lsa, keyin M mashinasi 0 |x1+1 0 |x2+1 … 0 |xn q1 | konfiguratsiyasida ish boshlaydi, bu erda |x = ||… | (x marta) , va eng o'ngdagi belgi qabul qilinadi, to'xtaydi va 0|yq0 | konfiguratsiyasi bilan tugaydi, bu erda y = f(x1 , x2 , …, xn). 2. Argument qiymatlari to'plami bo'lsa f funksiyani aniqlash sohasiga tegishli emas, u holda M mashinasi dastlabki konfiguratsiyada ishlay boshlaydi, cheksiz ishlaydi, ya'ni yakuniy holatga kelmaydi. Turing mashinasi - bu algoritmning aniq rasmiy ta'rifi. Ushbu kontseptsiyadan foydalanib, algoritmik masalalarning echilishi yoki hal qilinmasligini isbotlash mumkin. Agar masalalarning bir sinfiga mansub masalani yechish uchun hisoblash algoritmi topilsa, u holda bu masala algoritmik echiladigan masala deyiladi. Boshqacha qilib aytganda, hisoblashning hisoblanishi yoki samaradorligining majburiy sharti uning algoritmik echilishidir. Shu ma’noda “hal qilish imkoniyati” tushunchasi ham algoritmlar nazariyasida asosiy tushuncha hisoblanadi. Uch turdagi modellarni tahlil qilish shuni ko'rsatadiki, diskretlik, determinizm, ommaviy xarakter va samaradorlikning asosiy xususiyatlari turli tavsiflash usullari uchun o'zgarishsiz qoladi: Diskretlik xossasi: algoritm bosqichma-bosqich bajariladigan alohida elementar harakatlardan iborat; algoritmik jarayonni tashkil etuvchi elementar qadamlar to'plami chekli va sanab o'tilgandir. Determinizm xossasi: har bir bosqichdan keyin algoritmik jarayonning keyingi bosqichlarini qanday va qanday ketma-ketlikda bajarish kerakligi aniq ko'rsatib beriladi. Ommaviy belgilar xususiyati: algoritmdan foydalanish ma'lum turdagi algoritmik ob'ektlar to'plami va berilgan muammolar sinfi uchun maqbuldir. Samaradorlik xususiyati: algoritmik jarayonni to'xtatish istalgan natijani ko'rsatadigan cheklangan miqdordagi qadamlardan so'ng majburiydir. Biroq, tezisni isbotlab bo'lmaydi, chunki u Turingning hisoblash qobiliyatining aniq tushunchasi bilan intuitiv hisoblab chiqiladigan funktsiyaning noto'g'ri tushunchasi bilan bog'liq.