|
3. Loopning ishlashi.
M alifbosi A «(a 0, a 1, ..., p) va Q« (q 0, q 1, ..., q n) holatlar to'plami bo'lgan Tyuring mashinasi bo'lsin.
Ta'rif.
Loop operatsiyasining natijasi - Tyuring mashinasi (i = 0,2,3, ..., n; j = 0,1,2, ..., p; s = 0,2,3, bilan belgilanadi). .., n)
uning dasturi q mashina dasturidan olingan M qiaj ®q 1 atr, rÎ (L, R, L), t = 0,1,2, ... p, q belgisi 1 q s belgisi bilan.
2 .4 Tyuring mashinasining variantlari
Tyuring mashinasining modeli kengaytirilishi mumkin. Biz tasodifiy sonli tasmali va har xil cheklovlarga ega ko'p o'lchovli lentali Tyuring mashinalarini ko'rib chiqishimiz mumkin. Biroq, bu mashinalarning barchasi Tyuringda to'liq va an'anaviy Tyuring mashinasi tomonidan modellashtirilgan.
Bunday ekvivalentlikka misol sifatida, har qanday MTni yarim cheksiz lentada ishlaydigan MT ga kamaytirishni ko'rib chiqing.
Teorema: Har qanday Tyuring mashinasi uchun yarim cheksiz lentada ishlaydigan ekvivalent Tyuring mashinasi mavjud.
Isbot:
Yu G. G. Karpovning dalilini ko'rib chiqing. Bu teoremaning isboti konstruktivdir, ya'ni har qanday Tyuring mashinasi uchun e'lon qilingan xususiyatga ega ekvivalent Tyuring mashinasini tuzish algoritmini beramiz. Birinchidan, biz MT ishchi tasmasi hujayralarini o'zboshimchalik bilan raqamlaymiz, ya'ni lentadagi ma'lumotlarning yangi o'rnini aniqlaymiz:
1 -rasm.
Keyin biz hujayralarni qayta raqamlaymiz va "*" belgisi MT lug'atida yo'q deb taxmin qilamiz:
1 -rasm.
2.5 Tyuring hisoblanishi va aniqligi
Rekursiv funktsiyalar, Tyuring mashinalari yoki oddiy Markov algoritmlari yordamida hisoblanadigan funktsiyalar sinflari bir -biriga to'g'ri kelishi yuqorida isbotlangan. Bu bizga "hisoblash algoritmi" tushunchasini tavsiflash usuliga o'zgarmasligini ko'rib chiqishga imkon beradi. Farqlar faqat algoritmik ob'ektlarni ishlatishda kuzatiladi. Agar rekursiv funktsiyalar uchun ob'ektlar raqamlar va raqamli funktsiyalar bo'lsa va hisoblash jarayoni superpozitsiya, rekursiya, minimallashtirish va takrorlash operatorlari tomonidan aniqlangan bo'lsa, Tyuring mashinalari uchun bunday ob'ektlar tashqi va ichki xotira alifbosining ramzi hisoblanadi. hisoblash jarayoni chiqish, o'tish va boshni harakatlantirish protokoli bilan belgilanadi. Oddiy Markov algoritmi uchun bunday ob'ektlar so'zlar yoki belgilar ketma -ketligi bo'lib, hisoblash jarayoni dastlabki belgilar ketma -ketligining tarkibi va tuzilishini kerakli natijaga o'zgartiradigan almashtirish qoidalari yoki ishlab chiqarish bilan belgilanadi.
Arifmetik (raqamli) funktsiya - bu qiymatlar diapazoni N to'plamining kichik to'plami, aniqlanish diapazoni esa N to'plamining elementi.
Algoritmik muammolar uchun x 1, x 2 argumentlarining butun soniga qarab f (x 1, x 2,…, xn) sonli funktsiyani hisoblash algoritmini topish kerak bo'lgan odatiy holat. …, X n.
F: N n → N funktsiyasi, agar uning argumentlarining har qanday qiymatlari funktsiyasi qiymatini hisoblashga imkon beradigan algoritm mavjud bo'lsa (yoki bu funktsiya bu to'plamda aniqlanmaganligini bildirsa), hisoblanadigan deb ataladi. Hisoblanadigan funktsiya ta'rifida algoritmning intuitiv kontseptsiyasi ishlatilganligi sababli, "hisoblash funktsiyasi" atamasi o'rniga "intuitiv hisoblanadigan funktsiya" atamasi tez -tez ishlatiladi. Shunday qilib, agar massaga to'g'ri keladigan arifmetik funktsiya intuitiv tarzda hisoblansa, ommaviy masalaning echimi bor.
F (x 1, x 2,…, xn) funktsiyani samarali hisoblangan deyiladi, agar berilgan qiymatlar k 1, k 2,…, kn argumentlar uchun f (k 1, k 2,…, kn) ba'zi mavjud mexanik protsedura (algoritm) yordamida.
Algoritm kontseptsiyasini aniqlashtirishning o'rniga, "hisoblanadigan funktsiya" tushunchasini takomillashtirishni ko'rib chiqish mumkin. Odatda, ular quyidagi sxema bo'yicha harakat qilishadi:
1. Aniq belgilangan funktsiyalar sinfini joriy etish.
2. Bu sinfdagi barcha funktsiyalar hisob -kitob qilinishiga ishonch hosil qiling.
3. Hisoblanadigan funktsiyalar sinfi joriy qilingan funktsiyalar sinfiga to'g'ri kelishi haqidagi farazni (tezisni) qabul qiling.
Agar funktsiyani hisoblash algoritmi mavjud bo'lsa, uni hisoblash mumkin deb atashadi. "Hisoblash qobiliyati" algoritmlar nazariyasining asosiy tushunchalaridan biri bo'lib, hisoblangan funktsiya va algoritmga o'zgarmaydi. Hisoblanadigan funktsiya va algoritm o'rtasidagi farq - bu funktsiyani tavsiflash va uning qiymatlarini mustaqil argumentlar uchun hisoblash usuli o'rtasidagi farq.
Tyuring dissertatsiyasi. Har qanday intuitiv algoritm Tyuring mashinasi yordamida amalga oshirilishi mumkin.
Tyuring tezisidan kelib chiqadiki, agar algoritmik muammolar yuzaga kelsa, ularni Tyuring mashinalari, ya'ni algoritmning rasmiylashtirilgan kontseptsiyasi asosida hal qilish kerak. Bundan tashqari, algoritmik masalalarda ko'pincha algoritmni qurish haqida emas, balki ba'zi maxsus qurilgan funktsiyalarni hisoblash haqida gap boradi.
Shuni ta'kidlash kerakki, bu holatlarda alfavitdan foydalanish kifoya (0, |), bu erda 0 bo'sh belgidir. Masalan, bu alifbodagi 0 ni o'z ichiga olgan natural sonlar quyidagicha kodlangan: 0 - | 1 - ||; 2 -
N - || ... | (n + 1 marta). Qisman sonli n - lokal funktsiya f (x1, x2, ..., xn) Turing hisoblanadigan deb nomlanadi, agar uni quyidagi ma'noda hisoblaydigan M mashinasi bo'lsa: 1. Agar argument qiymatlari to'plami 0 | x1 + 1 0 | x2 + 1 ... 0 | xn q1 | konfiguratsiyasida ish boshlaydigan f, keyin M mashinasining ta'rifi sohasiga tegishli, bu erda | x = || ... | (x marta) va eng o'ngdagi belgi seziladi, to'xtaydi, 0 | yq0 | konfiguratsiyasida ishni tugatadi, bu erda y = f (x1, x2,…, xn). 2. Agar argument qiymatlari to'plami f funktsiyasining ta'rifi sohasiga tegishli emas, keyin M konfiguratsiyasida ishni boshlagan M mashinasi muddatsiz ishlaydi, ya'ni oxirgi holatga kelmaydi. Tyuring mashinasi - bu algoritmning aniq rasmiy ta'rifi. Ushbu kontseptsiyadan foydalanib, algoritmik masalalarning hal qilinishi yoki hal qilinmasligini isbotlash mumkin. Agar hisob -kitoblar algoritmi bitta masalalar sinfiga mansub masalani echish uchun topilsa, u holda bu masala algoritmik echiladigan masala sifatida aytiladi. Boshqacha qilib aytganda, hisoblashning samaradorligi yoki hisoblanishining zaruriy sharti uning algoritmik echimliligi hisoblanadi. Shu ma'noda "aniqlik" tushunchasi ham algoritmlar nazariyasidagi asosiy tushuncha hisoblanadi. Uch turdagi modellar tahlili shuni ko'rsatadiki, diskretlik, determinizm, massa xarakteri va samaradorlikning asosiy xossalari har xil tasvirlash usullari uchun o'zgarishsiz qoladi: Diskretlik xususiyati: algoritm bosqichma -bosqich bajariladigan individual elementar harakatlardan iborat; algoritmik jarayonni tashkil etuvchi elementar qadamlar majmui, albatta, sanaladi. Determinizm xususiyati: har bir qadamdan so'ng, algoritmik jarayonning keyingi bosqichlarini qanday va qanday ketma -ketlikda bajarish kerakligi aniq ko'rsatiladi. Ommaviy xarakterli xususiyat: algoritmdan ma'lum turdagi va berilgan toifadagi algoritmik ob'ektlar majmuasi uchun ruxsat etiladi. Samaradorlik xususiyati: algoritmik jarayonni to'xtatish kerakli natijani ko'rsatuvchi sonli qadamlardan so'ng talab qilinadi. Biroq, tezisni isbotlab bo'lmaydi, chunki u Tyuring hisoblanishi aniq tushunchasi bilan, intuitiv ravishda hisoblanadigan funktsiyaning noaniq tushunchasi bilan bog'liq.
Do'stlaringiz bilan baham: |
