1 maruza: Algoritm va uning ta’riflari Asosiy savollar

1. Kompozitsiyaning ishlashi.
M 1 va M 2 tashqi alifbosi A «teng bo'lgan Tyuring mashinalari bo'lsin (a 0, a 1, ..., a p). Keling, ularning holatlar to'plamini mos ravishda Q1 «(q 0, q 1, ..., q n) va Q2« (q 0 ", q 1", ..., q m ") deb belgilaymiz.
Ta'rif.
M 1 va M 2 mashinalarining tarkibi - M = M 1 × M 2 bilan belgilanadigan mashina, uning dasturi A alifbosi, Q «(q 0, q 1, ..., qn, qn +) holatlar to'plami. 1, ..., qn + m) va M 1 va M 2 mashinalarining dasturlaridan quyidagicha olinadi: M 1 mashinasining dasturining hamma joyida, q 1 belgisi bilan "uchlik" bor ( mashinaning oxirgi holati M 1), u q 0 "belgisi bilan almashtiriladi (M 2 mashinasining dastlabki holati); M 1 va M 2 mashinalari dasturlaridagi boshqa barcha belgilar o'zgarmaydi (oxirida, M mashinasining barcha holatlarini qayta raqamlash qoladi: (q 0, q 1 ", q 2, ..., qn, q 0", q 2 ", ..., qm")).
Kompozitsiya M 1 mashinasi sifatida "ishlay" boshlaydi, lekin M 1 mashinasi to'xtashi kerak bo'lgan hollarda q 1 q 0 ga almashtirilganligi sababli u M 2 mashinasining dasturiga o'tadi. "Shubhasiz, kompozitsion operatsiya assotsiativ, lekin komutativ emas.
Uning ishlashi T1 va T2 mashinalarining ketma -ket ishlashiga teng.
Rasmda n = 1 va m = 1 uchun superpozitsiya operatorini amalga oshiruvchi Tyuring mashinalari tarkibi ko'rsatilgan.
1 -rasm.
Ta'rif.
Tyuring mashinasining takrorlanishi M - bu mashina

2. Tarmoqlanishning ishlashi.
M 1, M 2 va M 3 bir xil tashqi alifbo A «(a 0, a 1, ..., ai, ..., aj, ..., ap) bo'lgan Tyuring mashinalari bo'lsin va shunga mos ravishda holatlar to'plami: Q1 «(q 0, q 1, ..., qn), Q2« (q 0 ", q 1", ..., qm "), Q3« (q 0 ", q 1", ..., ql ").
Ta'rif.
M 1, M 2 va M3 Tyuring mashinalarida bo'linish operatsiyasining natijasi Tyuring mashinasi M deb ataladi, uning dasturi M 1, M 2 va M 3 mashinalarining dasturlaridan quyidagicha olinadi: mashina dasturi M1 yoziladi, keyin M 2 va M 3 mashinalarining dasturlari tayinlanadi. Agar a i belgisi M1 mashinasining q 1 yakuniy holatida kuzatilsa, u holda boshqaruv M 2 mashinasiga o'tkaziladi, ya'ni. q 1 belgisi q 0 "belgisi bilan almashtiriladi va M 2 mashinasi ishlay boshlaydi. Agar aj belgisi M 1 mashinasining q 1 yakuniy holatida kuzatilsa, u holda boshqaruv M 3 mashinasiga o'tkaziladi, ya'ni. q 1 belgisi q 0 "belgisi bilan almashtiriladi va M 3 mashinasi ishlay boshlaydi. M 1 va M 2 mashinalari dasturlaridagi boshqa barcha belgilar o'zgarmaydi. M mashinasi q 1 yakuniy holatida tugaydi (oxir-oqibat, M mashinasining holatini oxirigacha raqamlash kerak).
M 1, M 2 va M3 Tyuring mashinalarida tarmoqlanish operatsiyasining natijasi quyidagicha belgilanadi:
Ikki harfli Tyuring mashinalari uchun (ikki harfli alifboli Tyuring mashinalari) o'zboshimchalik bilan M1, M2 va M3 Tyuring mashinalari ustidan bo'linish jarayoni quyidagicha belgilanadi:

o'sha. agar q 1 holatida M1 mashinasining ishlashi paytida a 0 belgisi kuzatilsa, u holda boshqaruv M2 mashinasiga, aks holda - M3 mashinasiga o'tkaziladi.