Tyuring mashinasining ishlashi

Tyuring mashinasining ishlashi:
Algoritmning uchta asosiy tushunchasidan ikkinchi ta'rifi mashina matematikasi bilan bog'liq. Algoritm har qanday vaqtda eng oddiy operatsiyalarni bajarishga qodir bo'lgan eng oddiy deterministik qurilma sifatida qaraladi. Asosiy model Tyuring mashinasidir.
Turing mashinasi uchta alifbo bilan ishlaydi:
1. alifboni kiritish LEKIN={a 0…a n), uning yordamida kirish, oraliq, chiqish ma'lumotlari yoziladi. a 0- bo'sh belgi (ahamiyatsiz nol, Ù, DA, #), a 1– 1 yoki |
2. ichki alifbo yoki davlatlar alifbosi Q={q0…q m}, q0- yakuniy holat q 1- boshlang'ich holati q 0 …q n- ish holati
3. alifboni siljitish (L, V, N) yoki (-1, +1, 0) (chap, o'ng, joyida)
Turing mashinasi quyidagi qismlardan iborat:
1) lenta, har ikki yo'nalishda ham potentsial cheksiz. Potensial cheksizlik deganda, vaqtning har bir lahzasida lentaga chekli so'z yozilishini anglatadi, ammo kerak bo'lganda, so'zning chap va o'ng tomonida kerakli hujayralar soni to'ldirilishi mumkin. Lenta hujayralarga bo'lingan, ularning har biri kirish alifbosining faqat bitta belgisini o'z ichiga oladi. Bo'sh katakchalarga bo'sh belgi yoziladi. Agar hujayradagi ma'lumotni o'chirish kerak bo'lsa, unga bo'sh belgi yozish kifoya.
2) nazorat qilish qurilmasi(UU), bu dastur yordamida Turing mashinasini boshqaradi. CU istalgan vaqtda faqat alifbo davlatlaridan birida bo'lishi mumkin Q.
3) bosh(o'quvchi va yozuvchi) har bir vaqtning har bir daqiqasida quyidagi harakatlarni bajaradi
katakka yozilgan belgini o‘qiydi
uni alifboning boshqa belgisi bilan almashtiradi LEKIN yoki xuddi shunday qoldiring
lenta bo'ylab o'ngga, chapga bitta katakka siljiydi yoki joyida qoladi
Tyuring mashinasi qoidasi:
Turing mashinasi, holatda bo'lish q i va xarakterni o'qish aj, bu katakka belgi yozadi a k, davlatga kiradi q e, siljishni amalga oshiradi. Shu bilan birga, ular mashina bitta buyruqni bajarganligini aytishadi: a j q i® a k q e S SO(L, P, N)
Buyruqlar majmuasi MT dasturi deb ataladi.
a j q i- buyruqlarning boshlang'ich belgilari boshqacha bo'lishi kerak. Agar bu shart bajarilsa, mashina chaqiriladi deterministik , aks holda - deterministik bo'lmagan . Mashina alohida vaqtlarda ishlaydi.
Shunday qilib, har bir daqiqada Tyuring mashinasining to'liq tavsifi, uning keyingi xatti-harakatlarini aniqlash mumkin bo'lgan ma'lumotlar quyidagilardan iborat:
mashina joylashgan ichki holat, lentaga yozilgan so'z va ma'lum bir vaqtda o'qiladigan belgi. Turing mashinasining to'liq holati chaqiriladi konfiguratsiya.

Turing mashinasining ishlashini konfiguratsiyalar ketma-ketligi sifatida ko'rsatish mumkin k 1® k2®…® k n.

Standart dastlabki konfiguratsiya eng chap bo'sh bo'lmagan belgini holatga o'qishdir q 1
Standart yakuniy konfiguratsiya - mashina yakuniy holatga kirdi:
Agar mashina yakuniy holatga kelgan bo'lsa, u berilgan kirish so'ziga tegishli bo'ladi, agar u cheksiz ishlasa, u holda mashina berilgan so'zga taalluqli emas.
MT - kirish alifbosi, holatlar alifbosi va dasturdan iborat to'plam. M= . A - kirish alifbosi Q - ichki alifbo P - dastur
Mashina dasturini quyidagicha sozlash mumkin:
1) buyruqlar ro'yxati: a j q i® a k q n S
2) jadvaldan foydalanish

	a 0	a 1	a 2
q0	a k, q m, S
q 1

3) predikat grafigi yordamida (cho'qqilar - holatlar, har bir buyruq yoyga to'g'ri keladi)
Turing mashinalarini loyihalash:
Turing mashinasini loyihalash - uning dasturini yaratish. U ikki bosqichda amalga oshiriladi:
1) hal qilinayotgan masala algoritmining og'zaki tavsifi
2) algoritmning og'zaki tavsifini Tyuring mashinasi tiliga tarjima qilish (buning uchun, A, Q, P)
Misol: f(n)=n+1 funksiyani baholovchi Tyuring mashinasini tuzing, bunda n ikkilik tizimda berilgan.
LEKIN={0,1,a 0), Q to'plami dasturni qurish jarayonida aniqlanadi.
Algoritm:
1. boshni o'ta o'ng holatdan o'ta chapga siljiting
2. Agar mashina o'ta o'ng holatda 0 ni o'qisa, uni 1-kameraga qo'ying va to'xtating, agar bosh 1 ni o'qisa, uni 0-hujayraga qo'ying va bir qadam chapga siljiting.

2-bosqichni takrorlang

Misol: Lentaga natural o'nlik son yoziladi. Bu raqamni 1 ga oshiradigan Tyuring mashinasini qurish kerak. Dastlab, bosh raqamning birinchi raqamiga ishora qiladi. Biz quyidagilarga ega bo'lamiz: A = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a 0 ), Q = (q 1 , q 2 , q 0 ). P - jadvalga qarang.

q 1	0>q1	1>q1	2>q1	3>q1	4>q1
q2	1=q0	2=q0	3=q0	4=q0	5=q0
					a 0
5>q1	6>q1	7>q1	8>q1	9>q1	a 0 <="" td="" >
6=q0	7=q0	8=q0	9=q0	0<="" td="" >	1=q0

Umumiy fikr - boshni raqamning oxirgi raqamiga o'tkazing va agar bu raqam 9 bo'lmasa, uni bittaga oshiring, aks holda uni nolga aylantiring va oldingi katakka o'ting.
Mashinalarning tarkibi:
Mashina tarkibi - ikkita mashinaning ketma-ket bajarilishi.
T 1=(A 1, 1-savol, P 1) T 2=(A2, 2-savol, P 2) 1-savolÇ 2-savol=Æ
Tarkibi mashinalar T 1° T 2 mashinani chaqirdi T(A, Q, P), qayerda LEKIN=A 1È A2; Q=(1-savolÈ 2-savol)\{q 10} (q 10- yakuniy holat T 1). Mashina T quyidagi qoidaga muvofiq ishlaydi: U- bir so'z T(U)=T 1° T 2(U)=T 2(T 1(U))