1 maruza: Algoritm va uning ta’riflari Asosiy savollar

Tyuring mashinalarining tarkibi

Ta'rif 6.1: Turing mashinalari mos ravishda umumiy tashqi alifbo (,…,) va ichki holat alifbosi (,…,) va (, ...,) ga ega bo'lsin. Mashinaga mo'ljallangan mashinaning tarkibi (yoki mahsuloti) - xuddi shunday tashqi alifbosi (,…,), ichki alifbosi (,…, ...,) va quyidagicha olingan dasturga ega bo'lgan yangi mashina. To'xtash belgisini o'z ichiga olgan barcha buyruqlarda oxirgi buyruq bilan almashtiring. Buyruqlaridagi boshqa barcha belgilar o'zgarishsiz qoladi. Buyruqlarida belgi o'zgarmaydi va boshqa barcha holatlar (i = 1, ..., t) mos ravishda o'zgartiriladi. Shu tarzda olingan barcha buyruqlar yig'indisi kompozitsion mashinaning dasturini tashkil qiladi.
Taqdim etilgan kontseptsiya Tyuring mashinalarini yaratish uchun qulay vositadir. Buni misol bilan ko'rsataylik.
Misol 6.1. Keling, (,…,) = (1? M? N) funktsiyalarini to'g'ri hisoblaydigan Tyuring mashinalarini tuzaylik.
Keling, n = 3, m = 2 aniq holatini ko'rib chiqaylik, ya'ni. funktsiya (,) =. Biz 0 so'zini 0 so'ziga aylantirishimiz kerak. Biz dastlabki konfiguratsiyaga avvaldan tuzilgan Turing mashinalari B, O:
Shunday qilib, (,) = funktsiyasi mashinalarning quyidagi tarkibi bilan hisoblanadi: BOO = B.
Endi biz (,…,) = shaklning har qanday funktsiyasini hisoblash uchun mashinalar kompozitsiyasini qurish uchun B, O algoritmini tasavvur qilishimiz mumkin. O'ng siljish bilan, uni m-1 marta qo'llaganingizda, birinchi navbatda qatorga kirishingiz kerak:
So'ngra, chapga siljish, qatorni yuqoriga chiqmaguncha, har bir qatorni chapga ulashgan holda (B yordamida) o'tkazing:
Endi siz (n -1) yordamida o'ngdagi eng o'ng qatorga o'tishingiz kerak - bir nechta o'ng siljish:
Nihoyat, o'ngdan chapga ketma -ket, birinchisidan tashqari, barcha qatorlarni o'chirish kerak:
Shunday qilib, bu funktsiyani (to'g'ri) quyidagi Tyuring mashinasi hisoblab chiqadi.
Tyuring mashinasining ta'rifi, ishlashi va aniqlash usullari
Tyuring mashinasi deganda quyidagi qismlardan tashkil topgan gipotetik (mavhum) mashina tushuniladi (3.1 -rasm).
1) har ikki yo'nalishda ham, hujayralarga bo'linadigan, cheksiz lenta, ularning har birida alifbodan faqat bitta belgi, shuningdek bo'sh l belgisi bo'lishi mumkin;
2) boshqaruv moslamasi (ishchi bosh), u har qanday vaqtda majmuadagi holatlardan birida bo'lishi mumkin. Har bir shtatda bosh hujayraning qarshisida joylashgan va unga alifbodan harf o'qish (ko'rish) yoki yozish mumkin. A.

Guruch. 3.1. Tyuring mashinasi
MTning ishlashi elementar qadamlar ketma -ketligidan (soat tsikllari) iborat. Har bir bosqichda quyidagi harakatlar bajariladi:
1. ishlaydigan bosh belgini o'qiydi (ko'radi);
2. uning holatiga va kuzatiladigan belgiga qarab, bosh simvol hosil qiladi va uni kuzatiladigan katakka yozadi (ehtimol =);
3. bosh bitta hujayrani o'ngga siljitadi (R), chapda (L) yoki joyida qoladi (E);
4. bosh boshqa ichki holatga o'tadi. (ehtimol =).
Shtat boshlang'ich, yakuniy deb nomlanadi. Oxirgi holatga kirganda, mashina to'xtaydi.
MT ning to'liq holati deyiladi konfiguratsiya ... Bu lentaning kataklaridagi harflarning taqsimlanishi, ishchi boshning holati va ko'rilayotgan katak. Har bir soat uchun konfiguratsiya t shaklida yoziladi :, bu erda kuzatiladigan katakchaning chap tomonidagi pastki so'z, kuzatilgan katakdagi harf, o'ngdagi pastki so'z.
Dastlabki va oxirgi konfiguratsiya standart deb ataladi.
MT ishini tasvirlashning 3 usuli mavjud:
Shakl buyruqlar tizimi
Funktsional jadval;
O'tishlarning grafigi (diagrammasi).
Keling, ularni misollar bilan ko'rib chiqaylik.