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

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ə

Ə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.