uy » Har xil

Tyuring nazariyasi. Tyuring mashinalari

1920-yillardan keyingi ifoda Hisoblash mashinasi ish bajargan har qanday mashinani bildiradi inson kompyuteri ayniqsa Cherch-Turing tezisining samarali usullariga muvofiq ishlab chiqilganlarga. Bu tezis quyidagicha tuzilgan: "Har qanday algoritm mos keladigan Tyuring mashinasi yoki qisman rekursiv ta'rif shaklida ko'rsatilishi mumkin va hisoblanadigan funktsiyalar klassi qisman rekursiv funktsiyalar sinfiga va Tyuring mashinalarida hisoblanadigan funktsiyalar sinfiga to'g'ri keladi. . " Boshqacha qilib aytganda, Cherch-Turing tezisi elektron kompyuterlar kabi mexanik hisoblash qurilmalarining tabiati haqidagi faraz sifatida ta'riflanadi. Mumkin bo'lgan har qanday hisob -kitobni kompyuterda bajarish mumkin, agar etarli vaqt va saqlash joyi bo'lsa.

Cheksizlik bilan hisoblash mexanizmlari analog tip sifatida tanildi. Bunday mexanizmlardagi qiymatlar uzluksiz sonli qiymatlar bilan ifodalangan, masalan, milning burilish burchagi yoki elektr potentsialidagi farq.

Analog mashinalardan farqli o'laroq, raqamli mashinalar raqamli holatni ko'rsatish va har bir raqamni alohida saqlash qobiliyatiga ega edi. Raqamli mashinalarda RAM qurilmasi ixtiro qilinishidan oldin turli xil protsessorlar yoki o'rni ishlatilgan.

Ism Hisoblash mashinasi 40 -yillardan boshlab, u kontseptsiya bilan almashtirila boshladi kompyuter... Bu kompyuterlar ilgari kotiblar qilgan hisob -kitoblarni bajara olishgan. Qadriyatlar jismoniy xususiyatlarga bog'liq bo'lmagan paytdan boshlab (analog mashinalarda bo'lgani kabi), raqamli uskunalarga asoslangan mantiqiy kompyuter tasvirlab berilishi mumkin bo'lgan hamma narsani qila oldi. faqat mexanik tizim .

Tyuring mashinalari matematik tarzda hisoblash kuchiga cheklovlar berilgan holda nimani aniqlash mumkinligini aniqlash uchun mo'ljallangan. Agar Tyuring mashinasi topshiriqni bajara olsa, u holda vazifa Tyuring hisoblanadigan hisoblanadi. Turing asosan nimani hisoblash mumkinligini aniqlaydigan mashinani loyihalashga e'tibor qaratdi. Tyuring xulosaga keldi, agar sonning taxminiyligini hisoblaydigan Tyuring mashinasi bo'lsa, bu qiymat sanaladi. Bundan tashqari, Tyuring mashinasi AND, OR, XOR, NOT va If-Then-Else kabi mantiqiy operatorlarni talqin qilishi mumkin.

Biz har xil murakkablikdagi muammolarni hal qilamiz: kundalik, matematik va boshqalar. Ba'zilarini hal qilish oson, ba'zilariga ko'p o'ylashimiz kerak, ba'zilariga hech qachon yechim topa olmaymiz.

Umumiy holda, muammoni hal qilish yo'lini (agar mavjud bo'lsa) cheklangan sonli elementar harakatlar yordamida tasvirlash mumkin.

Masalan, kvadrat tenglamani yechish:

  1. Tenglamani kanonik shaklga keltiring \ (a x ^ 2 + b x + c = 0 \)
  2. Agar \ (a = 0 \) bo'lsa, u holda \ (x = \ frac (-c) (b) \) eritmasi bo'lgan chiziqli tenglama. Muammo hal qilindi. Aks holda, 3 -bosqichga o'ting.
  3. Diskriminantni hisoblang \ (D = b ^ 2-4 a c \)
  4. Tenglama yechimlarini hisoblang \ (x_ (1,2) = \ frac (-b \ pm \ sqrt (D)) (2 a) \)... Muammo hal qilindi.

Siz algoritmning quyidagi intuitiv kontseptsiyasini kiritishingiz mumkin:

Algoritm - bu har qanday boshlang'ich ma'lumotlar to'plami uchun cheklangan miqdordagi amalda muammoni hal qilish natijasiga erishish uchun bajaruvchining harakatlari tartibini tavsiflovchi ko'rsatmalar to'plami.

Bu, albatta, qat'iy ta'rif emas, lekin u algoritm tushunchasining mohiyatini tavsiflaydi.

Algoritmlar ma'lum bir ma'lumot asosida tuziladi ijrochi, va shunga mos ravishda, ijrochi tushunadigan tilda tuzilishi kerak.

Algoritmni bajaruvchisi shaxs bo'lishi mumkin, yoki u kompyuter yoki boshqa mashina bo'lishi mumkin, masalan, dastgoh.

Algoritmlarning quyidagi xususiyatlari ajratilgan:

Algoritmning diskretligi alohida, aniq belgilangan qadamlar (harakatlar) ning ma'lum ketma -ketligi bo'lishi kerak. Bu harakatlarning har biri o'z vaqtida cheklangan bo'lishi kerak. Algoritmning har bir bosqichida determinizm, keyingi bosqich tizimning hozirgi holati bilan aniqlanadi. Natijada, bir xil boshlang'ich ma'lumotlarga ko'ra, algoritm har safar bir xil natijalarni beradi, u necha marta bajarilishidan qat'iy nazar. Tushunarli Algoritm ijrochiga tushunarli tilda tuzilishi kerak. Kompyuter haqida gap ketganda, algoritm faqat kompyuterga ma'lum bo'lgan va natijasi qat'iy belgilangan ko'rsatmalardan foydalanishi kerak. Algoritmning aniqligi cheklangan sonli bosqichlarda bajarilishi kerak. Algoritmning massivligi kirish ma'lumotlarining har xil to'plamlari uchun qo'llanilishi kerak. Boshqacha aytganda, algoritm echishga mos bo'lishi kerak sinf vazifalar. Kvadratik misolga qaytsak, algoritm yechishga mos keladi hammasidan bitta yoki bir nechta emas, balki kvadrat tenglamalar. Algoritmning samaradorligi ma'lum bir natija bilan tugashi kerak. Aytaylik, muammoni hal qilish orqali yoki echim yo'qligini bilib. Agar algoritm natijaga olib kelmasa, nima uchun umuman kerakligi aniq emas.

Muammoni hal qilishning hamma usuli ham algoritm emas. Aytaylik, algoritm hech qanday tanlovni nazarda tutmaydi. Misol uchun, ko'pchilik retseptlar algoritm emas, chunki ular "ta'mga tuz" kabi iboralarni ishlatadi. Natijada determinizm talabi buziladi.

Har bir muammoni hal qilish uchun emas, balki echim algoritmi ham mavjud. Masalan, tasvirni tanib olish muammosi haligacha hal qilinmagan va aniq algoritm ishlatilmagan. Biroq, neyron tarmoqlardan foydalanish juda yaxshi natijalar beradi.

Odatda, algoritm uchun to'plamlar mavjud joiz kirish ma'lumotlari. Kechki ovqat tayyorlashda, yoki aksincha, tenglamalarni echish algoritmini qo'llashga urinish g'alati bo'lardi.

Bundan tashqari, ijrochining mumkin bo'lgan harakatlari ham cheklangan, chunki agar biron -bir harakatga ruxsat berilgan bo'lsa, unda ular orasida "qabul qilib bo'lmaydigan" ham bo'lishi kerak edi.

Algoritmning qattiq ta'rifi

