Tyuring mashinasining ishlashi

1. Kompozitsiya operatsiyasi.
M 1 va M 2 bir xil tashqi alifbosi A« (a 0 ,a 1 ,...,a p ) boʻlgan Tyuring mashinalari boʻlsin. Ularning holatlar to‘plamlarini Q1 « (q 0 ,q 1 ,...,q n ) va Q2 « (q 0" ,q 1" ,...,q m" ) deb belgilaymiz.
Ta'rif.
M 1 va M 2 mashinalar tarkibi M=M 1 ×M 2 bilan belgilangan, dasturi A alifbosiga, Q« holatlar toʻplamiga (q 0 ,q 1 ,...,q n ,q n) ega boʻlgan mashinadir. +1 ,... ,q n+m ) va M 1 va M 2 mashinalarining dasturlaridan quyidagicha olinadi: M 1 mashinasi dasturining hamma joyida q 1 (belgili "uchlik" mavjud. mashinaning yakuniy holati M 1), u q 0" belgisi bilan almashtiriladi (mashinaning dastlabki holati M 2); M 1 va M 2 mashinalari dasturlaridagi barcha boshqa belgilar o'zgarishsiz qoladi (nihoyat, u M mashinaning barcha holatlarini qayta raqamlash uchun qoladi: (q 0 ,q 1" ,q 2 ,...,q n ,q 0 " ,q 2" ,...,q m" )).
Tarkibi M 1 mashinasi kabi "ishlay" boshlaydi, lekin M 1 mashinasi to'xtab qolishi kerak bo'lgan hollarda, q 1 ning q 0 "ga almashtirilishi tufayli M 2 mashinasining dasturiga o'tish mavjud. Bu Kompozitsiya amali assotsiativ, lekin kommutativ emasligi aniq.
Uning ishlashi T1 va T2 mashinalarining ketma-ket ishlashiga teng.
Rasmda n=1 va m=1 uchun superpozitsiya operatorini amalga oshiruvchi Tyuring mashinalarining tarkibi ko‘rsatilgan.
1-rasm.
Ta'rif.
Tyuring mashinasi M iteratsiyasi - bu mashina

2. Filialning ishlashi.
M 1, M 2 va M 3 bir xil tashqi alifbosi A« (a 0 ,a 1 ,...,a i ,...,a j ,...,a p ) va shunga mos ravishda toʻplamlarga ega boʻlgan Tyuring mashinalari boʻlsin. aytadi: Q1 « (q 0 ,q 1 ,...,q n ), Q2 « (q 0" ,q 1" ,...,q m" ), Q3 « (q 0», q 1" ,.. .,q l").
Ta'rif.
M 1, M 2 va M3 Tyuring mashinalarida tarmoqlanish operatsiyasining natijasi Tyuring mashinasi M bo'lib, uning dasturi M 1, M 2 va M 3 mashina dasturlaridan quyidagicha olinadi: M1 mashina dasturi yoziladi, keyin esa mashina. M 2 va M 3 dasturlari tayinlangan. Agar a i belgisi M1 mashinasining yakuniy q 1 holatida kuzatilsa, u holda boshqaruv M 2 mashinasiga o'tkaziladi, ya'ni. q 1 belgisi q 0" belgisi bilan almashtiriladi va M 2 dastgoh ishlay boshlaydi. Ammo, agar M 1 mashinasining yakuniy q 1 holatida a j belgisi 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 barcha boshqa belgilar o'zgarishsiz qoladi. M mashinasi yakuniy q 1 holatida tugaydi (xulosa qilib aytganda, M mashinaning holatlarini doimiy ravishda qayta raqamlashni amalga oshirish qoladi).
Tyuring M 1, M 2 va M3 mashinalarida tarmoqlanish operatsiyasining natijasi quyidagicha belgilanadi:
Ikki harfli Tyuring mashinalari uchun (ikki harfli alifboli Tyuring mashinalari) M1, M2 va M3 ixtiyoriy Tyuring mashinalarida tarmoqlanish operatsiyasi quyidagicha belgilanadi:

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