1 maruza: Algoritm va uning ta’riflari Asosiy savollar

Misol 1. Alifboda ikkita so'z birikmasini amalga oshiradigan MT tuzing. Lentadagi so'zlar *bilan ajratilgan. Dastlabki konfiguratsiya standart hisoblanadi.
MT buyruqlar tizimi quyidagicha:
Shtatda bosh o'ng belgiga o'tadi.
O'ng tarafdagi belgi o'chiriladi.
Agar birinchi so'z bo'sh bo'lsa, yulduzcha o'chiriladi.
O'ng so'z bitta belgidan chapga siljiydi.
Standart yakuniy konfiguratsiyaga o'tish.
Funktsional jadval

	a	b	*	l
				-
				-
				-
			-

Jadvaldagi chiziqlar l belgisini shtatlarda uchratib bo'lmasligini ko'rsatadi.

a / aL b / bL

O'tish sxemasi quyidagicha:

	a / aR b / bR * / * R

Standart yakuniy konfiguratsiya.
MT bo'yicha lug'at funktsiyasini hisoblash quyidagicha tushuniladi. Dastlabki konfiguratsiyada lentaga a so'zi yozilsin. Agar qiymat aniqlangan bo'lsa, unda cheklangan miqdordagi qadamlar (shomil) uchun, mashina lentaga yozilgan oxirgi konfiguratsiyaga o'tishi kerak. Aks holda, MT muddatsiz ishlashi kerak.
MT yordamida raqamlar bo'yicha arifmetik amallarning bajarilishini tasvirlash mumkin. Bu holda, raqamlar tasmada qandaydir sanoq tizimining raqamlaridan tashkil topgan alifbodagi so'zlar sifatida ko'rsatilgan va bu alifbo tarkibiga kirmaydigan maxsus belgi bilan ajratilgan, masalan, *. Eng keng tarqalgan tizim - bu bitta belgidan iborat yagona tizim. Lentadagi X raqami alifboda bir so'z bilan yozilgan (yoki qisqartirilgan) A = (1).
Agar konfiguratsiyani konfiguratsiyaga o'zgartiradigan MT bo'lsa, Turing tomonidan raqamli funktsiyani to'g'ri hisoblash mumkin (yoki oddiygina hisoblash mumkin). y, yoki aniqlanmagan vaqtda abadiy ishlaydi.
2 -misol. Yagona kodga ikkita raqam qo'shish operatsiyasi.
Dastlabki konfiguratsiya:
Yakuniy konfiguratsiya: ya'ni. qo'shilish aslida raqamni belgilashga to'g'ri keladi b raqamga a... Buning uchun birinchi 1 o'chiriladi va * 1 bilan almashtiriladi.
Bu erda MT ning funktsional jadval ko'rinishidagi tavsifi:

		*	l
			-
			-
		-

MT tavsifining yuqoridagi usullari amalda faqat oddiy algoritmlar uchun ishlatilishi mumkin murakkab tavsiflar uchun bu juda og'ir bo'ladi. Xuddi shunday, faqat oddiy funktsiyalar va superpozitsiya, ibtidoiy rekursiya va minimallashtirish operatorlari yordamida rekursiv funktsiyalarni tasvirlash juda og'ir bo'lar edi. Shuning uchun, funktsiyaning ibtidoiy yoki qisman rekursivligi boshqa funktsiyalar yordamida isbotlanadi, ularning ibtidoiy yoki qisman rekursivligi allaqachon isbotlangan.
Xuddi shunday, murakkab algoritmlar uchun Tyuring mashinalari mavjud MTlar yordamida qurilishi mumkin. Bu tartibga MT tarkibi deyiladi.
Keling, MT tuzilishining 4 asosiy usulini ta'riflaylik:
Tartibli tarkib (superpozitsiya);
Parallel kompozitsion;
Tarmoqlanish
Doimiy kompozitsion mashinalar va so'z funktsiyalarini hisoblash va alifboda A, mashina chaqirdi T hisoblash funktsiyasi. Ketma -ket kompozitsion quyidagicha tasvirlangan:

va bilan belgilanadi.
Algoritmlarning chiziqli bo'limlarini tasvirlash uchun odatda ketma -ket kompozitsiya ishlatiladi.
Mashina qurilishi mumkinligi haqidagi teoremaning isboti T, bu ikkita ixtiyoriy mashinaning ketma -ket tarkibi va yakuniy holatini dastlabki holat bilan aniqlash orqali amalga oshiriladi.
Misol 3. Bir so'zni a * a so'ziga aylantiradigan nusxa ko'chirish mashinasi va qo'shish mashinasi yordamida bir xil kodda 2 * X ko'paytirish algoritmini tuzing. Kerakli MT quyidagicha ko'rinadi:

