Tyuring mashinasining ishlashi

Tyuring mashinasining ta'rifi, ishlashi va aniqlash usullari
Tyuring mashinasi deganda quyidagi qismlardan tashkil topgan qandaydir faraziy (mavhum) mashina tushuniladi (3.1-rasm).
1) har ikki yo'nalishdagi cheksiz lenta, hujayralarga bo'lingan, ularning har biri alifbodan faqat bitta belgini, shuningdek bo'sh belgini o'z ichiga olishi mumkin l;
2) boshqaruv moslamasi (ishchi bosh), u istalgan vaqtda to'plamdagi holatlardan birida bo'lishi mumkin. Har bir shtatda bosh hujayraning qarshisida joylashgan bo'lib, unga alifbodan harfni o'qishi (ko'rishi) yoki yozishi mumkin. LEKIN.

Guruch. 3.1. Tyuring mashinasi

MT ning ishlashi elementar bosqichlar (tsikllar) ketma-ketligidan iborat. Har bir qadam quyidagi amallarni bajaradi:
1. ishchi bosh personajni o‘qiydi (ko‘radi);
2. Uning holatiga va kuzatilgan belgiga qarab, bosh belgi hosil qiladi va uni kuzatilgan hujayraga yozadi (ehtimol =);
3. bosh bir hujayrani o'ngga siljitadi (R), chap (L) yoki joyida qoling (E);
4. Bosh boshqa ichki holatga kiradi. (ehtimol =).
Davlat boshlang'ich, - yakuniy deb ataladi. Yakuniy holatga kirganda, mashina to'xtaydi.
MTning to'liq holati deyiladi konfiguratsiya . Bu lenta hujayralarida harflarning taqsimlanishi, ishchi boshning holati va kuzatilgan hujayra. Konfiguratsiya nozik t quyidagicha yoziladi: , bu yerda kuzatilayotgan yacheykaning chap tomonidagi pastki so‘z, kuzatilayotgan katakchadagi harf, o‘ngdagi pastki so‘z.
Dastlabki konfiguratsiya va yakuniy standart deb ataladi.
MT ishini tavsiflashning 3 ta usuli mavjud:
Buyruqlar tizimini ko'rish
Funktsiyalar jadvali;
O'tishlarning grafigi (diagrammasi).
Keling, ularni misollar bilan ko'rib chiqaylik.
1-misol Alifbodagi ikki so'zning birikishini amalga oshiruvchi MT tuzing. Lentadagi so'zlar * belgisi bilan ajratiladi. Dastlabki konfiguratsiya standartdir.
MT buyruqlar tizimi quyidagi shaklga ega:
Davlatda bosh bo'sh belgiga o'ngga o'tadi.
Eng o'ngdagi belgi o'chiriladi.
Agar birinchi so'z bo'sh bo'lsa, yulduzcha o'chiriladi.
To'g'ri so'z har bir belgi bilan bir pozitsiya belgisi bilan chapga siljiydi.
Standart maqsadli konfiguratsiyaga o'tish.
Funktsiyalar jadvali

	a	b	*	l
				-
				-
				-
			-

Jadvaldagi chiziqlar l ni shtatlarda uchratish mumkin emasligini bildiradi.

a/aL b/bL

O'tish diagrammasi quyidagicha ko'rinadi:

	a/aR b/bR */*R

Yakuniy standart konfiguratsiya.

MT da lug'at funksiyasini hisoblash quyidagicha tushuniladi. Dastlabki konfiguratsiyada lentaga a so'zi yozilsin. Agar qiymat aniqlangan bo'lsa, u holda cheklangan miqdordagi qadamlardan (tsikllardan) so'ng, mashina so'z lentada yozilgan oxirgi konfiguratsiyaga o'tishi kerak. Aks holda, MT cheksiz ishlashi kerak.
MT dan foydalanib, raqamlar ustidagi arifmetik amallarning bajarilishini tavsiflash mumkin. Bunda raqamlar lentada qandaydir sanoq sistemasining raqamlaridan tashkil topgan alifbodagi so'zlar sifatida taqdim etiladi va bu alifboga kiritilmagan maxsus belgi bilan ajratiladi, masalan, *. Eng ko'p qo'llaniladigan tizim -1 belgisidan iborat unary tizimdir. Lentadagi X raqami so'zda, (yoki qisqartirilgan) alifboda yozilgan A=(1).
Raqamli funktsiya Tyuring ma'nosida to'g'ri hisoblash mumkin (yoki oddiygina hisoblash mumkin), agar konfiguratsiyani konfiguratsiyaga o'tkazadigan MT mavjud bo'lsa, = y, yoki aniqlanmagan hollarda cheksiz ishlaydi.
2-misol Unar kodda ikkita raqamni qo'shish amali.
Dastlabki konfiguratsiya:
Yakuniy konfiguratsiya: ya'ni. qo'shish aslida raqamni tayinlash bilan bog'liq b raqamga a. Buning uchun birinchi 1 o'chiriladi va * 1 bilan almashtiriladi.
Biz MT ning tavsifini funktsional jadval shaklida beramiz:

		*	l
			-
			-
		-

MTni tavsiflashning yuqoridagi usullari amalda faqat oddiy algoritmlar uchun ishlatilishi mumkin, chunki chunki murakkab ta'riflar juda og'ir bo'ladi. Xuddi shunday, rekursiv funktsiyalarni faqat eng oddiy funksiyalar va superpozitsiya, ibtidoiy rekursiya va minimallashtirish operatorlari bilan tavsiflash juda mashaqqatli bo'lar edi. Shuning uchun funktsiyaning ibtidoiy yoki qisman rekursivligi ibtidoiy yoki qisman rekursivligi isbotlangan boshqa funksiyalar yordamida isbotlanadi.
Xuddi shunday murakkab algoritmlar uchun Tyuring mashinalari mavjud MT yordamida tuzilishi mumkin. Bunday qurilish MT tarkibi deb ataladi.
Keling, MT tarkibining 4 asosiy usulini tavsiflaymiz:
Ketma-ket kompozitsiya (superpozitsiya);
Parallel kompozitsiya;
Tarmoqlanish
Barqaror kompozitsiya lug'at funktsiyalarini hisoblaydigan mashinalar va alifboda LEKIN, mashina deb ataladi T, bu funktsiyani hisoblaydi. Ketma-ket kompozitsiya quyidagicha tasvirlangan:

va belgilanadi.

Algoritmlarning chiziqli bo'limlarini tasvirlash uchun odatda ketma-ket kompozitsiyadan foydalaniladi.
Mashina yasash imkoniyati haqidagi teoremani isbotlash T, bu ikkita ixtiyoriy mashinaning ketma-ket tarkibi bo'lib, yakuniy holatni dastlabki holat bilan aniqlash orqali amalga oshiriladi.
3-misol a so‘zini a*a so‘ziga va qo‘shish mashinasiga aylantiruvchi nusxa ko‘chirish mashinasi yordamida unar kodda 2*X ko‘paytirish algoritmini tuzing. Istalgan MT quyidagicha ko'rinadi:


Parallel kompozitsiya lug'at funktsiyalarini hisoblaydigan mashinalar va alifbolarda LEKIN va DA mos ravishda, mashinaning nomi T, lug'at funktsiyasini hisoblab chiqadi. Bu erda belgi parallel MT tarkibidagi so'zlarni ajratish uchun ishlatiladi.

va belgilangan: .

Aslida, ikkita MTning parallel tarkibi turli alifbolardagi 2 so'zdan iborat so'zni kirish sifatida qabul qiladi va 2 so'zdan iborat so'zni chiqaradi, ya'ni. bir vaqtning o'zida va mustaqil ishlaydigan ikkita mashinadan iborat.
Parallel kompozitsiyani amalga oshirish uchun ikki qavatli lentali mashina ishlatiladi. Buning zarurati va hisoblashning vaqt ichida ketma-ket sodir bo'lishi va hisoblangan, masalan, birinchi navbatda, a dan ko'ra ko'proq joy talab qilishi va b so'zini buzishi mumkin. Ikki qavatli lenta mashinasi shunday ishlaydi: b so'zi ikkinchi qavatga qayta yoziladi va birinchi qavatda o'chiriladi, birinchi qavatda hisoblab chiqiladi, ikkinchi qavatda hisoblab chiqiladi va keyin birinchi qavatga qayta yoziladi, ehtimol shift bilan. .
Parallel kompozitsiyani amalga oshirish uchun n ishlatiladigan mashinalar n– pol lentasi.
Ikki qavatli lenta bilan MT jamoasi quyidagicha yoziladi:, qayerda navbati bilan birinchi va ikkinchi qavatlarda yozilgan harflar.
4-misol. Mashinalarning parallel tarkibini amalga oshirish va , ikkilik tizimda hisoblash funktsiyalari va a+b unar sistemada.
Kiritilgan so'z quyidagi shaklga ega: .
MT ning ishlashini buyruqlar tizimi bilan tavsiflaymiz:
So'zni o'ngga siljitish b
b so'zini ikkinchi qavatga qayta yozish
A so‘ziga chapga siljiting
X ga 1 qo'shish.
So'zni o'ngga siljitish b.
Bir vaqtning o'zida raqamlar qo'shilishi bilan b 1-qavatgacha aholini ro'yxatga olish a va b.T mos ravishda. Buyruqlar tizimiga jingalak qavs ichidagi buyruqlar qo'shilgan
Butun MTning yakuniy holati.
Shuni ta'kidlash kerakki, barcha holatlarda, algoritm boshida, maxsus qiymatlar uchun dastlabki ma'lumotlarning tekshiruvini kiritish kerak (ko'pincha 0 uchun), bu talabga rioya qilmaslik pastadirga olib kelishi mumkin. .
MT tarkibi murakkab algoritmlarni qurish uchun ishlatilishi mumkin. Savol tug'iladi: har qanday algoritmni MT tarkibi sifatida amalga oshirish mumkinmi? Bu savolga javob Tyuring dissertatsiyasi , Cherkov tezisining analogi: har qanday algoritm Tyuring mashinalari yordamida amalga oshirilishi mumkin va aksincha, Tyuring mashinasi tomonidan amalga oshirilgan har qanday jarayon algoritmdir.
Tyuring tezisi teorema emas, uni isbotlash mumkin emas, chunki unda norasmiy tushuncha mavjud " algoritm". Biroq, uzoq muddatli matematik amaliyot bu tezisning ishonchli tasdig'idir: 50 yil davomida Tyuring mashinalari yordamida amalga oshirib bo'lmaydigan intuitiv ma'noda hech qanday algoritm topilmadi.
Tyuring mashinasi (MT) mavhum bajaruvchi (mavhum hisoblash mashinasi).
Algoritm birikmalari - bu bir nechta berilganlardan yangi algoritmlarni qurishning bir qancha maxsus usullariga berilgan nom.
Algoritmlar birikmalari haqidagi teoremalar algoritmlarning umumiy nazariyasining muhim qismini tashkil qiladi. Bir marta isbotlangan bo'lsa, ular kelajakda ularni aniqlaydigan sxemalarni yozmasdan murakkab va noqulay algoritmlarning maqsadga muvofiqligiga ishonch hosil qilish imkonini beradi.
Tyuring mashinasi uchun algoritmlarning kombinatsiyasi Tyuring mashinalaridagi operatsiyalar bilan tavsiflanadi.