Bir Turing makinasının biçimsel (formal) tanımını yapınız?

Bir Turing makinasının biçimsel (formal) tanımını yapınız?

Tip-0 gramerleri tarafından üretilen rekürsif numaralandırılabilir dili tanımlayan makinalara Turing makinesi denir. 1936 yılında Alan Turing tarafından tasarlanmıştır.

Turing makinası girdiyi sonsuz hücreli bir teyp üzerindeymiş gibi modelleyen matematiksel bir yaklaşımdır. Teypten verileri okuyan bir kafa mevcuttur. Durum registeri, Turing makinasının durumunu tutar. Bir girdi okununca içerik başka bir sembolle değiştirilir ve sağ veya sola hareket eder. Makina kabul durumunda ise ifade kabul edilir, aksi halde reddedilir.

Bir Turing makinası biçimsel(formal) olarak 7 ögeli (Q,E,T,S,q0,qaccept,qreject) şeklinde ifade edilir.
Burada;
Q: Durumlar
E: Girdi alfabesi
T: Teyp alfabesi, Boşluk(Blank) burada bulunur ayrıca Girdi alfabesini kapsar.
S: QxT->QxTx{Sol,Sağ} Geçiş fonksiyonları
q0: Başlangıç durumu
qaccept: Kabul durumu
qreject: Ret durumu, Kabul durumu ile Ret durumu aynı olamaz.

Başka bir ifade şekli de:

TM->(Q, X, ∑, δ, q0, B, F)
Q: Durumlar
X: Teyp Alfabesi
∑: Girdi alfabesi
δ: Geçiş fonksiyonları δ : Q × X → Q × X × {Sola Hareket, Sağa Hareket}
q0: Başlangıç durumu
B: Boşluk sembolü
F: Kabul durumları

Etiketler: , , , , , , , , , ,

Yorum Yapın