Parallel kompozitsion mashinalar va so'z funktsiyalarini hisoblash va alifbo A va V mos ravishda, mashina deb ataladi T lug'at funktsiyasini hisoblash. Bu erda belgi MT ning parallel tarkibidagi so'zlarni ajratish uchun ishlatiladi.

va bilan ko'rsatilgan:

Aslida, ikkita MTning parallel tarkibi kirish sifatida turli alifbolarda 2 so'zdan iborat so'zni oladi va 2 so'zdan iborat so'zni chiqaradi, ya'ni. bir vaqtning o'zida va mustaqil ishlaydigan ikkita mashinani ifodalaydi.
Parallel kompozitsiyani amalga oshirish uchun ikki qavatli lentali mashina ishlatiladi. Bunga ehtiyoj, hisob -kitob o'z vaqtida ketma -ket amalga oshirilganligi va masalan, birinchi navbatda, a -dan ko'proq joy talab qilishi va b so'zini buzishi bilan bog'liq. Ikki qavatli lentali mashina quyidagicha ishlaydi: b so'zi ikkinchi qavatda qayta yoziladi va birinchi qavatda o'chiriladi, birinchi qavatda hisoblab chiqariladi, ikkinchi qavatda hisoblanadi va keyin birinchi qavatda, ehtimol siljish bilan qayta yoziladi. .
Parallel kompozitsiyani amalga oshirish uchun n ishlatilgan mashinalar n- pol tasmasi.
Ikki qavatli lentali MT buyrug'i quyidagicha yozilgan:, mos ravishda birinchi va ikkinchi qavatlarda yozilgan harflar.
Misol 4... Ikkilik sanoq sistemasida mashinalar va hisoblash funktsiyalarining parallel tarkibini amalga oshirish va a + b yagona tizimda.
Kirish so'zi :.
Keling, MT ishini buyruqlar tizimi bilan tasvirlaymiz:
B so'ziga o'ngga o'ting
B so'zini ikkinchi qavatga qayta yozish
A so'ziga qadar chapga siljiting
X ga 1 qo'shiladi.
B so'ziga o'ngga o'ting.
1 -qavatdagi ro'yxatga olish b, bir vaqtning o'zida raqamlar qo'shilishi bilan a va b.T, mos ravishda. Buyruqlar tizimiga qo'shilgan buyruqlar
Butun MT ning yakuniy holati.
Shuni ta'kidlash kerakki, barcha holatlarda algoritm boshida maxsus qiymatlar uchun dastlabki ma'lumotlarning chekini qo'yish kerak (ko'pincha 0 da); bu talabni bajarmaslik cheksiz tsiklga olib kelishi mumkin.
MT tarkibi murakkab algoritmlarni tuzishda ishlatilishi mumkin. Savol tug'iladi: har qanday algoritm MT tarkibi ko'rinishida amalga oshirilishi mumkinmi? Bu savolga javob quyidagicha berilgan Tyuring dissertatsiyasi , Cherkov tezisining analogi: har qanday algoritm Tyuring mashinalari yordamida amalga oshirilishi mumkin va aksincha, Tyuring mashinasi tomonidan amalga oshiriladigan har qanday jarayon algoritmdir.
Tyuring tezisi teorema emas, uni isbotlashning iloji yo'q, chunki unda norasmiy tushuncha bor " algoritm". Biroq, ko'p yillik matematik amaliyot bu tezisning ishonchli tasdig'idir: 50 yil davomida intuitiv ma'noda Tyuring mashinalari yordamida amalga oshirib bo'lmaydigan algoritm topilmadi.
Turing mashinasi (MT) - mavhum ijrochi (mavhum hisoblash mashinasi).
Algoritmlarning kombinatsiyasi - bu bir nechta algoritmlardan yangi algoritmlarni tuzishning o'ziga xos usullari uchun yaratilgan nom.
Kombinatsiya teoremalari algoritmlar umumiy nazariyasining muhim qismini tashkil qiladi. Tasdiqlanganidan so'ng, ular murakkab va og'ir algoritmlarning maqsadga muvofiqligini, ularni aniqlaydigan sxemalarni yozmasdan turib, yanada tekshirishga imkon beradi.
Tyuring mashinasi algoritmlarining kombinatsiyasi Tyuring mashinalarida bajariladigan operatsiyalar bilan tavsiflanadi.