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

Tyurinq maşınlarının formal tərifi

A əlifbası – simvolların sonlu çoxluğudur.Bu əlifbanın simvollar ardıcıllığı zəncir adlanır.X zəncirinin uzunluğu zəncirdə olan simvolların sayını göstərir və |x| ilə işarə olunur.Boş zəncirin uzunluğu sıfıra bərabərdir.

X və Y zəncirlərinin kонкатенаsiyası Y zəncirinin simvollarının X zəncirinə sağdan yazılması ilə alınan zəncir adlanır.

Tyurinq maşını 7-lik şəklində verilir:

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

Q - sonlu sayda vəziyyətlər çoxluğudur,hansında ki,idarəedici qurğu yerləşə bilər;

A - giriş əlifbası;

δ - keçidlər funksiyası, δ= Q ⋅ A → Q ⋅ A ⋅ S,haradaki S = {R, L, E}-sürüşmənin istiqaməti;

P_{0 –} ilkin vəziyyət, P₀ Q

P_z- son vəziyyət, pz ∈ Q;

a₀-boş xananı göstərən simvol, a0 ∈ A;

a₁-xüsusi simvoldur,lentdə zəncirləri ayırmaq üçündür, a1 ∈ A.

Tyurinq maşınının əmri qa → pbr keçidlər funksiyasının elementi adlanır.Haradaki, q və p∈ Q; a və b∈A; r∈S.Hər bir əmr Tyurinq maşınının bir taktını təsvir edir.

Tyurinq maşınının konfiqurasiyası aşağıdakı kimi təsvir olunur:

t = , haradaki,

C- hesablayıcı başlığın solunda yerləşən zəncir;

q- Tuyurinq maşınının vəziyyəti;

a- Tyurinq maşınının başlığının altınada yerləşən sinvol;

B- Tyurinq maşınının başlığının sağında yerləşən zəncir;

konfiqurasiyası birbaşa nq_na_nB_n> konfiqurasiyasına o zaman keçir ki,əgər ilkin konfiqurasiyaya tətbiq edilən bir əmrdən sonra yeni konfiqurasiya alınsın.

Bu konfiqurasiyadan digərinə birbaşa keçid aşağıdakı kimi işarə edilir:

⇒nq_na_nB_n>.

İlkin vəziyyəti göstərən konfiqurasiya başlanğıc, sonuncu vəziyyəti göstərən konfiqurasiya isə sonuncu deyilir.Əgər C zənciri konfiqurasiyada boşdursa,onda baçlanğıc və sonuncu konfiqurasiya standart adlanır.

Tyurinq maşını x zəncirini y zəncirinə o vaxt çevirir ki,əgər lentdə x və y zənciri var və başlanğıc konfiqurasidan başlayaraq Tyurinq maşını sonuncu konfiqurasiyaya keçir.Əgər başlanğıc və son konfiqurasiya standartdırsa,onda x-in y-ə çevrilməsi düzgün çevrilmə adlanır.