Yuqoridagi algoritmning ta'rifi qat'iy emas. Bu ba'zi qiyinchiliklarni keltirib chiqaradi. Xususan, bunday ta'rif bilan, berilgan muammolar sinfini algoritm yordamida hal qilinishini qat'iy isbotlash mumkin emas.

Ma'lum bo'lishicha, sinf bor algoritmik hal qilinmaydigan muammolar- echim algoritmini tuzish mumkin bo'lmagan muammolar. Ammo algoritmik noaniqlikni qat'iy isbotlash uchun avval siz algoritmning aniq ta'rifiga ega bo'lishingiz kerak.

XX asrning 20-30-yillarida turli matematiklar algoritmni aniq belgilash muammosi ustida ishladilar, xususan, Alan Tyuring, Emil Leon Post, Andrey Andreevich Markov, Andrey Nikolaevich Kolmogorov, Alonzo Cherkov va boshqalar. Ularning ishi oxir -oqibat algoritmlar nazariyasi, hisob -kitoblar nazariyasi va hisob -kitoblarga har xil yondashuvlar va aytmoqchi, umuman dasturlashning paydo bo'lishi va rivojlanishiga olib keldi. Algoritmning har xil yo'llar bilan kiritilgan, lekin bir -biriga ekvivalent bo'lgan bir qancha qat'iy ta'riflari paydo bo'lishi ularning ish natijalaridan biri bo'ldi.

Biz Turing ta'rifiga batafsil to'xtalamiz va Post, Cherkov va Markovning ekvivalent ta'riflarini yuzaki tahlil qilamiz.

Tyuring mashinasi

Algoritmning rasmiy ta'rifini kiritish uchun Tyuring Turing hisoblash mashinasi yoki oddiy Tyuring mashinasi deb nomlangan mavhum hisoblash mashinasini o'ylab topdi.

Alan Turing (1912-1954)

Ingliz matematik, mantiqchi, kriptograf, ehtimol dunyodagi birinchi "xaker", informatika va sun'iy intellekt nazariyasining boshida edi. U Ikkinchi Jahon urushida ittifoqchi kuchlarning g'alabasiga katta hissa qo'shdi.

Tyuring mashinasi uchun kirish ma'lumotlari sozlar malumot yordamida tuzilgan alifbo, ya'ni to'plam belgilar.

Tyuring mashinasining ishining natijasi ham so'zlardir.

Algoritm qo'llaniladigan so'z deyiladi kiritish... Ishdan kelib chiqqan so'z hafta oxiri.

Algoritm qo'llaniladigan so'zlar to'plami deyiladi algoritm doirasi.

Qat'iy aytganda, har qanday ob'ektni alifbo bilan tuzilgan so'zlar shaklida ko'rsatish mumkinligini isbotlash mumkin emas - buning uchun bizga ob'ektning aniq ta'rifi kerak bo'ladi. Biroq, siz ob'ektlarda ishlaydigan tasodifiy algoritmni algoritmning mohiyatini o'zgartirmasdan so'zlar ustida ishlashini o'zgartirishingiz mumkinligini tekshirishingiz mumkin.

Tyuring mashinasining tavsifi

Tyuring mashinasi ikkala yo'nalishda ham cheklanmagan, hujayralarga bo'linadigan lenta va boshqaruv moslamasini o'z ichiga oladi o'qish-yozish boshi yoki oddiygina mashina), ko'p shtatlardan birida bo'lishga qodir. Boshqarish moslamasining mumkin bo'lgan holatlari soni cheklangan va aniq ko'rsatilgan.

Tekshirish moslamasi lenta bo'ylab chapga va o'ngga siljishi, cheklangan alifbo belgilarini kataklarga o'qishi va yozishi mumkin. \ (A_0 \) yoki \ (\ Lambda \) bilan belgilangan maxsus bo'sh belgi ajratilgan bo'lib, u lentaning barcha katakchalarini to'ldiradi, faqat kirish ma'lumotlari yozilgan (sonli sonlar) bundan mustasno.

Nazoratchi Turing mashinasi tomonidan berilgan algoritmni ifodalovchi o'tish qoidalariga muvofiq ishlaydi. Har bir o'tish qoidasi mashinaga joriy holatga va joriy katakchada kuzatiladigan belgiga qarab, bu katakka yangi belgi yozishni, yangi holatga o'tishni va bitta katakchani chapga yoki o'ngga ko'chirishni buyuradi. Tyuring mashinasining ba'zi holatlarini terminal sifatida belgilash mumkin va ularning har biriga o'tish ishning tugashini, algoritmning to'xtashini bildiradi.

