Və avtomatlar nəZƏRİYYƏSİ (Məşğələ dərsləri üşün vəsait)

III. Tyurinq maşınlarının qurulması

Məsələ1 . f(x) =x+1 funksiyasını düzgün olaraq ikilik say sistemində toplama qanunlarına uyğun olaraq hesablayan Tyurinq maşınının qurulması
Həlli. Məsələnin şərtinə uyğun olaraq,giriş əlifbasını seçək: А ={0, 1, ε}.

Tyurinq maşınını cədvəl və qraf şəklində quraq

Cədvəl şəklində:

Qraf şəklində:

Qurulmuş Tyurinq maşınının proqramını quraq,haradaki, lentdəki giriş zənciri ikilik ədədə 111-ə bərabərdir.Hər bir əmrin solunda lentdəki giriş zəncirini verilmiş əmrin yerinə yetirilməsi təsvir edəkBaşlıq altındakı simvolu qeyd edək.

Nümunədən görünür ki, Tyurinq maşını standart ilkin konfiqurasiyadan 1-9 əmrlərini yerinə yetirərək(lentdə ilkin arqument 111) standart son vəziyyətə keçmişdir və nəticədə 1000 almışdır.Doğrudan da 111₂+1₂=1000₂

Məsələ2 (x div 2) əməliyyatını yerinə yetirən Tyurinq maşınının qurulsun və giriş əlifbası А = {0, 1, ε} .

Həlli.

Tyurinq maşınının uyğunluq cədvəli aşağıdakı kimi olacaqdır

(x div 2) əməliyyatı zəncirin 1 dərəcə sağa sürüşməsi ilə yerinə yetirilmişdir.

Məsələ3. Verilmiş arqumentin surətini çıxarma əməliyyatını yerinə yetirən Tyurinq maşınının qurulsun.Giriş əlifbası kimi А={0,1,ε} seçilsin.

Həlli Tyurinq maşınının uyğunluq cədvəli aşağıdakı kimi olacaqdır

Qurulmuş Tyurinq maşınının proqramını quraq,haradaki, lentdəki giriş zənciri ikilik ədədə 111-ə bərabərdir.Hər bir əmrin solunda lentdəki giriş zəncirini verilmiş əmrin yerinə yetirilməsi təsvir edəkBaşlıq altındakı simvolu qeyd edək.

Nümunədən görünür ki, Tyurinq maşını standart ilkin konfiqurasiyadan 1-32 əmrlərini yerinə yetirərək(lentdə ilkin arqument 111) standart son vəziyyətə keçmişdir və nəticədə 111*111ε almışdır.