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

III. TYURİNQ MAŞINLARI

3.1.Əsas məlumatlar
Alqoritmin ilk formal təriflərindən biri ingilis riyaziyyatçısı A.Tyurinqin 1936-cı ildə verdiyi tərif olmuşdur.O, hansısa hipotetik (abstrakt) maşının sxemini təsvir etmiş və bu maşının işini təsvir edən hərəkətlər ardıcıllığını formalaşdırmışdır.

Tyurinq maşını abstrakdır və onu praktik realizə etmək mümkün deyil.Ona görə də Tyurinq maşınlarının alqoritmləri başqa vasitələrlə yerinə yetirilməlidir. Tyurinq maşınlarından istifadə etməklə alqoritmlərin formalaşdırıl-masının əsas nəticəsi,müxtəıif məsələlərin həll alqoritmlərinin olub və ya olmaması imkanının sübut edilməsidir.

Tyurinq maşınları üçün yazılmış alqoritmləri təsvir edərək və alqoritmlərin müxtəlif kompozisiyasının realizə olunmasını isbat etməklə, Tyurinq özü tərəfindən təklif olunmuş konstruksiyaların müxtəlif imkanlarını göstərərək, belə bir tezislə çıxış etmişdir:”İstənilən alqoritm uyğun Tyurinq maşını ilə həyata keçirilə (realizə oluna) bilər.”Tyurinqin bu tezisini isbat etmək olmaz, ona görə ki,”istənilən alqoritm” anlayışı onun formalaşmasında təyin olunmamışdır.Onu ancaq müxtəlif alqoritmləri Tyurinq maşınları şəklində göstərməklə əsaslandırmaq olar.İsbat olunmuşdur ki,bu maşınlarda hesablanan funksiyaların sinfi ilə üst-üstə düşür.
3.2.Tyurinq maşınlarının formal olmayan tərifi
Tyurinq maşını hər iki tərəfə uzadılmış lenti olan avtomatdan ibarətdir:hesablayıcı başlıq və idarəedici qurğu .

İdarəedici qurğu Q={q₀,q₁,...,q_n} sonlu çoxluğu əmələ gətirən vəziyyətlərdən birində ola bilər.Q çoxluğunu Tyurinq maşınının daxili əlifbası da adlandırırlar.

Tyurinq maşınının hesablama maşınlarından prinsipial fərqi ondan ibarətdir ki,onun yaddaş qurğusu sonsuz lent şəklində olur və onun fiziki realizasiyası mümkün deyil.Lent yuvalara(xanalara) bölünmüşdür və hər bir yuvada A={a₀,a₁,...,a_m} sonlu əlifbasının simvollarından biri yazılır.A əlifbası Tyurinq maşınının giriş əlifbası adlandırılır.Tyurinq maşınının fəaliyyəti zamanı sonlu sayda yuvalar doldurula bilər.Hesablayıcı başlıq hər bir zaman anında lentin yuvasında olan simvoldan asılı olaraq ,onu təsvir edir.İdarəedici qurğu bu yuvaya (xanaya) ya yeni simvol yazır ya da onu sağa və ya sola sürüşdürməklə dəyişməz saxlayır ya da köhnə yerində saxlayır.Bu zaman idarəedici qurğu ya yeni vəziyyətə keçir ya da əvvəlki vəziyyətdə qalır .İdarəedici qurğunun vəziyyətləri arasında q₀ ilkin vəziyyəti və q_n son vəziyyəti xüsusi olaraq qeyd olunur.

Beləliklə,Tyurinq maşını bir takt ərzində simvolu oxuyaraq ,ya onun yerinə yeni simvol yazır, ya onu dəyişməz saxlayaraq başlığı bir xana sağa ya sola sürüşdürür, ya da onu öz yerində saxlayır.

3.3. 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.
3.4. Tyurinq maşınının təsviredilmə üsulları

Tyurinq maşınının 3 cür təsviredilmə üsulu var:

əmrlərin birləşməsindən;

qraf şəklində;

cədvəl şəklində
3.4.1. Əmrlərin birləşməsindən istifadə etməklə Tyurinq maşınların təsviri
Maşın tərəfindənyerinə yetirilən bütün əmrlər birləşməsinə proqram deyilir.

