1 maruza: Algoritm va uning ta’riflari Asosiy savollar

a j q i- buyruqlarning asl belgilari boshqacha bo'lishi kerak. Agar bu shart bajarilsa, mashina chaqiriladi deterministik , aks holda - noaniq ... Mashina alohida vaqtda ishlaydi.
Shunday qilib, Tyuring mashinasining har bir lahzada, uning keyingi xatti -harakatlarini aniqlash mumkin bo'lgan to'liq tavsifi quyidagilarni o'z ichiga oladi:
mashinaning ichki holati, lentaga yozilgan so'z va ma'lum bir vaqtda o'qiladigan belgi. Tyuring mashinasining to'liq holati chaqiriladi konfiguratsiya

Tyuring mashinasining ishlashi konfiguratsiyalar ketma -ketligi sifatida ifodalanishi mumkin k 1® k 2®…® k n.

Dastlabki konfiguratsiya - chapdagi bo'sh bo'lmagan belgini holatga o'qish q 1
Standart yakuniy konfiguratsiya - mashina oxirgi holatga kirdi:
Agar mashina yakuniy holatga kirgan bo'lsa, bu kirish so'ziga qo'llaniladi, agar u abadiy ishlayotgan bo'lsa, u holda mashina bu so'zga taalluqli emas.
MT - bu kirish alifbosi, davlatlar alifbosi va dasturidan 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) jadval yordamida

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

3) predikat grafigi yordamida (tepaliklar holatlar, har bir buyruq yoyga to'g'ri keladi)
Turing mashinasi dizayni:
Tyuring mashinasini yaratish - uning dasturini tuzish. 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, NS)
Misol: f (n) = n + 1 funktsiyasini hisoblaydigan Tyuring mashinasini qurish, bu erda n ikkilik tizimda berilgan.
A={0,1,a 0), Q to'plami dasturni tuzish jarayonida aniqlanadi.
Algoritm:
1. Boshni o'ta o'ng holatidan o'ta chapga siljitish
2. agar o'ta o'ng holatida mashina 0 ni o'qisa, uni 1 -katakka qo'ying va to'xtating, agar bosh 1 o'qisa, uni 0 -katakchaga qo'ying va chapga bir qadam siljiting.

2 -qadamni takrorlang

Misol: Lentaga tabiiy kasr raqami yozilgan. Bu raqamni 1 ga ko'paytiradigan Tyuring mashinasini qurish kerak. Dastlab bosh raqamning birinchi raqamini ko'rsatadi. Biz olamiz: 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> q 1	1> q 1	2> q 1	3> q 1	4> q 1
q 2	1 = q 0	2 = q 0	3 = q 0	4 = q 0	5 = q 0
					a 0
5> q 1	6> q 1	7> q 1	8> q 1	9> q 1	a 0 <="" td="" “" "”" "‘" "’";">
6 = q 0	7 = q 0	8 = q 0	9 = q 0	0<="" td="" “" "”" "‘" "’";">	1 = q 0

Umumiy fikr - boshni raqamning oxirgi raqamiga o'tkazing va agar bu raqam 9 bo'lmasa, uni bittaga ko'paytiring, aks holda uni nolga aylantiring va oldingi katakka o'ting.
Mashinalarning tarkibi:
Mashinalarning tarkibi - bu ikkita mashinaning ketma -ket bajarilishi.
T 1=(A 1, 1 -savol, P 1) T 2=(A 2, 2 -savol, P 2) 1 -savolÇ 2 -savol=Æ
Tarkibi mashinalar T 1° T 2 mashinani chaqirdi T(A, Q, NS), qaerda A=A 1È A 2; Q=(1 -savolÈ 2 -savol)\{q 10} (q 10- oxirgi holat T 1). Avtomobil T quyidagi qoidaga muvofiq ishlaydi: U- ba'zi so'zlar, T(U)=T 1° T 2(U)=T 2(T 1(U))
Teorema. Mashinalarning tarkibi T 1° T 2 mavjud.
1 -savol={q 10, q 1,…, q n}
2 -savol={q 20, q` 1 , …, q` n), keyin Q ni qurish uchun q 10 holatini olib tashlaymiz va uni qayta nomlaymiz q n +1, bu ikkinchi mashinaning boshlang'ich holatiga to'g'ri keladi va boshqa barcha holatlar q` i = q n + 1 .
Tyuring hisoblangan funktsiyalar:
F (x 1 ... x n) funktsiya deyiladi Tyuring hisoblab chiqilgan agar argumentlar qiymatlari berilganida bu funksiyaning qiymatini hisoblaydigan Tyuring mashinasi bo'lsa. F (x 1… x n) funktsiyasi natural sonlar to'plamida berilgan, lekin algoritmlar nazariyasi NÈ (0) natural sonlarning kengaytirilgan to'plamini ko'rib chiqadi.
Lentadagi f (x 1 ... x n) funktsiyasining argumentlari quyidagi so'z bilan ifodalanadi:
Har bir bahsda bu bahsning qiymatiga teng bo'lgan tayoqlar bor. Agar f funktsiyasi x 1 ... xn o'zgarmaydigan qiymatlar majmui bo'yicha aniqlangan bo'lsa, Tyuring mashinasining ishlashi natijasida qatorda yozilgan shunday tayoqlar qolishi kerak. lenta, bu to'plamdagi funktsiyaning qiymatiga teng. Agar berilgan funktsiyada f funktsiyasi aniqlanmagan bo'lsa, Tyuring mashinasi cheksiz ishlashi kerak.

Nazorat savollari
1. Аlgoritmlar turlarini ayting.
2. Hisoblashda algoritmlarning oʼrni.
3. Аlgoritmlar orqali yechiluvchi masalalarga misollar keltiring.