Tyuring mashinasi mavhum tushuncha bo'lsa -da, bunday mashinani tasavvur qilishning o'zi kifoya (cheklangan lenta bilan bo'lsa ham) va shunga o'xshash demo mashinalari ham bor:

Tyuring mashinasining algoritmini jadval ko'rinishida ko'rsatish qulay: jadval ustunlari lentadagi joriy (kuzatilgan) belgiga mos keladi, satrlar mashinaning hozirgi holatiga mos keladi va hujayralarda mashina tomonidan bajariladigan buyruq.

Buyruq, o'z navbatida, quyidagi tuzilishga ega bo'lishi mumkin:

\ [a_k \ chap \ lbrace \ boshlanish (matritsa) L \\ N \\ R \ oxiri (matritsa) \ o'ng \ rbrace q_m \]

Birinchi navbatda \ (a_k \) katakchasiga yozilishi kerak bo'lgan alifbo belgisi keladi, keyin mashinaning chapga (L), o'ngga (P) yoki hech qayerga (joyida qol, H) harakati ko'rsatilgan. Oxirida \ (q_m \) avtomat kirishi kerak bo'lgan yangi holat ko'rsatiladi.

Jadval yacheykasi joriy belgi \ (a_i \) va mashinaning hozirgi holati \ (q_j \) bilan aniq belgilanadi.

Keling, ish boshlanishida Tyuring mashinasi ishlayotganiga rozi bo'laylik boshlang'ich holat, \ (q_1 \) bilan belgilanadi va ga o'tishda to'xtatish holati\ (q_0 \) algoritmi tugadi va mashina to'xtaydi.

Misol

Keling, kiruvchi so'zga 1 qo'shadigan, o'nlik raqam bo'lgan Tyuring mashinasi uchun algoritm tuzaylik.

Keyin tavsifiy ravishda algoritmni quyidagicha shakllantirish mumkin:

  1. O'ngga siljib, kirish so'zining boshini toping
  2. O'ngga siljib, kirish so'zining oxirini toping
  3. Kirish so'zining joriy bitiga bittasini qo'shing. Agar 0 dan 8 gacha raqam bo'lsa, chiqing. Aks holda, 0 yozing, chapga siljiting va 3 -bosqichga qayting.

Keling, bu algoritmni jadval shaklida yozamiz. Alfavit 0 dan 9 gacha bo'lgan raqamlardan va \ (\ Lambda \) bo'sh belgidan iborat. Shuningdek, bizga algoritm tavsifidagi bosqichlarga mos keladigan to'xtash holatini hisoblaydigan avtomatning 4 ta holati kerak.

Keling, \ (1 \) boshlang'ich holati kirish so'zining boshlanishini qidirish, \ (2 \) - kirish so'zining oxirini qidirish, \ (3 \) - 1 qo'shilishi.

\ (_ (q_j) \ teskari chiziq ^ (a_i) \) Λ 0 1 2 3 4 5 6 7 8 9
1 PP1 0H2 1H2 2H2 3H2 4H2 5H2 6H2 7H2 8H2 9H2
2 3L3 0P2 1P2 2P2 3P2 4P2 5P2 6P2 7P2 8P2 9P2
3 1H0 1H0 2H0 3H0 4H0 5H0 6H0 7H0 8H0 9H0 0L3

Keling, bu algoritmning ishlashini misol bilan kuzatamiz. Birinchi satr lentaga to'g'ri keladi, ikkinchisi mashinaning holatini va uning hozirgi holatini ko'rsatadi.

1 9 9
1

1 -holatda, avtomat bo'sh katakchaning tepasida. "DP1" jadvalidagi tegishli buyruq, ya'ni hujayrani bo'sh qoldiring, o'ng tomonga o'ting va 1 -holatda qoling:

1 9 9
1

Endi mashina "1" qiymatini kuzatadi. "1H2" mos keladigan buyruq, ya'ni hujayrada "1" ni qoldiring, qimirlamang va "2" holatiga o'ting:

1 9 9
2

"2" holatida, mashina "1" qiymatini kuzatadi. Tegishli "1P2" buyrug'i, ya'ni "1" ni qoldiring, o'ngga siljiting va "2" holatida qoling:

Vaziyat yana takrorlanadi:

Endi, 3 -holatda va "9" belgisini kuzatib, mashina "0L3" buyrug'ini bajaradi:

1 9 0
3

Vaziyat yana takrorlanadi:

"0" holati - to'xtash holati. Algoritm tugallandi.

Rasmiy tavsif

Matematik jihatdan Tyuring mashinasini quyidagicha ta'riflash mumkin.

Tyuring mashinasi (MT)

bu shakl tizimi \ (\ (A, a_0, Q, q_1, q_0, T, \ tau \) \), qaerda

  • \ (A \) - MT alifbosining cheklangan belgilar to'plami
  • \ (a_0 \ A \ da) - bo'sh alifbo belgisi
  • \ (Q \) - MT ning cheklangan holatlar to'plami
  • \ (q_1 \ Q \ da) - MT ning dastlabki holati
  • \ (Q_0 \ Q \ da) - MTning oxirgi holati (to'xtash holati)
  • \ (T = \ (A, P, H \) \) - MT siljishlar to'plami
  • \ (\ tau \) - MT dasturi, ya'ni xaritalashni aniqlaydigan funksiya \ (\ tau: A \ marta Q \ teskari chiziq \ (q_0 \) \ o'ng o'q A \ marta T \ marta Q \)

Algoritmlar nazariyasidagi kalit bu Tyuring dissertatsiyasi.

Turingning tezislari erkin tarzda tuzilgan:

Tyuring tezisida har qanday algoritmik yechiladigan masala, bu muammoni hal qiladigan Tyuring mashinasi mavjud. Aks holda, har qanday algoritm uchun ekvivalent Tyuring mashinasi mavjud.

Tyuring tezisi bizga oddiy matematik apparatdan foydalangan holda algoritmlar haqida gapirishga imkon beradi. Bundan tashqari, Tyuring mashinasining o'zi universal aktuator va bunday xayoliy mashinani yaratish imkoniyatining o'zi universal hisoblash texnologiyasini yaratish haqida gapirish uchun sabab bo'ldi.

Muqobil algoritm ta'riflari

Tyuring mashinasidan tashqari, Tyuring ta'rifiga teng bo'lgan bir nechta mustaqil ta'riflar mavjud.

Xususan, Post mashinasi orqali, Cherkov lambda hisobi orqali, Markovning oddiy algoritmi.

Keling, ushbu usullarni ko'rib chiqaylik.

Pochta mashinasi

Tyuringdan bir yil o'tib, amerikalik matematik Emil Leon Post mustaqil ravishda Turing mashinasiga qaraganda biroz soddalashtirilgan boshqa mavhum universal hisoblash mashinasini taklif qildi.

Post mashinasi ikki xonali alifbo bilan ishlaydi va mashinaning ichki holati almashtiriladi dastur liniyasi.

Aks holda, Post mashinasi Tyuring mashinasiga o'xshaydi: u erda avtomat va hujayralari bo'lgan cheksiz lenta bor.

Pochta mashinasi quyidagi buyruqlarni bajarishi mumkin:

  1. 1-ni yozing, dasturning i-qatoriga o'ting
  2. 0 yozing, dasturning i-qatoriga o'ting
  3. Chapga siljiting, dasturning i-qatoriga o'ting
  4. O'ngga siljiting, dasturning i-qatoriga o'ting
  5. Shartli sakrash: agar kuzatilgan katakchada 0 bo'lsa, dasturning i-qatoriga o'ting, aks holda dasturning j-satriga o'ting.
  6. STOP.

Post mashinasida bir nechta taqiqlangan buyruqlar mavjud:

  1. 1 -hujayraga yozish allaqachon 1 bo'lsa.
  2. 0 bo'lsa, 0 katakka yozish.

Bunday hodisalar halokatga olib keladi.

Pochta mashinasi uchun dastur yozish uchun siz quyidagi yozuvlardan foydalanishingiz mumkin:

  1. ∨ i - 1 yozing, dasturning i -qatoriga o'ting
  2. × i - 0 yozing, dasturning i -qatoriga o'ting
  3. ← i - chapga siljishni bajaring, dasturning i -qatoriga o'ting
  4. → i - o'ngga siljishni bajaring, dasturning i -qatoriga o'ting
  5. ? i; j-shartli sakrash: agar kuzatilgan katakchada 0 bo'lsa, dasturning i-qatoriga o'ting, aks holda dasturning j-satriga o'ting.
  6. ! - STOP.

Namuna dasturi:

1. → 2 2.? 1; 3 3. × 4 4. ← 5 5.!

Bu dastur mashinaning boshlang'ich pozitsiyasining o'ng tomonida joylashgan birinchi belgini (1) o'chirib tashlaydi va uning chap tomonidagi kameradagi mashinani to'xtatadi.

Umuman olganda, Postning avtomobili avvalgisidir majburiy dasturlash tillari, masalan, C, Fortran va boshqalar.

Post mashinasi Tyuring mashinasiga teng. Boshqacha aytganda, Tyuring mashinasi uchun har qanday dastur uchun siz Post mashinasi uchun ekvivalent dastur yozishingiz mumkin va aksincha.

Bu ekvivalentlikning muhim natijalaridan biri shundaki har qanday alifbo ikkilik kodga tushirilishi mumkin.

Turing tezisiga o'xshab, Post tezislari ham bor.

Post tezisida har qanday algoritm pochta mashinasi shaklida ifodalanishi mumkin.

Oddiy Markov algoritmi

Oddiy Markov algoritmlari turli alifbolardagi so'zlarga qo'llanilishi uchun mo'ljallangan.

Har qanday oddiy algoritm ta'rifi ikki qismdan iborat:

  1. Alifbo algoritm
  2. Sxemalar algoritm

Algoritm o'zi uchun qo'llaniladi so'zlar, ya'ni belgilar ketma -ketligi alifbo.

Oddiy algoritm sxemasi cheklangan tartibli deyiladi almashtirish formulalari, ularning har biri bo'lishi mumkin oddiy yoki final... \ (L \ dan D \) shaklining ifodalari oddiy almashtirish formulalari deb ataladi, bu erda \ (L \) va \ (D \) algoritm alifbosidan tuzilgan ikkita ixtiyoriy so'z (mos ravishda chap va o'ng deb nomlanadi). almashtirish formulasining tomonlari). Xuddi shunday, oxirgi almashtirish formulalari \ (L \ to \ cdot D \) shaklining ifodasidir, bu erda \ (L \) va \ (D \) algoritm alifbosidan tuzilgan ikkita ixtiyoriy so'z.

\ (\ To \) va \ (\ to \ cdot \) yordamchi belgilar algoritm alifbosiga tegishli emas deb taxmin qilinadi.

Oddiy algoritmni ixtiyoriy so'zga qo'llash jarayoni \ (V \) quyidagi harakatlar ketma -ketligidir:

  1. \ (V "\) algoritmning oldingi bosqichida olingan so'z bo'lsin (yoki joriy qadam birinchi bo'lsa asl so'z).
  2. Agar chap tomoni \ (V "\) ga kiradigan almashtirish formulalari o'rtasida hech qanday almashtirish bo'lmasa, u holda algoritm ishi tugallangan hisoblanadi va bu ishning natijasi \ (V" \ so'zidir. ).
  3. Aks holda, chap tomoni \ (V "\) ga kiritilgan almashtirish formulalari orasida birinchisi tanlanadi.
  4. \ (V "\) so'zining \ (RLS \) (bu erda \ (R \) - prefiks va \ (L \) qo'shimchasi) ko'rinishidagi barcha mumkin bo'lgan vakilliklardan biri shunday tanlanganki, \ ( R \) eng qisqa, keyin \ (V "= RDS \) o'rnini bosadi.
  5. Agar almashtirish formulasi cheklangan bo'lsa, algoritm \ (V "\) natijasi bilan to'ldiriladi, aks holda 1 -bosqichga o'ting (keyingi qadam).

Har qanday oddiy algoritm Tyuring mashinasiga tengdir va aksincha - har qanday Tyuring mashinasi oddiy algoritmga teng.

Oddiy algoritmlar uchun Tyuring tezisining analogi odatda chaqiriladi normallashtirish printsipi.

Misol

Bu algoritm ikkilik sonlarni "bitta" ga aylantiradi (bunda N bo'lmagan tamsaytli yozuv N tayoqchalardan iborat). Masalan, 101 ikkilik raqami 5 tayoqchaga aylanadi: |||||

Alfavit: (0, 1, |) Qoidalar:

  1. 1 → 0|
  2. |0 → 0||
  3. 0 -> (bo'sh satr)
Asl qator: 101 Ijro etilishi:
  1. 0|00|
  2. 00||0|
  3. 00|0|||
  4. 000|||||
  5. 00|||||
  6. 0|||||
  7. |||||

Rekursiv funktsiyalar

Tyuring mashinasiga teng tizim matematik funktsiyalar asosida qurilishi mumkin. Buning uchun biz quyidagi funktsiyalar sinflarini joriy etishimiz kerak:

  • ibtidoiy rekursiv funktsiyalar
  • umumiy rekursiv funktsiyalar
  • qisman rekursiv funktsiyalar

Oxirgi sinf Tyuring hisoblanadigan funktsiyalar sinfiga to'g'ri keladi (ya'ni Tyuring mashinasi uchun algoritm tuzish orqali hisoblash mumkin).

Algoritmni rekursiv funktsiyalar orqali aniqlash aslida lambda hisobining markazida va uning asosida yondashuv qurilgan. funktsional dasturlash.

Primitiv rekursiv funktsiyalar

Ibtidoiy rekursiv funktsiyalar klassi o'z ichiga oladi asosiy funktsiyalar va operatorlar yordamida asosiy funktsiyalardan olingan barcha funktsiyalar almashtirishlar va ibtidoiy rekursiya.

Asosiy funktsiyalarga quyidagilar kiradi:

  • \ N (0 () = 0 \) null funktsiyasi har doim \ (0 \) qaytaradigan argumentlari bo'lmagan funksiya.
  • \ (S (x) = x + 1 \) ketma -ketlik funktsiyasi har qanday natural songa \ (x \) quyidagi sonni \ (x + 1 \) belgilaydigan funksiya.
  • Vazifalar \ (I_n ^ m (x_1, \ ldots, x_n) = x_m \), bu erda \ (0

Qolgan sinf funktsiyalarini yaratish uchun operatorlardan foydalaniladi:

  • O'zgartirishlar. \ (M \) o'zgaruvchilardan \ (f \) funktsiyasi va \ (n \) o'zgaruvchilardan \ (m \) funktsiyalari \ (g_1, \ ldots, g_m \) uchun, almashtirish natijasi \ (g_k \) \ (f \) da - bu funksiya \ (h (x_1, \ ldots, x_n) = f (g_1 (x_1, \ ldots, x_n), \ ldots, g_m (x_1, \ ldots, x_n)) \)\ (n \) o'zgaruvchilardan.
  • Ibtidoiy rekursiya. \ (F (x_1, \ ldots, x_n) \) \ (n \) o'zgaruvchilar funktsiyasi va \ (g (x_1, \ ldots, x_ (n + 2)) \) funktsiyasi \ (n + 2 \) o'zgaruvchilar. Keyin ibtidoiy rekursiya operatorini \ (f \) va \ (g \) funktsiyalariga qo'llash natijasi \ (n + 1 \) o'zgaruvchining \ (h \) funktsiyasi bo'ladi: \ [h (x_1, \ ldots, x_n, 0) = f (x_1, \ ldots, x_n) \] \ [h (x_1, \ ldots, x_n, y + 1) = g (x_1, \ ldots, x_n, y, h (x_1, \ ldots, x_n, y)) \]

Qisman rekursiv funktsiyalar

Qisman rekursiv funktsiyalar sinfiga ibtidoiy rekursiv funktsiyalar, shuningdek, argumentlarni minimallashtirish operatori yordamida ibtidoiy rekursivlardan olingan barcha funktsiyalar kiradi:

Argumentlarni minimallashtirish operatori

\ (F \) \ (n \) o'zgaruvchilarining funktsiyasi bo'lsin \ (x_i \ in \ mathbb (N) \). \ Argument minimallashtirish operatorini \ (f \) funktsiyasiga qo'llash natijasi \ (n-1 \) argumentining \ (h \) funktsiyasi bo'lib, u quyidagicha ta'riflanadi.

\ [h (x_1, \ ldots, x_ (n-1)) = \ min y, \] qayerda \ Ya'ni, \ (h \) oxirgi argumentning minimal qiymatini \ (f \) nol bo'lgan \ (f \) funktsiyasiga qaytaradi.

Ibtidoiy rekursiv funktsiyalar har doim hisoblansa -da, ba'zi argument qiymatlari uchun qisman rekursiv funktsiyalar aniqlanmasligi mumkin.

Aniqroq aytganda, qisman rekursiv funktsiyalarni "qisman aniqlangan rekursiv funktsiyalar" deb atash kerak, chunki ular mumkin bo'lgan argument qiymatlarining faqat bir qismiga to'g'ri keladi.

Umumiy rekursiv funktsiyalar

Umumiy rekursiv funktsiyalar - bu har qanday argument qiymati uchun belgilangan barcha qisman rekursiv funktsiyalarning kichik klassi. Berilgan qisman rekursiv funksiyaning umumiy rekursiv ekanligini aniqlash muammosi algoritmik jihatdan aniq emas... Bu bizni hisoblash nazariyasi va to'xtatish muammosiga olib keladi.

Hisoblash nazariyasi va to'xtatish muammosi

Bizning tasavvurlarimiz odatda hal qilinmaydigan muammolar, ya'ni algoritm tuzish mumkin bo'lmagan muammolarning mavjudligiga imkon beradi.

Hisoblash nazariyasi bunday muammolarni hal qiladi.

Algoritmik yechilmaydigan muammolarga misollar muammoni to'xtatish va inkubatsiyani aniqlash muammosi... Keling, ularni batafsilroq ko'rib chiqaylik.

To'xtatish muammosi A algoritmi va \ (x \) kirish ma'lumotlarining tavsifi asosida \ (A \) algoritmi \ (x \) kirish ma'lumotlarida to'xtab qolishini aniqlash kerak.

To'xtatish muammosi algoritmik jihatdan hal qilinmaydi. Keling buni isbotlaylik.

\ (\ Delta \)

To'xtatish muammosini hal qiladigan universal algoritm bo'lsin. Algoritmlarni tavsiflovchi matnlarni qayta ishlaydigan algoritmlar sinfini ko'rib chiqing.

To'xtatish muammosini hal qilish uchun universal algoritm mavjudligi sababli, yuqorida aytib o'tilgan sinfdagi algoritm o'z matnida to'xtab qoladimi yoki yo'qligini aniqlaydigan algoritm mavjud. Keling, bunday algoritmni \ (B \) bilan belgilaymiz.

\ (C \) algoritmini tuzamiz, kirish ma'lumoti \ (A \) algoritmi matni bo'lib, u o'z matnini qayta ishlaydi:

  1. \ (B \) algoritmini \ (A \) ustidan bajaring.
  2. Agar \ (B \) algoritmi \ (A \) o'z matnida to'xtashini aniqlasa, 1 -bosqichga o'ting. Aks holda, 3 -bosqichga o'ting.
  3. Algoritm tugashi \ (C \).

\ (C \) algoritmini \ (C \) algoritmiga qo'llashga urinib, biz aniq qarama -qarshilikka duch kelamiz: agar \ (C \) o'z matnida to'xtasa, u to'xtata olmaydi va aksincha. Shuning uchun \ (B \) algoritmi yo'q. \ (\ Delta \ emas)

To'xtatish muammosining yanada umumiy formulasi - bu hatchablelikni aniqlash muammosi.

Tugatish qobiliyatini aniqlash muammosi

Ma'lum alifbo, bu alifbo so'zlari (formulalari) va ushbu alifbo so'zlari bo'yicha rasmiy o'zgartirishlar tizimi aniqlansin (ya'ni, mantiqiy hisob qurilgan)

Bu mantiqiy hisob doirasida \ (R \) va \ (S \) ikkita so'z uchun \ (R \) dan \ (S \) gacha bo'lgan deduktiv zanjir bormi?

1936 yilda Alonzo cherkovi Cherch teoremasini isbotladi.

Cherkov teoremasi Deduktsiyani tan olish muammosi algoritmik jihatdan hal qilinmaydi.

Cherkov lambda hisobining rasmiyligini isbotlash uchun ishlatgan. 1937 yilda, mustaqil ravishda, Tyuring Turing mashinasi formalizmidan foydalanib, xuddi shu teoremani isbotladi.

Algoritmlarning barcha ta'riflari bir -biriga teng bo'lgani uchun, algoritmning aniq ta'rifi bilan bog'liq bo'lmagan va tushuncha bilan ishlaydigan tushunchalar tizimi mavjud. hisoblash funktsiyasi.

Hisoblanadigan funksiya Algoritm yordamida hisoblanadigan funksiya.

Kirish va chiqish ma'lumotlari o'rtasidagi bog'liqlikni algoritm yordamida tasvirlab bo'lmaydigan muammolar mavjud. Bunday funktsiyalar hisoblab bo'lmaydigan.

Hisoblanmaydigan funktsiyaga misol

\ Mathbb (N) \) \ (\ forall n \ \ for \ n uchun belgilangan \ (h (n) \) funktsiyasini quyidagicha bajaring:

\ [h (n) = \ boshlanish (holatlar) 1, & \ matn (agar bo'lsa) \ pi \ matn (aniq ketma-ketlik bor) n \ matn (9-k) \\ 0, & \ matn (aks holda) ) \ end (holatlar) \]

Biz bu funktsiya uchun \ (1 \) qiymatini olishimiz mumkin, lekin \ (0 \) qiymatini olish uchun \ (\ pi \) sonining cheksiz kasr kengayishini tekshirishimiz kerak, bu aniq cheklangan vaqt. Shunday qilib, bu funktsiyani hisoblash mumkin emas.

Zamonaviy informatika fanining eng muhim savollaridan biri shundaki, uning yordamida har qanday rasmiy ijrochiga taqlid qilish mumkin bo'lgan rasmiy ijrochi bormi. Bu savolga javobni deyarli bir vaqtning o'zida ikkita taniqli olim - A. Tyuring va E. Post olgan. Ular taklif qilgan ijrochilar bir -biridan farq qilar edilar, lekin ular bir -biriga taqlid qilishlari, eng muhimi, har qanday rasmiy ijrochining ishiga taqlid qilishlari mumkin edi.

Rasmiy pudratchi nima? Bu nimani anglatadi - bitta rasmiy ijrochi boshqa rasmiy ijrochining ishiga taqlid qiladi? Agar siz kompyuter o'yinlarini o'ynagan bo'lsangiz, ekrandagi narsalar o'yinchining buyruqlariga shubhasiz bo'ysunadi. Har bir ob'ektda amaldagi buyruqlar to'plami mavjud. Shu bilan birga, kompyuterning o'zi ijrochi va virtual emas, balki haqiqiydir. Ma'lum bo'lishicha, bitta rasmiy ijrochi boshqa rasmiy ijrochining ishiga taqlid qiladi.

Tyuring mashinasi qanday ishlashini ko'rib chiqing.

Tyuring mashinasi - bu hujayralarga bo'linadigan cheksiz lenta va lenta bo'ylab harakatlanadigan vagon (o'quvchi va printer).

Shunday qilib, Tyuring mashinasi rasman ikkita alifbo to'plami bilan tasvirlangan:

A = (a1, a2, a3, ..., an) - tashqi alifbo, dastlabki ma'lumotlarni yozish uchun ishlatiladi

Q = (q1, q2, q3,…, qm) - ichki alifbo, o'quvchi va bosma qurilmaning holatlar to'plamini tavsiflaydi.

Lentaning har bir katakchasida A = (a0, a1, ..., an) tashqi alifbosidagi belgi bo'lishi mumkin (bizda A = (0, 1))

Tyuring mashinasining amaldagi harakatlari quyidagilar:

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

2) qo'shni kameraga o'ting

3) holatni ichki alifbo Q belgisi bilan ko'rsatilgan holatlardan biriga o'zgartiring

Tyuring mashinasi - bu stol boshqariladigan mashina.

Jadvaldagi qatorlar tanlangan A alifbosining belgilariga, ustunlar esa avtomat Q = (q0, q1,…, qm) holatiga mos keladi. Ish boshlanishida Tyuring mashinasi q1 holatida bo'ladi. Q0 holati - bu oxirgi holat; unga kirgandan so'ng, avtomat o'z ishini tugatadi.

Ai va qj holatiga mos keladigan jadvalning har bir katakchasi uch qismdan iborat buyruqni o'z ichiga oladi
A alifbosidagi belgi
· Harakat yo'nalishi: ">" (o'ngda), "<» (влево) или «.» (на месте)
Mashinaning yangi holati

Yuqoridagi jadvalda A = (0, 1, _) alifbosi (3 ta belgidan iborat) va ichki alifbo Q = (q1, q2, q3, q4, q0), q0 - vagonning to'xtashiga sabab bo'lgan holat.

Keling, bir nechta vazifalarni hal qilish orqali ko'rib chiqaylik. Turing mashinasini saytdagi bo'limda yuklab olishingiz mumkin.

Muammo 1. A = (0, 1, _) bo'lsin. Tasma ustidagi katakchalarda alifbodan quyidagi belgilar joylashtirilgan 0011011. Karet birinchi belgidan yuqori. 0 ni 1 ga, 1 ni 0 ga almashtiradigan va aravani asl holatiga qaytaradigan dastur yozish kerak.

Endi vagon holatini aniqlaylik. Men ularni "arava biror narsa qilishni xohlaydi" deb atayman.

q1) Vagon o'ng tomonga o'tishi kerak: agar u 0 ko'rsa, uni 1 ga o'zgartiradi va q1 holatida qoladi, 1 ko'rsa, 0 ga o'zgartiradi va q1 holatida qoladi, agar _ ko'rsa, u 1 hujayra orqaga qaytadi, "boshqa narsani xohlaydi", ya'ni q2 holatiga o'tadi. Keling, o'z fikrimizni ijrochi stoliga yozaylik. Sintaksis uchun dastur yordamiga qarang)

q2) Endi biz "arava istagi" ni ta'riflaymiz q2. Biz asl holatimizga qaytishimiz kerak. Buning uchun: agar biz 1ni ko'rsak, biz uni qoldiramiz va q2 holatida qolamiz (xuddi shu istak bilan belgilar qatorining oxiriga yetish uchun); agar biz 0 ni ko'rsak, biz uni tark etamiz va q2 holatida chap tomonga o'tishda davom etamiz; biz ko'ramiz _ - o'ngga 1 katakka siljigan. Bu erda siz muammoning bayonotida kerakli joyni topasiz. biz q0 holatiga o'tamiz.

Videoda dasturning ishini ko'rishingiz mumkin:

Muammo 2. Berilgan: 0 va 1 ning oxirgi ketma -ketligi (001101011101). Ularni bu ketma -ketlikdan keyin bo'sh katak orqali yozib qo'yish kerak va shu ketma -ketlikda ularni 0 bilan almashtirish kerak. Masalan:

001101011101 dan biz 000000000000 1111111 olamiz.

Ko'rib turganingizdek, bu ketma -ketlikdan keyin ettitasi yozilgan va ularning o'rnida nol bor.

Keling, mantiqqa o'taylik. Tashish uchun qaysi davlatlar kerakligini va qancha bo'lishini aniqlang.

q1) ko'rdim 1 - nolga to'g'rilang va boshqa holatga o'ting q2 (vagon bir pasda hammasini nolga o'zgartirmasligi uchun yangi holat kiritiladi)

q2) hech narsani o'zgartirmang, ketma -ketlikning oxiriga o'ting

q3) karet bo'sh katakchani ko'rishi bilan o'ng tomonga qadam tashlaydi va birini chizadi, agar uni ko'rsa, oxiridagi belgiga imzo qo'yadi. Biz birlikni chizishimiz bilan q4 holatiga o'tamiz

q4) hech narsani o'zgartirmasdan yozma birliklardan o'tamiz. Biz ketma -ketlikni ketma -ketlikdan ajratadigan bo'sh hujayraga etib borganimiz sari, biz yangi q5 holatdan o'tamiz

q5) bu holatda biz hech narsani o'zgartirmasdan ketma -ketlikning boshiga o'tamiz. Biz bo'sh hujayraga etib boramiz, orqaga burilib q1 holatiga o'tamiz

Bu ketma -ketlikning oxirigacha q1 holatidan o'tib, bo'sh katakka duch kelganda, tashish q0 holatini oladi.

Biz quyidagi dasturni olamiz:

Tyuring mashinasining ishini quyidagi videoda ko'rishingiz mumkin.

Tyuring mashinasi - bu quyidagi ob'ektlar to'plami

  • 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 ikkala yo'nalishda ham cheksiz lenta, hujayralarga bo'linadi, ularning har birida har qanday vaqtda A alifbosidan faqat bitta belgi yozilishi mumkin;
  • 5) ko'p shtatlardan birida bo'lishga qodir bo'lgan boshqaruv moslamasi

Bo'sh katakchaning belgisi tashqi alifbo 0 harfidir.

Shtatlar orasida mashina ishlay boshlagan dastlabki q 1 va mashina to'xtaydigan oxirgi (yoki to'xtash holati) q 0 ajratiladi.

Boshqarish moslamasi lenta bo'ylab chapga va o'ngga harakat qilishi, A alifbosi harflarini o'qishi va lentaning katakchalariga yozishi mumkin. Boshqarish moslamasi quyidagi buyruqlar asosida ishlaydi.

q i a j> a p X q k

Yozuv quyidagilarni bildiradi: agar boshqaruv moslamasi qi holatida bo'lsa va kuzatilgan katakchada aj harfi yozilgan bo'lsa, unda hujayradagi aj o'rniga (1), ap yoziladi, (2) mashina ko'rishga o'tadi keyingi ko'rilgan hujayradan keyingi o'ng katak, agar X = P bo'lsa yoki keyingi chap yacheykani ko'rish uchun, agar X = L bo'lsa yoki lentaning o'sha katagini tekshirishni davom ettirsa, X = C bo'lsa, (3) boshqaruv moslamasi q k holatiga o'tadi.

Mashinaning ishlashi shartli ravishda uning holati bilan to'liq aniqlanganligi sababli, ma'lum bir vaqtda va shu vaqtda hujayraning tarkibi kuzatiladi, shuning uchun q i a j mumkin bo'lgan har bir konfiguratsiya uchun aniq bitta qoida mavjud. Faqat mashina to'xtaydigan oxirgi holat uchun qoidalar yo'q. Shuning uchun tashqi alifbo A = (a0, a1,…, an) va ichki Q = (q1, q2,…, qm) bo'lgan Tyuring mashinasi dasturida ko'pi bilan m (n + 1) ko'rsatma mavjud.

A alifbosidagi yoki Q alifbosidagi yoki A alifbosidagi so'z - bu tegishli alifbo harflarining har qanday ketma -ketligi. K-konfiguratsiya deganda biz mashinaning tasmasi tasvirini k-chi qadamning boshida hosil bo'lgan ma'lumotni (yoki l alifbosidagi so'zni k boshida yozilganini bildiramiz. th qadam), bu bosqichda qaysi hujayra ko'rib chiqilayotgani va mashina qanday holatda ekanligini ko'rsatadi. Faqat oxirgi konfiguratsiyalar mantiqan, ya'ni. sonli sonlar bundan mustasno, lentaning barcha kataklari bo'sh bo'lganlar. Agar konfiguratsiya oxirgi holatda bo'lsa, konfiguratsiya yakuniy deb nomlanadi.

