2-amaliy mashg’ulot: tyuring mashinasi

TYURING MASHINASINING VAZIFALARI

Algoritmlarni echishda ko‘pincha funktsiyani amalga oshirish talab qilinadi. Hisoblash uchun zanjirni yozish imkoniyatiga qarab, funktsiya algoritmik hal qilinadigan yoki hal etilmaydigan deb ataladi. Tabiiy yoki ratsional sonlar to‘plami sifatida, mashina uchun chekli N alifbosidagi so‘zlar, biz B to‘plamining ketma-ketligini ko‘rib chiqamiz - B = (0,1) ikkilik kod alifbosi doirasidagi so‘zlar. Shuningdek, hisoblash natijasi algoritm "osilib qolganda" yuzaga keladigan "aniqlanmagan" qiymatni hisobga oladi. Funktsiyani amalga oshirish uchun rasmiy tilning cheklangan alifboda mavjudligi va to‘g’ri tavsiflarni tanib olish muammosi hal qilinishi muhimdir.

QURILMA DASTURI

Turing mexanizmi uchun dasturlar jadvallar bilan formatlangan bo‘lib, unda birinchi qator va ustun tashqi alifbo belgilarini va mashinaning mumkin bo‘lgan ichki holatining qiymatlarini - ichki alifboni o‘z ichiga oladi. Jadvalli ma’lumotlar Turing mashinasi tomonidan qabul qilinadigan buyruqlardir. Muammoning yechimi shundan iboratki, katakchadagi bosh tomonidan o‘qilgan harf yuqoridagi momentni topadi va mashina boshining ichki holati buyruqlarning qaysi biri bajarilishi kerakligini belgilaydi. Xususan, bunday buyruq jadvaldagi tashqi va ichki alifbo belgilarining kesishgan joyida joylashgan.

HISOBLASH KOMPONENTLARI

Bitta aniq muammoni hal qilish uchun Tyuring mashinasini qurish uchun uning quyidagi parametrlarini aniqlash kerak.
Tashqi alifbo. Bu A belgisi bilan belgilanadigan, tashkil etuvchi elementlari harflar bilan ataladigan ba’zi chekli belgilar to‘plami. Ulardan biri - a0 - bo‘sh bo‘lishi kerak. Masalan, Tyuring qurilmasi bilan ishlaydigan alifbo ikkilik raqamlar, quyidagicha ko‘rinadi: A = (0, 1, a0).
Lentaga yozib olingan harf-ramzlarning uzilmagan qatori so‘z deyiladi.
Avtomat - bu inson aralashuvisiz ishlaydigan qurilma. Turing mashinasida u muammolarni hal qilish uchun bir necha xil holatlarga ega va yuzaga keladigan muayyan sharoitlarda bir pozitsiyadan ikkinchisiga o‘tadi. Bunday tashish holatlarining to‘plami ichki alifbodir. U Q = (q1, q2 ...) ko‘rinishidagi harf belgisiga ega. Ushbu pozitsiyalardan biri - q1 - boshlang’ich bo‘lishi kerak, ya’ni dasturni ishga tushiradigan narsa. Yana bir zarur element - bu yakuniy, ya’ni dasturni tugatuvchi va qurilmani to‘xtash holatiga keltiradigan q0 holat.
O‘tish stoli. Ushbu komponent mashinaning holati va hozirgi vaqtda o‘qilayotgan belgining qiymatiga qarab, qurilma vagonining xatti-harakati uchun algoritmdir.