Etiket Arşivleri: Turing makinesi

∑={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, # […]

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, […]

P, NP, NPC Problemler ne demektir?

Hesaplama teorisi (Theory of computation) bilgisayar biliminin bir problemin belirli bir algoritma ve hesap modeli ile çözülüp çözülemeyeceğini veya çözülürse ne kadar hızlı ve verimli bir şekilde çözüleceğini inceleyen bilim dalıdır. Başlıca 2 dala ayrılır: Karmaşıklık Teorisi (Complexity Theory) ve Hesaplanabilirlik Teorisi (Computability Theory). Karmaşıklık teorisi genelde karar verme problemleri (decision problems) ile uğraşır. Karar […]