:::: MENU ::::
Hesaplama Teorisi

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 tezine göre bir fonksiyonun hesaplanabilir olması bu fonksiyonun bir makine ile (veya elektronik devre ile veya bilgisayar programı ile) modellenebiliyor olmasını ve sınırsız zaman ve depolama imkanı (storage) verildiğinde bir şekilde biteceği anlamına gelir.

Değeri bir Turing makinesi kullanılarak hesaplanabilen fonksiyonlara Hesaplanabilir Fonksiyon (Computable Function) denir.

Örneğin bir dilin hesaplanabilir olması bu dildeki bütün kelimeler için doğru ve bu dilden olmayan bütün kelimeler için de yanlış sonucunu veren bir fonksiyon bulunabilmesine bağlıdır. Bu fonksiyona da hesaplanabilir fonksiyon ismi verilir.

Örneğin bir düzenli ifade (regular expression) ile gösterilen dildeki bütün üretilebilen kelimeler için doğru sonucu veren fonksiyon ve üretilemeyen bütün kelimeler için yanlış sonucu veren fonksiyon bu tip bir fonksiyondur.

Bu tanımı biraz daha genişleterek bir A kümesi ve bir bu küme üzerindeki bir f fonksiyonu için Turing makinesi (turing machine) üretilebiliyorsa (ya da bir kahin makinesi (oracle) ) hesaplanabilir bir kümemiz ve hesaplanabilir bir fonksiyonumuz bulunuyor demektir. Bu duruma A-hesaplanabilir (A-computable) veya f-hesaplanabilir (f-computable) isimleri de verilir.

Kaynak: http://bilgisayarkavramlari.sadievrenseker.com/2009/06/25/hesaplanabilir-fonksiyon-computable-function/


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 işlemler kümesidir.

İlk algoritmayı Ebu Abdullah Muhammed bin Musa el Harezmi bulmuştur. O yüzden Harezmi Yolu’da denmektedir.

Algoritma, Değişkenler (Dışarıdan girilen veya bizim oluşturduğumuz değerler), Algoritma (gerekli adımların mantıksal bir sıra ile yazılması) ve Akış Diyagramı (Şekiller ve oklar ile mantıksal sıraların birbirine bağlandığı şema) parçalarından oluşur.

Her algoritma,
1. Girdi : Sıfır veya daha fazla değer dışarıdan verilmeli.
2. Çıktı : En azından bir değer üretilmeli.
3. Açıklık : Her işlem (komut) açık olmalı ve farklı anlamlar içermemeli.
4. Sonluluk: Her türlü olasılık için algoritma sonlu adımda bitmeli.
5. Etkinlik : Her komut kişinin kalem ve kağıt ile yürütebileceği kadar basit olmalıdır.
kriterlerini sağlamalıdır.

Kaynaklar:
https://tr.wikipedia.org/wiki/Algoritma
http://www.elektrikport.com/teknik-kutuphane/bes-dakikada-algoritmayi-taniyin/8223#ad-image-0


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.

dil-siniflandirmasi

Karar verilebilir bir dilde Turing makinesi ya kabul ya da ret sonucunu döndürür:

turing-makinesi-kabul-ret

Bir dil karar verilebilir ise tümleyeni de karar verilebilirdir.
Karar verilebilir bir dil aynı zamanda sayılabilirdir.

Örnek: m sayısının asal olup olmadığı problemi karar verilebilir (decidable) mi karar verilemez (undecidable) mıdır?

Asal Sayılar={2,3,5,7,11,13,…}

m sayısını 2 ile √m arasındaki bütün sayılara böleriz, herhangi birisi 0 kalanını verirse ret, aksi halde kabul olur. Böylece bu problem karar verilebilir bir problemdir.


Post Correspondence Problemi nedir? Post Correspondence Probleminin karar verilemez (undecidable) olduğunu gösteriniz?

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ı ifadeyi üretmek mümkünken, bazılarında bu mümkün değildir.

M = (x1,x2,x3)=(abb, aa, aaa) dersek.
N = (y1,y2,y3)=(bba, aaa, aa) dersek.

x2x1x3 = ‘aaabbaaa’ ve y2y1y3 = ‘aaabbaaa’ olduğunu görürüz böylece x2x1x3 = y2y1y3 olur. Fakat

M = (ab, bab, bbaaa) ve N = (a, ba, bab) listeleri için aynı şekilde bir ifade oluşturmaya çalıştığımızda:

| x2x1x3 | ≠ | y2y1y3 | ifadelerin uzunluklarının dahi tutmadığı görülmektedir. İşte bu durumdan dolayı Post Correspondence Problemi karar verilemez (undecidable) bir problemdir.

Daha biçimsel anlatımı, farklı bir örneği ve ispatı için tıklayınız

Videolu anlatım:


Sayfalar:12345678