Tyuring mashinasining ishlashi

test savollari
ü1.Tyuring mashinalarining tarkibi qanday?
ü2.Tyuring mashinalarining tarkibi nima uchun ishlatiladi?
ü3.Bir Tyuring mashinasi boshqa mashinaning ishini simulyatsiya qila oladimi?
Turing?
ü4.Bu holatda qanday harakatlar bajariladi?
ü5.Universal Tyuring mashinasining tuzilishini tushuntiring?
ü6.UMT lentasi zonalarida qanday ma’lumotlar qayd etiladi?
ü7.Tyuring mashinasining ko‘rsatmalar to‘plami nima?
ü8.UMT ish sikli qanday bosqichlarni o‘z ichiga oladi?
ü9.“Qidiruv buyruqlar zonasi” qadamining mazmunini tushuntiring.
ü10.“Buyruqni bajarish” qadamining mazmunini tushuntiring.
ü11.Axborotni qayta ishlash jarayoni qanday xususiyatlardan foydalaniladi
Oldingi paragrafda biz "ma'lum Tyuring mashinasi f(, ...,) funktsiyasini qanday baholashini" ko'rib chiqdik. Buning uchun har bir raqam, ..., mos keladigan birlik sonidan iborat uzluksiz massivda mashina lentasiga yozilishi va massivlarning o'zi 0 belgisi bilan ajratilishi kerak. f (, ...,) funktsiyasi berilgan argument qiymatlari to'plamida aniqlanadi, keyin natijada lentada f (, ...,) birlik qatorida yozilishi kerak. Shu bilan birga, biz emas edik. Mashinaning qaysi boshlang'ich holatida ishlay boshlagani (ko'pincha bu standart boshlang'ich pozitsiyasi edi), u ishni qaysi holatda yakunlashi va bu ish qanday davom etishi haqida juda qattiq.
Quyida biz Tyuring mashinasida funktsiyaning hisoblanishi to'g'risida kuchliroq tushunchaga - to'g'ri hisoblash tushunchasiga muhtojmiz.
Ta'rif 5.1: Biz aytamizki, Tyuring mashinasi f (, ...,) funktsiyasini to'g'ri hisoblaydi, agar u 0 ... 0 boshlang'ich so'zini 0 ... 0 so'ziga tarjima qilsa va shu bilan birga yangi katakchalarni qo'shmasa. lentadagi boshlang'ich so'z chapga yoki o'ngga. Agar f funktsiyasi berilgan argument qiymatlari to'plamida aniqlanmagan bo'lsa, u ko'rsatilgan pozitsiyadan ishlay boshlagan bo'lsa, u ish paytida hech qachon chap tomonda lentani qurmaydi.
5.1-misol. Bu yerda S(x) = x+1 va O(x) = 0 funksiyalarini to'g'ri baholovchi Tyuring mashinasi dasturlari keltirilgan. S(x) = x+1 funksiyasi quyidagicha tarjima qiladi: 0 => . Uning dasturi: 0 > P, 1 > 1P, 0 > 1, 1 > 1L, 0 > 0. O(x) = 0 funksiyasi tarjima qiladi: 0 => . Uning dasturi: 0 > 0P, 1 > 1P, 0 > 0L, 1 > 0, 0 > 0L, 0 > 0. Tegishli Tyuring mashinasi O deb belgilandi.