1 maruza: Algoritm va uning ta’riflari Asosiy savollar

TYURING MASHINASINING TARKIBI. TYURING MASHINASINING TARKIBI UNIVERSAL TYURING MASHINASI
Oldingi paragrafda biz "berilgan Tyuring mashinasi f (, ...,) funktsiyasini qanday hisoblashini" ko'rib chiqdik. Buning uchun, ... raqamlarining har biri mashinaning lentasiga mos keladigan sonlarning uzluksiz qatori sifatida yozilishi kerak va massivlarning o'zlari 0 belgisi bilan ajratilishi kerak. Agar f ( , ..., berilgan argument qiymatlari to'plamida aniqlanadi, natijada tasmada f (, ...,) birlik qatoriga yozilishi kerak, biz esa boshlang'ich pozitsiyasiga unchalik qattiq bo'lmaganmiz. mashina (bu odatda standart boshlang'ich pozitsiyasi edi), u ishni tugatadi va bu ish qanday davom etadi.
Kelgusida bizga Tyuring mashinasidagi funktsiyani hisoblashning kuchliroq tushunchasi kerak bo'ladi - to'g'ri hisoblash tushunchasi.
Ta'rif 5.1: Aytamiz, agar Tyuring mashinasi f (, ...,) funktsiyasini to'g'ri hisoblasa, agar u 0 ... 0 so'zini 0 ... 0 so'ziga aylantirsa va lentaga yangi katakchalarni qo'shmasa. jarayonda chapga yoki o'ngga. Agar f funktsiyasi berilgan argument qiymatlari to'plamida aniqlanmagan bo'lsa, u holda belgilangan pozitsiyadan ishlay boshlagan holda, u hech qachon jarayonni chap tomonida o'tkazmaydi.
Misol 5.1. Bu erda S (x) = x + 1 va O (x) = 0 funktsiyalarini to'g'ri hisoblaydigan Tyuring mashinalari dasturlari. S (x) = x + 1 funktsiyasi tarjima qilinadi: 0 =>. Uning dasturi: 0> P, 1> 1P, 0> 1, 1> 1L, 0> 0. O (x) = 0 funktsiyasi tarjima qilinadi: 0 =>. Uning dasturi: 0> 0P, 1> 1P, 0> 0L, 1> 0, 0> 0L, 0> 0. Tegishli Tyuring mashinasi O.
Misol 5.2."Chap siljish" va "o'ng siljish" ikkita mashinani yarating. Boshlang'ich standart pozitsiyaning birinchisi 0 so'zini bir xil so'zga aylantiradi va nol bilan eng chap katakka qarashni to'xtatadi. Chap katakchasi nol bilan ko'rsatilgan boshlang'ich holatidagi ikkinchi mashina 0 so'zi bir xil so'zga aylanadi va to'xtab, eng o'ngdagi nolga qaraydi.
Mashina dasturi: 0> 0L, 1> 1L, 0> 0. Mashinaning dasturi oldingi mashinaning dasturidan "L" belgisini "P" belgisiga almashtirish orqali olinishi aniq.