Hesaplanabilir Fonksiyonlar ve Church-Turing Tezi
Hesaplanabilir fonksiyonlar, mekanik bir prosedürle değerlendirilebilen fonksiyonlardır ve Church-Turing tezi, bu gayri resmi kavramı, hepsi aynı sınıfı tanımlayan çeşitli kesin matematiksel modellerle özdeşleştirmektedir.
Tanım
Bir fonksiyon, eğer bir Turing makinesi veya eşdeğer olarak bir kısmi özyinelemeli tanım, tanımlı olduğu her girdide çıktısını üretiyorsa hesaplanabilirdir; Church-Turing tezi, bu matematiksel olarak kesin sınıfın, etkin bir şekilde hesaplanabilir fonksiyonların sezgisel sınıfıyla örtüştüğünü ileri sürmektedir.
Kapsam
Bu konu, Turing makinelerini, temel fonksiyonlardan bileşim, ilkel özyineleme (primitive recursion) ve minimizasyon yoluyla oluşturulan kısmi özyinelemeli fonksiyonları, lambda kalkülüsünü ve kayıt makinelerini, bu modellerin eşdeğer olduğuna dair kanıtları, evrensel makineleri ve tüm etkin hesaplamayı kapsadıklarını öne süren Church-Turing tezini kapsamaktadır.
Temel sorular
- Turing makinesi nedir ve bir hesaplamayı nasıl tanımlar?
- Kısmi özyinelemeli fonksiyonlar temel işlemlerden nasıl üretilir?
- Hesaplamanın tüm makul modelleri neden aynı fonksiyonları tanımlar?
- Church-Turing tezinin durumu ve önemi nedir?
Temel kuramlar
- Turing makinesi modeli
- Bir Turing makinesi, sınırsız bir bant üzerinde çalışan sonlu durumlu bir cihazdır ve hesapladığı fonksiyonlar, temel sembol manipülasyonu açısından algoritma kavramını formüle etmektedir.
- Modellerin eşdeğerliği
- Turing makineleri, kısmi özyinelemeli fonksiyonlar, lambda kalkülüsü ve kayıt makineleri, hesaplanabilirlik kavramının sağlamlığını göstererek, tam olarak aynı fonksiyon sınıfını hesaplamaktadır.
- Evrensel makine ve numaralandırma
- Kodu verildiğinde herhangi bir makineyi simüle eden evrensel bir Turing makinesi bulunmaktadır, bu nedenle hesaplanabilir fonksiyonlar etkin bir şekilde numaralandırılabilir ve veri olarak ele alınabilir, bu da öz-referans sonuçlarının temelini oluşturmaktadır.
Klinik önem
Hesaplanabilir fonksiyon kavramı, teorik bilgisayar biliminin temelini oluşturmaktadır: evrensel makine, depolanmış programlı bilgisayarın öncüsü olarak kabul edilmekte, modellerin eşdeğerliği algoritmanın tek ve sağlam bir tanımını haklı çıkarmakta ve bu çerçeve, çözümsüzlük (undecidability) ve karmaşıklığın incelendiği kesin bir ortam sağlamaktadır.
Tarihçe
1936'da Church, lambda kalkülüsü aracılığıyla etkin hesaplanabilirliği tanımlamış, Turing ise kendi makineleri aracılığıyla bunu yapmıştır ve bu iki kavram kısa süre sonra Kleene'nin özyinelemeli fonksiyonlarına eşdeğer olduğu kanıtlanmıştır. Ortaya çıkan Church-Turing tezi, algoritmanın kabul görmüş tanımı haline gelmiş ve Turing'in evrensel makinesi, genel amaçlı bilgisayarın kavramsal bir atası olmuştur.
Öne çıkan isimler
- Alan Turing
- Alonzo Church
- Stephen Cole Kleene
- Emil Post
İlgili konular
Temel eserler
- cutland1980
- turing1936
- sipser2013
Sıkça sorulan sorular
- Bazı fonksiyonlar hesaplanamaz mı?
- Evet. Programlar numaralandırılabilirken fonksiyonlar numaralandırılamadığı için, bir sayma argümanı çoğu fonksiyonun hesaplanamaz olduğunu göstermektedir ve durma fonksiyonu gibi belirli örneklerin kanıtlanabilir şekilde hesaplanamaz olduğu bilinmektedir. Hesaplama yeteneği, algoritmaların hangi fonksiyonları değerlendirebileceği konusunda gerçek bir kısıtlamadır.
- Church-Turing tezi, bilgisayarların yapabileceklerini sınırlar mı?
- Bu tez, etkin hesaplamanın hiçbir modelinin hesaplanabilir fonksiyonlar sınıfını Turing makinelerinin ötesine genişletmediğini belirtmektedir. Daha hızlı donanım veya farklı mimariler verimliliği değiştirir, prensipte hesaplanabilir olanın sınırını değil; bu nedenle tez, algoritmik çözülebilirlik üzerinde mutlak bir sınır koymaktadır.