Formal diLLƏr və avtomatlar nəZƏRİYYƏSİ

3.6. Tyurinq maşını üzərində əməllər.

1. 
   Tyurinq maşınının kompoziyası.
   

Tutaq ki, T₁ və T₂ maşınlarının P₁ və P₂ proqramları var..Hesab edək ki,bu maşınların daxili əlifbaları kəsişmir:haradaki, q_z1 - T₁ maşınının son vəziyyəti,q₀₂ - T₂ maşınının başlanğıc vəziyyəti.

P₁ proqramının hər yerində q_z1 son vəziyyətini T₂ maşınının q₀₂ başlanğıc vəziyyəti ilə əvəz edək və yaranmış proqramı P₂ proqramı ilə birləşdirək.Yeni yaranmış P proqramı (q_z1, q₀₂) vəziyyətlərinə uyğun olaraq T₁ və T₂ maşınlarının kompoziyası olan T maşınını təyin edir.Maşınların kompoziyasını T₁ ^.T₂ və ya T₁ T₂ kimi işarələyə bilərik.Maşınların daha ətraflı kompoziyası aşağıdakı kimi olacaqdır:
T= T(T₁ ,T₂ (q_z1, q₀₂)) , haradaki,

T₁=(Q₁,A₁, δ₁,P₀₁,P_z1,a₀₁,a₁₁) ,

T₂=(Q₂,A₂, δ₂,P₀₂,P_z2,a₀₂,a₁₂) .

Tutaq ki,

a₀₁=a₀₂=a₀ və

a₁₁=a₁₂=a1

Onda T₁ T₂ kompoziyalarının xarici əlifbası T₁ və T₂ maşınlarının xarici əlifbalarının birləşməsindən əmələ gələcəkdir.

Alqoritmlər üzərində aparılan kompozisiya əməliyyatı əvvəlcədən məlum olan sadə alqoritmlərdən daha mürəkkəb alqoritmlərin alınmasına gətirib cıxarır.

2. 
   Tyurinq maşınının iterasiyası
   

Bu əməliyyatı ancaq bir maşında yerinə yetirmək olar.Tutaq ki, q_z – T maşınının son vəziyyətidir və q_n isə T maşınının hər hansı sonuncu olmayan bir vəziyyətidir. T maşınının P proqramının hər yerində q_z –i q_n ilə əvəz edək.Alınmış proqram yeni T(q_z, q_n) maşınını təyin edəcəkdir,hansı ki, (q_z, q_n) vəziyyətlərinə görə T maşınının iterasiyası adlanacaqdır.

3. 
   Tyurinq maşınının budaqlanması.
   

Tutaq ki, T₁ , T₂ və T₃ Tyurinq maşınları uyğun olaraq P₁,P₂ və P₃ proqramları ilə verilmişdir.Hesab edək ki,bu maşınların daxili əlifbası cüt-cüt kəsişmir və tutaq ki, q_z11 və q _z12 - T₁ maşınını hər hansı müxtəlif vəziyyətləridir.

P₁ proqramının hər yerində q_z11 vəziyyətini T₂ maşınının başlanğıc olan q₀₂ ilə,q_z12 vəziyyətini isə T₃ maşınının q₀₃ başlanğıc vəziyyəti ilə əvəz edək .Sonra yeni proqramı P₂ və P₃ proqramları ilə birləşdirək.Bu zaman Tyurinq maşınının P proqramını almış olarıq və bu aşağıdakı kimi işarələnəcəkdir

T=T(T_1,( q_z11, q₀₂),T₂(q_z12, q₀₃), T₃)

T maşını T₁ maşını ilə ilə idarə olunan T₂ və T₃ maşınlarının budaqlanmasından əmələ gəlmişdir.