Algoritm tushunchasi qadimdan shakllanib kelgan.Zamonaviy odam algoritm deganda muayan tartibda ayrim amallarni biror berilgan sinf uchun masalalarni yechishga bajarilishining yuriqnomalarning aniq tizimini tushunadi. Juda ko’p lgoritmlarning turlari bizni hayotimizning turli javhalarida uchraydi.
Algoritmlarning ko’p misollari bilan boshlang’ich sinflardan boshlab to’qnashamiz. Avval bu turli sonlar ustida to’rta arifmetik amallarni bajarilishi, natural, butun, kasr, kompleks sonlar ustida shunday amallarni bajarilishi.Mashhur alforitmlad Evklid algoritmi, ikkita natural sonlarning eng kata umumiy b’luchisini toppish, turli tartibli determinantlarni echish, ratsional lementli matritsalarning ranglarinin hisoblash, tenlamalarning taqribiy echimlarinin toppish.v.h.z. ХХ asrning boshida olimlar ba’zi masalalar algoritmik echimga ega bo’lmasligini aniqlashdi. Algoritmning mavjud emasligini aniqlash uchun uning ta’rifini aniq bilish kerak deb aniqlandi. 1936–1937 y.y. A.Tyuring,E.Post, K.Gedel, A.A.Markov,, A.Chorch. tomonidan algoritmning mavjud bo’lishi haqida ta’riflar keltirildi, ularni bir biriga teng kuchli ta’riflar ekanligini aniqlashidi va ular bitta tushunchani aniqlashganini belgilashdi.
Tyuring mahinasi. Tyuring mashinasi bu matematik tasavvur etiladigan mashina bo’lib, fizik mashina eas. U funktsiya, integral v.h.z. kabi bitta tushunchadir.Bu mashina real jarayonlarni modellashtiradi.
Tyuring Mashinasi lenta, boshqaruvchi qurilma va sanashni qayd etuvchi uchidan iborat.
Lenta hujayralarga bo'linadi. Vaqtning har bir lahzasidagi har bir katakka tashqi alfavitdan A = {a0, a1, ... an-1}, n 2. aniq bir belgi kiradi, A alifbosining ba'zi bir belgisi bo'sh, shu payt bo'sh belgi bo'lgan har qanday katak bo'sh deb nomlanadi. hujayra. Keyinchalik, tashqi alifbo sifatida A = {0,1} dan foydalanamiz, bu erda 0 (nol) ni bo'sh belgi sifatida ishlatamiz. Vaqtning har bir lahzasida lentada sonli kataklar mavjud, ammo mashinaning ishlashi paytida bo'sh hujayrada yangi katakchalar qo'shilishi mumkin.
Vaqtning har bir lahzasida boshqarish moslamasi Q {q0, q1,…, qr-1}, r to'plamiga tegishli qi holatini topadi 1. Q to'plam ichki alfavit deb ataladi. Keyinchalik, dastlabki holat q1 bilan, oxirgi holat q0 bilan belgilanadi.
O'qish boshi lenta bo'ylab harakatlanadi, shunda u bir vaqtning o'zida bitta lenta katakchasiga qaraydi. Bosh nazorat ostidagi hujayraning tarkibini o'qishi va unga tashqi alifbodan yangi belgi yozilishi mumkin.
Tyuring mashinasining ishlashi dastur asosida aniqlanadi. Dastur buyruqlardan iborat. Har bir buyruq quyidagilardan biridir:
1. qi aj →qk ae
2. qi aj →qk ae R
3. qi aj →qk ae L
1-buyruq shundan iboratki, lentada ko'rilgan hujayraning aj tarkibi o'chiriladi va uning o'rniga ae belgisi qo'shiladi (bu aj bilan mos tushishi mumkin), mashina yangi holatga o'tadi qk (u avvalgi holatiga to'g'ri kelishi mumkin).
Buyruq 2 xuddi shu buyruq bilan ishlaydi va qo'shimcha ravishda o'qilgan boshni qo'shni katakka o'ng tomonga siljitadi.
3-buyruq 1-buyruqqa o'xshash ishlaydi va qo'shimcha ravishda o'qilgan boshni qo'shni katakchaga chap tomonga siljitadi.
Agar o'qish boshi lentaning o'ng tomonida (chapda) joylashgan bo'lsa va u o'ngga (chapga) harakatlansa, u holda bo'sh joyga lentaga yangi katak biriktiriladi.
Mashina so'zi yoki konfiguratsiya - bu shakl so'zi
1-buyruq shundan iboratki, lentada ko'rilgan hujayraning aj tarkibi o'chiriladi va uning o'rniga ae belgisi qo'shiladi (bu aj bilan mos tushishi mumkin), mashina yangi holatga o'tadi qk (u avvalgi holatiga to'g'ri kelishi mumkin).
Buyruq 2 xuddi shu buyruq bilan ishlaydi va qo'shimcha ravishda o'qilgan boshni qo'shni katakka o'ng tomonga siljitadi.
3-buyruq 1-buyruqqa o'xshash ishlaydi va qo'shimcha ravishda o'qilgan boshni qo'shni katakchaga chap tomonga siljitadi.
Agar o'qish boshi lentaning o'ng tomonida (chapda) joylashgan bo'lsa va u o'ngga (chapga) harakatlansa, u holda bo'sh joyga lentaga yangi katak biriktiriladi.
Mashina so'zi yoki konfiguratsiya - bu shakl so'zi
Ai1,ai2,…,qkait,…, aik,
Bu yerda аij А, qk Q.
ok simvoli qirqiladigan yacheyka oldida yoziladi.Bunda qk simvoli eng chapki bo’lishi mumkin, o’ng bo’la olmaydi. Quyida gi belgilarni qo’llaymiz, bunda b quyidagini belgilashi mumkin, so’z аi аi …аi =
Masalan, 13=10212 konfiguratsiya lentada quyidagi ko’rinishga ega:
▼q1
Agar Turing mashinasi berilgan bo'lsa, unda dastur, tashqi va ichki alifbolar ko'rsatilgan bo'lsa va qaysi belgilar boshlang'ich va yakuniy holatni ko'rsatsa. Agar Turing mashinasi oxirgi holatga kelsa, u holda u to'xtatilgan deb nomlanadi.
Agar Turing mashinasi oxirgi holatga kelsa, u holda u to'xtatilgan deb nomlanadi.
Turing mashinasi biron bir (boshlang'ich) daqiqada ishlay boshlasin. Lentada shu daqiqada yozilgan so'z boshlang'ich so'z deb nomlanadi. Tyuring mashinasi ishlay boshlashi uchun o'qish boshini lentadagi har qanday katakchaga qo'yib, Tyuring mashinasining hozirgi holatini ko'rsatish kerak.
Agar P boshlang'ich so'z bo'lsa, unda Turing mashinasi "so'z" ustida ish boshlagan holda, ma'lum bir qator qadamlardan so'ng to'xtaydi yoki hech qachon to'xtamaydi. Birinchi holda, Turing mashinasi P so'ziga taalluqli deyiladi va mashinani P so'ziga qo'llash natijasi yakuniy konfiguratsiyaga mos keladigan M so'zidir.
Ikkinchi holda, mashina R so'ziga taalluqli emasligi aytiladi.
1-misol: Quyidagi dastur tomonidan berilgan Turing mashinasi qo'llanilishini aniqlang
Q10→ q20 R, q11→ q11 R, q20→ q30 R, q21→ q11 L, q30→ q00 , q31→ q21 R, к слову
Р= q1 130212.
▼q1
q11→ q11 R 13 q10212
▼q2
q10→ q20 R 130 q2012
▼q3
q20→ q30 R 1302 q312
▼q2
q31→ q21 R 13021 q21
▼q1
q21→ q11 L 1302 q112
▼q1
q11→ q11 R 130212 q10
▼q2
q10→ q20 R 130212 0q20
▼q3
q20→ q30 R 130212 02q30
▼q0
q30→ q00 130212 02q00
Shuning uchun, bu Turing mashinasi P so'ziga taalluqlidir va yakuniy konfiguratsiya: 13021202q00.
Shundan so'ng M M yozuvi Turing mashinasi (T) cheklangan sonli tsikldan so'ng M mashina so'zini M1 mashina so'ziga aylantiradi degan ma'noni anglatadi.
Agar funktsiyani hisoblaydigan Turing mashinasi bo'lsa, funktsiya Turing computable deb nomlanadi.
Birinchidan, biz qisman raqamli funktsiyalar haqida gapirayotganimizni eslaymiz. Ikkinchidan, lentadagi f (x1, x2 ... xn) funktsiyasining argumentlarining x1, x2 ... x qiymatlari quyidagicha yozilishiga rozilik bildiramiz:
yoki .
Biz ushbu so'zni standart holatdan, ya'ni q1 holatida tasvirlangan so'zning eng o'ng birligi kuzatiladigan joydan qayta ishlashni boshlaymiz. Agar berilgan argument qiymatlari to'plamida F (X1, x 2 ... xN) funktsiyasi aniqlangan bo'lsa, natijada tasmaga F (X1, x 2 ... xN) birliklari ketma-ket yozilishi kerak, aks holda mashina cheksiz ishlashi kerak. Agar yuqoridagi barcha shartlar bajarilsa, biz Turing mashinasi berilgan F funktsiyasini hisoblab chiqadi deb aytamiz.
2-misol: O (x) = 0 funktsiyasini hisoblaydigan Turing mashinasini yarating. Buning uchun q101 so'zidan (x - har qanday tabiiy son) ishlay boshlagan va lentada hech kim yo'q bo'lganda to'xtaydigan Turing mashinasini (T), (ya'ni dastur tuzish) qurish kerak. q101 => q 0
Ushbu dastur quyidagicha ko'rinadi:
Q10à q20R
Q20 à q0O
Q21à q20R
3-misol: F (X, y) = X + y funktsiyani hisoblab chiqadigan Turing mashinasini yarating. q101 01 so'zidan boshlab X + y birliklarida tasmada turganida q 01 01 =>q 01 da to'xtaydigan Turing mashinasini (T) yarataylik.
Q10 à q20R q2 0
Q 0 à q OR q 0
Q 1à q 1 q 0
Q 1 à q 1R Q 01
Q 0 à Q 1 Q 1
Q 1 à q 1L q 01
Q 0 à q 0R q 1
Q5 1à q 0 q 01
4-misol: F (X) = 2 / X funktsiyasini hisoblaydigan Turing mashinasini yarating. Ushbu funktsiya hamma joyda aniqlanmagan. Faqat X = 1, X = 2 bo'lganda, uning qiymatlari mos ravishda 2 va 1 natural sonlardir. Shuning uchun q101 so'zi bilan ishlay boshlaydigan yoki lentada mos ravishda bitta birlik bo'lgan ikkita qitish bo'lganida q1012 to'xtab turadigan Turing mashinasini qurish mumkin. Boshqa hollarda, mashina q2 (X ≠ 1, X ≠ 2) so'zlaridan ishlay boshlaydi. Bunday mashina quyidagi dastur tomonidan o'rnatiladi:
:
Q 0 à q 0R q
Q 0 à q 0
Q 1 à q 1R 1 q 1
Q 0 à q 1L q ,
Q 1 à q 1R q 1
Q 1 à q 1
Q40 à q50L 1 q51
Q51 à q00L q01,
Takroriy funktsiyalar. Keyinchalik, N natural sonlar to'plami deganda biz N = {0,1,2,…, K,…} to'plamini tushunamiz.
Y = F (X1, X2,…, Xn) N o'zgaruvchilar funktsiyasi bo'lsin. Biz D (Y) - Y = F (X1, X2, ..., Xn) funktsiyani aniqlanish sohasi E (Y) - Y = F (X1, X2, ..., Xn) funktsiya sohasini belgilaymiz.
Funksiya Y = F (X1, X2,…, Xn) Agar raqamli funktsiya deyiladi, agar:
1) D(Y)=N ×∙ N ∙× …×∙ N = ;
2) E(Y) N
|
