Tyuring mashinasining ishlashi

5.2-misol. Ikkita mashinani "chapga siljish" va "o'ngga siljish" yasang. Dastlabki standart pozitsiyadan birinchisi 0 so'zini xuddi shu so'zga aylantiradi va to'xtab, eng chap katakchaga nol bilan qaraydi. Chap katak nolga teng bo'lgan dastlabki holatdan ikkinchi mashina 0 so'zini xuddi shu so'zga qayta ishlaydi va to'xtab, eng o'ngdagi katakchani nol bilan ko'radi.
Mashina dasturi: 0 > 0L, 1 > 1L, 0 > 0. Mashina dasturi oldingi mashina dasturidan «L» belgisini «P» belgisiga almashtirish orqali olinganligi aniq.
Tyuring mashinalarining tarkibi
Ta'rif 6.1: Tyuring mashinalari umumiy tashqi alifboga (, …,) va ichki holat alifbolariga (, …,) va (, …, ) ega boʻlsin. Mashina uchun mashinaning tarkibi (yoki mahsuloti) bir xil tashqi alifbo (, ...,), ichki alifbo (, ..., ..., ) va quyidagi tarzda olingan dasturga ega bo'lgan yangi mashinadir. To'xtash belgisidan iborat barcha buyruqlarda oxirgisini bilan almashtiring. Buyruqlardagi barcha boshqa belgilar o'zgarishsiz qoladi. dan buyruqlarida belgi o'zgarishsiz qoladi va boshqa barcha holatlar (i = 1, ..., t) mos ravishda almashtiriladi. Shu tarzda olingan barcha buyruqlar yig'indisi kompozitsiya mashinasining dasturini tashkil qiladi.
Taqdim etilgan kontseptsiya Tyuring mashinalarini loyihalash uchun qulay vositadir. Buni misol bilan ko'rsatamiz.
6.1-misol. Proyektor funksiyalarini (, …,) = (1? m ? n) to‘g‘ri hisoblaydigan Tyuring mashinalarini tuzamiz.
Avval n=3, m=2, ya'ni maxsus holatni ko'rib chiqing. funktsiya (,) =. Biz 0 so'zini 0 so'ziga qayta ishlashimiz kerak. Biz dastlabki konfiguratsiyaga avval tuzilgan Turing mashinalari B, O ni qo'llaymiz:
Shunday qilib, (,) = funktsiyasi mashinalarning quyidagi tarkibi bilan hisoblanadi: BOO = B.
Endi biz (, ...,) = ko'rinishdagi istalgan funktsiyani hisoblash uchun B, O mashinalar kompozitsiyasini qurish algoritmini tasavvur qilishimiz mumkin. To'g'ri siljish bilan, uni m-1 marta qo'llagan holda, siz avval qatorga erishishingiz kerak:
Keyin, chapga o'tib, massiv birinchi o'rinda bo'lmaguncha, massivni chapga ulashgan har bir massiv bilan almashtiring (B yordamida):
Endi siz (n-1) yordamida eng o'ng qatorga o'tishingiz kerak - o'ng siljishning bir nechta ilovasi:
Va nihoyat, birinchisidan tashqari barcha massivlarni o'ngdan chapga ketma-ket o'chirishingiz kerak:
Shunday qilib, bu funktsiya quyidagi Tyuring mashinasi tomonidan (to'g'ri) hisoblangan.