Agar biz Tyuring mashinasining har qanday yakuniy bo'lmagan konfiguratsiyasini boshlang'ich sifatida tanlasak, mashinaning ishi oxirgi konfiguratsiyaga erishilgunga qadar dastlabki konfiguratsiyani mashina dasturiga muvofiq ketma-ket (bosqichma-bosqich) o'zgartirishdan iborat bo'ladi. Shundan so'ng, Tyuring mashinasining ishi tugallangan deb hisoblanadi va ish natijasi erishilgan yakuniy konfiguratsiyadir.

Aytamizki, A (a 0) = (a 1, ..., an) alifbosidagi bo'sh bo'lmagan b so'zni mashina standart holatda qabul qiladi, agar u lentaning ketma-ket kataklariga yozilgan bo'lsa, boshqa barcha hujayralar bo'sh, va mashina b so'zi yozilganlardan eng chap yoki eng o'ng yacheykaga qaraydi. Agar standart pozitsiyada so'zni qabul qiladigan mashina q 1 boshlang'ich holatda bo'lsa (mos ravishda q 0 to'xtash holatida), standart pozitsiya boshlang'ich (oxirgi) pozitsiya deb ataladi.

Agar b so'zini qayta ishlash Tyuring mashinasini yakuniy holatga o'tkazsa, u holda b ga to'g'ri keladi, aks holda b ga taalluqli emas (mashina cheksiz ishlaydi)

Keling, bir misolni ko'rib chiqaylik:

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

q 1 0> 1 L q 2;

q 1 1> 0 C q q 2;

q 2 0> 0 P q 0;

q 2 1> 1 C q 1;

Bu dasturni jadval yordamida yozish mumkin

Birinchi qadamda quyidagi buyruq bajariladi: q 1 0> 1 L q 2 (boshqaruv moslamasi q1 holatida va kuzatilgan katakchada 0 harfi yoziladi, hujayraga 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

Bu konfiguratsiya yakuniy hisoblanadi, chunki mashina q 0 to'xtash holatida edi.

Shunday qilib, dastlabki 110 so'z mashinada 101 so'ziga ishlov beriladi.

Olingan konfiguratsiyalar ketma -ketligini qisqacha yozish mumkin (kuzatilgan katakchaning tarkibi hozirda mashina joylashgan holatning o'ng tomoniga yozilgan):

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

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

Tyuring mashinasi (MT)- mavhum ijrochi (mavhum hisoblash mashinasi). 1936 yilda Alan Tyuring tomonidan algoritm kontseptsiyasini rasmiylashtirish taklif qilingan.

Tyuring mashinasi - cheklangan davlat mashinasining kengaytmasi va Cherkovga ko'ra - Tyuring tezisida, barcha ijrochilarga taqlid qilishga qodir(o'tish qoidalarini belgilab) bosqichma-bosqich hisoblash jarayonini qandaydir tarzda amalga oshiradi, bunda hisoblashning har bir bosqichi juda oddiy.

Ya'ni, har qanday intuitiv algoritm Turing mashinasi yordamida amalga oshirilishi mumkin.

YouTube kolleji

    1 / 5

    ✪ 09 - Algoritmlarga kirish. Tyuring mashinasi

    ✪ Tyuring mashinasi - Aleksandr Shen

    ✪ 20 -ma'ruza: Tyuring mashinasi

    ✪ Tyuring mashinasi. Ishga misol

    ✪ 16 - hisoblash qobiliyati. Tyuring mashinalari. Motivatsiya va misollar

    Subtitrlar

Tyuring mashinasining tuzilishi

Tyuring mashinasi har ikki yo'nalishda ham cheksizni o'z ichiga oladi tasma(Tyuring mashinalari mumkin, ular bir nechta cheksiz lentalarga ega), hujayralarga bo'linadi va nazorat qilish qurilmasi(ham deyiladi o'qish-yozish boshi (GZCH)), birida bo'lishga qodir davlatlar to'plami... Boshqarish moslamasining mumkin bo'lgan holatlari soni cheklangan va aniq ko'rsatilgan.

Tekshirish moslamasi lenta bo'ylab chapga va o'ngga siljishi, cheklangan alifbo belgilarini kataklarga o'qishi va yozishi mumkin. Maxsus ajralib turadi bo'sh lentaning barcha katakchalarini to'ldiruvchi belgi, ulardan tashqari (oxirgi son), kirish ma'lumotlari yozilgan.

Tekshirish moslamasi mos ravishda ishlaydi o'tish qoidalari algoritmni ifodalaydi, amalga oshadigan bu Tyuring mashinasi. Har bir o'tish qoidasi mashinaga joriy holatga va joriy katakchada kuzatiladigan belgiga qarab, bu katakka yangi belgi yozishni, yangi holatga o'tishni va bitta katakchani chapga yoki o'ngga ko'chirishni buyuradi. Tyuring mashinasining ba'zi holatlarini quyidagicha belgilash mumkin Terminal, va ularning birortasiga o'tish ishning tugashini, algoritmning to'xtashini bildiradi.

Tyuring mashinasi deyiladi deterministik agar jadvaldagi holat va chiziq belgilarining har bir kombinatsiyasiga ko'pi bilan bitta qoida mos kelsa. Agar "chiziqli belgi - holat" jufti bo'lsa, unda 2 yoki undan ko'p ko'rsatma bo'lsa, bunday Tyuring mashinasi deyiladi noaniq.

Tyuring mashinasining tavsifi

Maxsus Tyuring mashinasi A alifbosi harflari to'plami, Q holatlar to'plami va unga muvofiq ishlaydigan mashina ishlaydigan qoidalar majmuasini sanab o'tish yo'li bilan aniqlanadi. Ular quyidagi shaklga ega: qiaj → q i1 a j1 dk (agar bosh qi holatida bo'lsa va aj harfi kuzatilgan katakka yozilgan bo'lsa, u holda bosh q i1 holatiga o'tadi, hujayrada j1 yoziladi. aj o'rniga, bosh dk harakatini amalga oshiradi, uning uchta varianti bor: bitta hujayra chapga (L), bitta hujayra o'ngga (R), joyida qol (N)). Har qanday mumkin bo'lgan konfiguratsiya uchun aniq bitta qoida bor (deterministik bo'lmagan Tyuring mashinasi uchun ko'proq qoidalar bo'lishi mumkin). Faqat mashina to'xtaydigan oxirgi holat uchun qoidalar yo'q. Bunga qo'shimcha ravishda, siz tugatish va boshlanish holatlarini, tasmadagi dastlabki konfiguratsiyani va mashina boshining joyini ko'rsatishingiz kerak.

Tyuring mashinasiga misol

Yagona sanoq sistemasida sonlarni ko'paytirish uchun MT ga misol keltiraylik. "Qiaj → q i1 a j1 R / L / N" qoidasining yozuvi quyidagicha tushunilishi kerak: qi - bu qoida bajarilgan holat, aj - bosh joylashgan katakdagi ma'lumotlar, q i1 - bu borish kerak bo'lgan holat, j1 - hujayraga nima yozish kerak, R / L / N - ko'chirish buyrug'i.

Mashina quyidagi qoidalarga muvofiq ishlaydi:

q 0 q 1 q 2 q 3 q 4 q 5 q 6 q 7 q 8
1 q 0 1 → q 0 1R q 1 1 → q 2 aR q 2 1 → q 2 1L q 3 1 → q 4 aR q 4 1 → q 4 1R q 7 1 → q 2 aR
× q 0 × → q 1 × R q 2 × → q 3 × L q 4 × → q 4 × R q 6 × → q 7 × R q 8 × → q 9 × N
= q 2 = → q 2 = L q 4 = → q 4 = R q 7 = → q 8 = L
a q 2 a → q 2 aL q 3 a → q 3 aL q 4 a → q 4 aR q 6 a → q 6 1R q 7 a → q 7 aR q 8 a → q 8 1L
* q 0 * → q 0 * R q 3 * → q 6 * R q 4 * → q 5 1R
q 5 → q 2 * L

Shtatlarning tavsifi:

Boshlash
q 0 boshlang'ich holat. Biz o'ngdagi "x" belgisini qidiramiz. Qachon topilsa, biz q1 holatiga o'tamiz
q 1 biz "1" ni "a" ga almashtiramiz va q2 holatiga o'tamiz
Hamma "1" ni birinchi raqamdan natijaga o'tkazing
q 2 chapda "x" ni qidiring. Qachon topilsa, biz q3 holatiga o'tamiz
q 3 chapda "1" ni qidiring, uni "a" bilan almashtiring va q4 holatiga o'ting.

Agar "1" tugagan bo'lsa, biz "*" ni topamiz va q6 holatiga o'tamiz
q 4 oxirigacha o'ting (o'ngda "*" ni qidiring), "*" ni "1" bilan almashtiring va q5 holatiga o'ting.
q 5 oxirigacha "*" qo'shing va q2 holatiga o'ting
Biz ikkinchi raqamning har bir raqamini qayta ishlaymiz
q 6 o'ngda "x" ni qidiring va q7 holatiga o'ting. Biz qidirayotganimizda "a" ni "1" ga almashtiramiz.
q 7 o'ngda "1" yoki "=" ni qidiring

"1" ni topganda, biz uni "a" bilan almashtiramiz va q2 holatiga o'tamiz

"=" topilganda, biz q8 holatiga o'tamiz
Oxiri
q 8 chapda "x" ni qidiring. Qachon topilsa, biz q9 holatiga o'tamiz. Biz qidirayotganimizda "a" ni "1" ga almashtiramiz.
q 9 terminal holati (to'xtatish algoritmi)

Birlik tizimidagi MT yordamida 3 ga 2 ga ko'paytiring. Protokolda MT ning boshlang'ich va oxirgi holatlari, tasma ustidagi dastlabki konfiguratsiya va mashina boshining joyi ko'rsatilgan (tagiga chizilgan belgi).

Boshlash. Biz q 0 holatidamiz, ma'lumotlarni mashinaga kiritdik: *111x11 = *, mashina boshi birinchi belgida joylashgan *.

1 -qadam. Keling, mashinaning q 0 holatida va "*" belgisidan yuqori bo'lganida nima qilishini qoidalar jadvaliga qaraymiz. Bu 5 -qatorning 1 -ustunidagi qoida - q 0 * → q 0 * R. Bu shuni anglatadiki, biz q 0 holatiga o'tamiz (ya'ni, biz uni o'zgartirmaymiz), belgi "*" bo'ladi (ya'ni o'zgarmaydi) va biz kiritgan matn bo'ylab harakatlanamiz "*111x11 =*" o'ngga bir pozitsiya (R), keyin 1 -belgi bo'yicha 1. O'z navbatida, q 0 1 (1 -ustun 1 -qator) holati q 0 1 → q 0 1R qoidasi bilan ishlanadi. Ya'ni, yana o'ngga 1 pozitsiyaga o'tish bor. Bu "x" belgisida turmagunimizcha sodir bo'ladi. Va hokazo: biz holatni olamiz (indeks q), biz turgan belgini (chizilgan belgi) olamiz, ularni bog'laymiz va qoidalar jadvaliga muvofiq hosil bo'lgan kombinatsiyaning ishlashini kuzatamiz.

Oddiy so'zlar bilan aytganda, ko'paytirish algoritmi quyidagicha: 2 -faktorning 1 -birligini belgilang, uni "a" harfi bilan almashtiring va butun 1 -omilni teng belgining orqasiga o'tkazing. O'tkazish navbatma -navbat 1 -faktor birliklarini "a" ga almashtirish va satr oxiriga bir xil sonli birliklarni qo'shish orqali amalga oshiriladi (o'ngdagi "*" chap tomonda). Keyin biz hamma "a" ni "x" ko'paytirish belgisiga o'zgartiramiz. Va tsikl takrorlanadi. Haqiqatan ham, A ni B ga ko'paytirganda, A + A + A B marta ifodalanishi mumkin. Endi biz 2 -omilning 2 -birligini "a" harfi bilan belgilaymiz va birliklarni yana o'tkazamiz. Agar "=" belgisidan oldin birliklar bo'lmasa, ko'paytirish tugallanadi.

Turingning to'liqligi

Aytishimiz mumkinki, Tyuring mashinasi - bu chiziqli xotiraga ega bo'lgan eng oddiy hisoblash mashinasi, u rasmiy qoidalarga muvofiq ketma -ketlik yordamida kirish ma'lumotlarini o'zgartiradi. elementar harakatlar.

Amallarning elementar xususiyati shundaki, bu harakat xotiradagi kichik ma'lumotlarni o'zgartiradi (Tyuring mashinasida faqat bitta katak) va mumkin bo'lgan harakatlar soni cheklangan. Tyuring mashinasining soddaligiga qaramay, u oddiy harakatlar ketma -ketligi yordamida hisob -kitoblarni bajaradigan boshqa har qanday mashinada hisoblash mumkin bo'lgan hamma narsani hisoblash uchun ishlatilishi mumkin. Bu mulk deyiladi to'liqlik.

Bir mashinada amalga oshirilishi mumkin bo'lgan hisoblash algoritmlarini boshqa mashinada amalga oshirish mumkinligini isbotlashning tabiiy usullaridan biri bu birinchi mashinani ikkinchisiga taqlid qilishdir.

Imitatsiya quyidagicha. Ikkinchi mashinaga kirishda birinchi mashinaning dasturining tavsifi (ishlash qoidalari) berilgan D (\ displey uslubi D) va ma'lumotlarni kiritish X (\ Displaystyle X), ular birinchi mashinaning kirish qismiga kelishi kerak edi. Bunday dasturni (ikkinchi mashinaning ishlash qoidalari) shunday ta'riflash kerakki, hisob -kitoblar natijasida birinchi mashina ma'lumotlarni kirish sifatida qabul qilsa, xuddi shunday bo'lib chiqadi. X (\ Displaystyle X).

Aytilganidek, Tyuring mashinasida bosqichma-bosqich hisoblash jarayonini qandaydir tarzda amalga oshiradigan boshqa barcha ijrochilarni simulyatsiya qilish (o'tish qoidalarini o'rnatish orqali) mumkin, bunda hisoblashning har bir bosqichi juda oddiy.

Tyuring mashinasida siz Post mashinasiga, oddiy Markov algoritmlariga va ba'zi bir algoritm yordamida kirish ma'lumotlarini chiqishga aylantiradigan oddiy kompyuterlar uchun har qanday dasturga taqlid qilishingiz mumkin. O'z navbatida, Turing mashinasini har xil mavhum ijrochilarga taqlid qilish mumkin. Bu mumkin bo'lgan ijrochilar chaqiriladi Turing tugadi(Turing tugadi).

Tyuring mashinasining ishlashini simulyatsiya qiladigan oddiy kompyuterlar uchun dasturlar mavjud. Ammo shuni ta'kidlash kerakki, bu taqlid to'liq emas, chunki Tyuring mashinasida abstrakt cheksiz lenta mavjud. Ma'lumotli cheksiz lentani cheklangan xotirali kompyuterda to'liq simulyatsiya qilish mumkin emas (kompyuterning umumiy xotirasi - RAM, qattiq disklar, har xil tashqi xotira omborlari, registrlar va protsessor keshi va boshqalar) - juda katta bo'lishi mumkin, lekin shunga qaramay, har doim cheklangan).

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.

Yarim cheksiz kamarda ishlaydigan Tyuring mashinasi

Bunday kamaytirishga misol sifatida quyidagi teoremani ko'rib chiqing: Har qanday Tyuring mashinasi uchun yarim cheksiz lentada (ya'ni bir yo'nalishda cheksiz bo'lgan lentada) ishlaydigan ekvivalent Tyuring mashinasi mavjud.

Yu.Garpovning "Avtomatika nazariyasi" kitobida keltirilgan dalilni 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 tasmasi hujayralarini o'zboshimchalik bilan raqamlaymiz, ya'ni lentadagi ma'lumotlarning yangi joylashishini aniqlaymiz:

Keyin biz hujayralarni qayta raqamlaymiz va "*" belgisi MT lug'atida yo'q deb taxmin qilamiz:

Nihoyat, biz Tyuring mashinasini shtatlar sonini ikki barobarga o'zgartirib, o'qish-yozishni o'zgartirish siljishini o'zgartiramiz, shunda bir guruh shtatlarda mashinaning ishlashi uning soyali maydonda, boshqa shtatlar guruhida ishlashiga teng bo'ladi. Mashina asl mashinada bo'lgani kabi ishlaydi. Agar MT ishlayotganda '*' belgisi paydo bo'lsa, o'qish-yozish boshi zona chegarasiga etib kelgan:

Yangi Tyuring mashinasining dastlabki holati u yoki bu zonada o'rnatiladi, bu asl tasmaning qaysi qismi asl konfiguratsiyadagi o'qish-yozish boshi bo'lganiga bog'liq. Shubhasiz, "*" chegara belgilarining chap tomonida lenta ekvivalent Tyuring mashinasida ishlatilmaydi.

Ikki o'lchovli Tyuring mashinalari

  • Langton chumoli

Shuningdek qarang

  • JFLAP avtomatlar, Tyuring mashinalari, grammatikasi platformalararo dastur simulyatori, avtomat grafikasini chizadi.