:::: MENU ::::
Lisansüstü Araştırmalar

Özyineleme (Recursion) teoremi nedir?

Özyineleme (Recursion) teoremi nedir?

T, t:Ʃ^*×Ʃ^*→Ʃ^* fonksiyonunu hesaplayan bir Turing makinesi olsun. Ve bir r:Ʃ^*→Ʃ^* fonksiyonunu hesaplayan, her bir w için r(w)=t(,w) olan bir R Turing makinesi olsun. Kendi tanımını elde edip ardından bununla hesaplama yapabilen bir Turing makinesi yapmak için yalnızca, makinenin tanımını ekstra bir giriş olarak alan, yukarıda belirtildiği gibi bir T makinesi yapmak gerekir. Ardından recursion teoremi, tıpkı T gibi çalışan ancak tanımı otomatik olarak yapılmış yeni bir R makinesi üretir.

Başka bir açıdan:

Özyineleme (Recursion) teoremi, hesaplanabilirlik teorisinde ileri düzey çalışmalarda önemli bir rol oynayan matematiksel bir yaklaşımdır. Matematiksel mantığa, kendi kendini yeniden üreten sistemlerin teorisine ve hatta bilgisayar virüslerine bağlantıları vardır.

Özyineleme (Recursion) teoremini izah etmek için yaşam araştırmasında kullanılan bir paradokstan bahsedelim. Kendi kopyalarını oluşturabilen makineler yapma ihtimali var mıdır? sorusuna cevap aranmaktadır.

1. Canlılar makinelerdir.
2. Canlılar kendiliğinden çoğalabilirler.
3. Makineler kendi kendine çoğalamazlar.

Özyineleme (Recursion) teoremi 3.durumun yanlış olduğunu ortaya koyar.

Özyineleme (Recursion) teoremi:

T, t:E*xE*->E* fonksiyonunu işleyen bir Turing makinesidir. R, r:E*->E* fonksiyonunu her w girdisi için işleyen bir Turing makinesidir. r(w)=t(,w).

Bu tanıma göre T Turing Makinesi, R Turing makinesini otomatik olarak üretir.

Bilgisayar virüsleri, kendi kendilerine çoğalan bir yapıdadırlar.

Videolu anlatım:


İndirgeme (Reduction) nedir? İndirgenebilirlik (Reducibility) nedir? Örneklerle açıklayınız?

İndirgeme (Reduction) nedir? İndirgenebilirlik (Reducibility) nedir? Örneklerle açıklayınız?

İndirgeme bir problemi başka bir probleme dönüştürme işlemidir, böylece ikinci problemin çözümü birinci problemi çözmek için kullanılabilir.

İndirgenebilirlik, A ve B gibi iki problemi içerir. Eğer A, B’ye indirgenebilirse, B’yi çözmek için A’yı kullanabilirsiniz.

Örneğin bir şehirde yolunuzu bulmak istiyorsunuz. Bir haritanız olmuş olsa yolları daha rahat bulabileceğinizi biliyorsunuz. Böylece şehirde yol bulma problemini bir harita elde etme problemine indirgemiş oldunuz. Haritanız olduğu zaman şehirde yolunuzu bulabilirsiniz.

Burada A-> Şehirde Yol Bulma B-> Harita Edinme

İndirgenebilirlik, A veya B’nin çözümü için bir yorumda bulunmaz sadece B problemini çözdüğünüz zaman A problemini de çözebileceğinizi belirtir.

Bir başka örnek:
A->Konya’dan İstanbul’a gitmek
B->Konya-İstanbul uçak bileti almak
C->Bilet almak için para kazanmak
D->Para kazanmak için iş bulmak

Matematiksel örnekler verecek olursak:
-Dikdörtgen alanını bulmak, genişliğini ve yüksekliğini ölçmek için indirgemedir.
-Bir dizi doğrusal denklem çözmek, bir matrisi tersine çevirmek için indirgemedir.

İndirgenebilirlik, problemleri karar verilebilir (decidable) ve karar verilemez (undecidable) olarak sınıflandırmada ve karmaşıklık teorisinde (complexity theory) önemli rol oynar.

A, B’ye indirgenebilir olduğunda, A’yı çözmek B’yi çözmekten daha zor olamaz çünkü B’nin çözümü A’ya bir çözüm getirir.

Hesaplanabilirlik teorisi açısından, eğer A, B’ye indirgenebilir ve B karar verilebilir ise, A da karar verilebilirdir. Benzer şekilde, A, karar verilemez ve B’ye indirgenebilirse, B karar verilemezdir.


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


Sayfalar:12345678910...24