:::: MENU ::::
Hesaplama Teorisi

Durma (Halting) problemi nedir?

Durma (Halting) problemi nedir?

Bir programın belli bir zaman sonra durup durmayacağı belirsizdir. D(P,G) şeklinde bir durup durmamayı bilen program yazıldığını düşünelim. Burada P programı G girdisi ile çalıştığı zaman durup durmayacağını D(P,G) programımız söyleyecek olsun. D(P,G)’nin bir sonuç döndüreceğini kabul ettiğimizden eğer programa kendisini girdi olarak verirsek sonuç döndürmesi beklenir, yani D(P,P) durumu. Fakat böyle bir şey mümkün değildir. Durma (Halting) problemi kararı mümkün olmayan (undecidable) bir problemdir.

Halting makinesi girdi olarak aldığı ifadenin sonucunda makinenin durup durmayacağını belirten makinedir.

durma-halting-makinesi


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ı


∑={0,1} alfabesi ile oluşturulmuş C={w|w#w} dilini tanıyan Turing makinesini tanımlayınız?

∑={0,1} alfabesi ile oluşturulmuş C={w|w#w} dilini tanıyan Turing makinesini tanımlayınız?

C diline ait ifadeleri kabul eden, aksi ifadeleri reddeden bir Turing makinesi tasarlayacağız.
İfadenin ortasında # işareti var ve #’in sağ ve solundaki ifade aynı olmak zorundadır.

Çözüm yaklaşımı: # işaretinin sağında ve solunda zikzak yaparak çözüme ulaşabiliriz.
İfadenin içerisinde # işareti yoksa ret,
# işareti varsa ve #’in sağındaki ve solundaki sembollerin sayısı farklıysa ret,
aynıysa #’in sağındaki ve solundaki sembollerin dizilişi farklıysa ret, aynıysa kabul durumuna geçer.

w#w

Q (Durumlar)= {q1,q2,q3,q4,q5,q6,q7,q8,qaccept},
Girdi alfabesi= {0,1,#}
Teyp Alfabesi = {0,1,#,x,null}

011000#011000 girdisi için adımların simülasyonu:

w-sharp-w


Church-Turing tezi nedir? Açıklayınız?

Church-Turing tezi nedir? Açıklayınız?

Alonzo Church tarafından ortaya atılan teze göre, herhangi bir algoritma, herhangi bir donanımda çalışabiliyorsa, bu donanıma karşılık gelen bir Turing makinesi olduğudur. Daha basit bir ifadeyle, Turing makineleri, herhangi bir donanımın yaptığı algoritmasal işlemleri yerine getirebilir.

Church-Turing tezi:
Mekanik olarak yapılabilen her hesaplamayı yapabilecek bir Turing makinesi vardır.

Church-Turing tezine göre, Turing makinesiyle gerçekleştirilemeyen hesaplamalar karar verilemez (undecidable) olarak adlandırılır.

Church, algoritmaları tanımlamak için lambda-calculus adlı bir gösterge sistemi kullandı. Turing bunu makinesi ile yaptı. Bu iki tanımın eşdeğer olduğu gösterildi. Biçimsel olmayan algoritma anlayışı ile kesin tanım arasındaki bu bağlantı Church-Turing tezi olarak anılmaktadır.


Sayfalar:12345678