MühaziRƏ 1 Verilənlər. Alqoritmlər və verilənlərin strukturu

MÜHAZİRƏ 12

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.