Algoritma nedir? Bir Turing makinesinde uygulanabilir her şey algoritmadır. Algoritma, bir problemi çözmek veya bir amaca ulaşmak için tasarlanan yoldur. Matematikte ve bilgisayar biliminde bir işi yapmak için tanımlanan, bir başlangıç durumundan başladığında, açıkça belirlenmiş bir son durumunda sonlanan, sonlu işlemler kümesidir. İlk algoritmayı Ebu Abdullah Muhammed bin Musa el Harezmi bulmuştur. O yüzden Harezmi>>>
Kategori Arşivleri: Hesaplama Teorisi
Hesaplama Teorisi
Karar Verilebilirlik (Decidability) nedir? Bir dil Turing makinesi tarafından kabul ediliyorsa rekürsif/özyineli veya karar verilebilir (decidable) olarak adlandırılır. Bütün karar verilebilir diller Turing Acceptable’dır. Diller: -Karar Verilebilir (Decidable) -Turing Kabul Eder (Turing Acceptable) -Turing Kabul Etmez (Non-Turing Acceptable) olarak sınıflandırılabilir. Karar verilebilir bir dilde Turing makinesi ya kabul ya da ret sonucunu döndürür: Bir dil>>>
Post Correspondence Problemi nedir? Post Correspondence Probleminin karar verilemez (undecidable) olduğunu gösteriniz? Post Correspondence Problemi, 1946 yılında Emil Post tarafından açıklanmış karar verilemez (undecidable) bir karar problemidir. Örnek: M = (abb, aa, aaa) ve N = (bba, aaa, aa) şeklinde a ve b sembollerinden oluşmuş 2 listemiz olsun. Bu iki listenin elemanlarının bazı kombinasyonlarında aynı>>>
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>>>
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>>>
∑={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? 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,>>>
Belirsizlik (Ambiguity) nedir? Bir örnekle açıklayınız? Bir L(G) içerikten bağımsız gramerinden (context-free grammar) üretilmiş w ifadesi için birden fazla türetme ağacı (derivation tree) oluşturulabiliyorsa bu tip gramere belirsiz(ambigious) denir ve bu durumun oluşmasına Belirsizlik (Ambiguity) ismi verilir. Örneğin: X → X+X | X*X | X | a gramerini belirsiz midir değil midir? ‘a+a*a’ ifadesini türeterek>>>
C={0^n1^n|n>= 0} dilinin içerikten bağımsız gramerini (context-free grammar) yazınız? Dilimiz n=0 durumunda null üretir Dilimiz n=1 durumunda 01 üretir Dilimiz n=2 durumunda 0011 üretir Bu şekilde devam eder. Bağımsız grameri (context-free grammar): S->S1 S1->0S11|null
C={w|w eşit sayıda 0 ve 1 içerir} dili düzenli mi, değil mi? Bir dilin düzenli olup olmadığını anlamak için pompalama önsavı(pumping lemma) şartlarını sağlaması gerekmektedir. Bir dilin düzenli olmadığını en başta o dili düzenli kabul ederek pompalama önsavı(pumping lemma) şartlarını sağlayamaması durumunda olmayana ergi(proof by contradiction) ile ispat ederiz. Pompalama Önsavı (Pumping Lemma) şartları: -A>>>