Tyurinq maşını aşağıdakı şərtlər yerinə yetirilərsə,düzgün sayılır:

- əgər onun xarici və daxili əlifbası verilərsə;

- proqram;

- başlanğıc konfiqurasiya;

- son vəziyyət.

Əmrlər birləşməsini yazmaq üçün aşağıdakı qaydalardan istifadə etmək lazımdır:

1. 
   alqoritmin ilkin addımına q₀ – başlanğıc vəziyyəti uyğunlaşdırılır;
   
2. 
   dövrün son addımlarından başlamğıc addımına keçid yerinə yetirməli;
   
3. 
   alqoritmin növbəti addımına keçidə yanaşı vəziyyət uyğun gəlir.
   
4. 
   Alqoritmin son addımı son vəziyyətə keçiddir.
   

Misal.0-lar və 1-dən istifadə edərək giriş zəncirinin Tyurinq maşının əmrlər birləşməsinə baxaq.

Tutaq ki, Tyurinq maşını A={0, 1, ε} çoxluöu ilə verilmiş,haradaki,

ε simvolu boş xananı göstərir,idarəedici qurğunun vəziyyətləri

Q = {q0, q1, qz}. Çoxluğu ilə verilmişdir.Əgər ,məsələn başlanğıc konfiqurasiya q0110011 şəklindədirsə,onda sonuncu konfiqurasiya əməliyyatın sonundan sonra qz001100 şəklində olmalıdır.

Bu məsələnin həlli üçün maçın aşağıdakı əmrlər ardıcıllığından istifadə edəcəkdir:

q₀1 → q₀0R, q₁0 → q₁0L,

q₀0 → q₀1R, q₁1 → q₁1L,

q₀ ε → q₁εL, q₁ε → q_zεR.

Standart başlanğıc konfiqurasiya başlıq soldakı ilk simvolun üzərindədir və idarəedici qurğu başlanğıc vəziyyətdədir.

Növbəti addımda (taktda) Tyurinq maşını öz vəziyyətini dəyişmədən 0-ı 1-lə və ya 1-i 0-la əvəz edir və sağa 1 simvol sürüşür.Bütün zəncir nəzərdən keçirilərək başlığın altında boş xananı göstərən simvol olur.Bu zaman Tyurinq maşını yeni vəziyyətə keçir və sola 1 simvol sürüşür.Növbəti taktlarda idarəedici qurğu öz vəziyyətini dəyişmir,başlıq altındakı simvolu dəyişməz saxlayır və boş xanaya rast gələnə kimi sola sürüşdürülür.Boş xanaya rast gələrkən Tyurinq maşını sonuncu vəziyyətə keçir və standart sonuncu konfiqurasuyaya keçir.

3.4.2. Tyurinq maşınının qrafla təsviri
Tyurinq maşınını qrafla təsvir edərkən hər bir vəziyyətə qrafın zirvəsi,hər bir əmrə isə -işarələnmiş əyrini uyğunlaşdırmaq lazımdır.

Yuxarıda baxdığımız misala uyöun olaraq Tyurinq maşını qraf şəklində aşağıdakı kimi olacaqdır:

Başlanğıc və son zirvələr adətən seçilməlidir:şəkildə onlar qara dairələrlə işarələnmişdir,Əgər Tyurinq maşınının işinin növbəti taktında lentdəki simvol dəyişmirsə,onda əmrin sağında onu yazmasaq da olar.(q_z vəziyyətində ε).

3.4.3. Tyurinq maşınının cədvəllə təsvir edilməsi
Bu üsulla təsvir zamanı cədvəl aşağıdakı üsulla tərtib edilir:hər vəziyyətə sətir,giriş əlifbasının hər bir simvoluna isə sütun uyğun gəlir.Cədvəlin xanalarında isə(sətir və sütunun birləşməsində) yerinə yetiriləcək hərəkət(ya da əmrin sağ tərəfi).

Verilmiş misal öçün Tyurinq maşının uyğun cədvəli aşağıdakı kimi olacaqdır:

	0	1	ε
q0	q01R	q00R	q1 εL
q1	q10L	q11L	qz εL

Giriş zəncirinin çevrilməsinin Tyurinq maşını proqram ilə yerinə yetirmək olar.Bu proqram 6 əmrdən ibarətdir.