Lisansüstü Araştırmalar

Lisansüstü Araştırmalar

Hesaplanabilir Fonksiyon (Computable Function) nedir?

Hesaplanabilir Fonksiyon (Computable Function) nedir? Bir f:Ʃ^*→Ʃ^* fonksiyonu, her bir w girdisinde, herhangi bir M Turing makinesi teybinde yalnızca f(w) ile sonlanırsa (halt) hesaplanabilir bir fonksiyondur. Basitçe bir fonksiyonun hesaplanabilir olması o fonksiyonun bir sonucunun çıkması anlamına gelir. Örneğin Church-Turing…

Algoritma nedir?

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…

Karar Verilebilirlik (Decidability) nedir?

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….

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…

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…

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….

Belirsizlik (Ambiguity) nedir? Bir örnekle açıklayınız?

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 →…