Hesaplama Modelleri
Birçok resmi çerçeve, lambda kalkülüsünün fonksiyon yeniden yazımından Boole devrelerine ve kuantum sistemlerine kadar hesaplamanın ne anlama geldiğini tanımlamaktadır; bu modellerin güçlerinin karşılaştırılması ise hangilerinin eşdeğer olduğunu ve hangilerinin gerçekten farklılaştığını ortaya koymaktadır.
Tanım
Bir hesaplama modeli, hangi işlemlerin izin verildiğini ve bir hesaplamanın nasıl ilerlediğini belirten hassas bir soyut çerçevedir; farklı modeller aynı fonksiyon sınıfını hesaplayabilmekle birlikte, özlülük, paralellik veya açıkça belirttikleri kaynaklar açısından farklılık gösterebilmektedir.
Kapsam
Bu alan, lambda kalkülüsü ve fonksiyonel modelleri, özyinelemeli fonksiyonlar ve kayıt makinelerini, Boole devreleri ve devre karmaşıklığını ve kuantum hesaplamayı kapsamaktadır; her bir modelin algoritmaları nasıl ifade ettiğini, hesaplanabilirlik güçlerinin Church–Turing tezi aracılığıyla nasıl ilişkili olduğunu ve verimliliklerinin nasıl farklılaşabileceğini incelemektedir.
Alt konular
Temel sorular
- Hesaplama kavramını resmileştirmenin ne gibi farklı yolları vardır?
- Hangi modeller hesaplayabildikleri fonksiyonlar açısından eşdeğerdir ve neden?
- Verimlilik, paralellik veya fiziksel gerçekleştirilebilirlik önemli hale geldiğinde modeller nasıl farklılaşmaktadır?
- Kuantum hesaplama gibi fiziksel olarak motive edilmiş bir model, klasik verimliliği aşabilmekte midir?
Temel kuramlar
- Church–Turing tezi altında eşdeğerlik
- Lambda kalkülüsü, özyinelemeli fonksiyonlar, kayıt makineleri ve Turing makinelerinin hepsi tam olarak aynı fonksiyon sınıfını hesaplamaktadır; bu yakınsama, hesaplamanın Turing hesaplanabilirliği ile özdeşleştirilmesinin temelini oluşturmaktadır.
- Verimlilikte farklılaşma
- Hesaplanabilirlik konusunda hemfikir olan modeller, kaynaklar açısından keskin farklılıklar gösterebilmektedir: devreler paralel ve tekdüze olmayan hesaplamayı ortaya koyarken, kuantum modelleri hızlanmalar sunuyor gibi görünmektedir; bu nedenle, hesaplanabilirlik için olmasa bile karmaşıklık için model seçimi büyük önem taşımaktadır.
Klinik önem
Farklı modeller, gerçek hesaplamanın farklı yönlerini aydınlatmaktadır: lambda kalkülüsü, fonksiyonel programlama dillerinin teorik temelini oluştururken, devreler donanımı ve paralel hesaplamayı modellemektedir; kayıt makineleri geleneksel işlemcileri yansıtmaktadır ve kuantum modelleri, gelişmekte olan kuantum donanım ve algoritmalarının tasarımına rehberlik etmektedir.
Tarihçe
1930'larda Church'ün lambda kalkülüsü, Gödel ve Kleene'nin özyinelemeli fonksiyonları ve Turing'in makineleri ayrı ayrı önerilmiş ve ardından eşdeğer oldukları gösterilmiştir. Daha sonraki modeller yeni boyutlar eklemiştir: devre karmaşıklığı paralel ve donanım hesaplamasını resmileştirmiş, Feynman'ın 1982'deki kuantum simülasyonu önerisi ise kuantum hesaplama modelinin temelini atmıştır.
Öne çıkan isimler
- Alonzo Church
- Alan Turing
- Stephen Kleene
- Richard Feynman
İlgili konular
Temel eserler
- church1936
- sipser2013
- aroraBarak2009
Sıkça sorulan sorular
- Aynı fonksiyonları hesaplıyorlarsa neden birçok model incelenmektedir?
- Eşdeğerlik yalnızca prensipte hesaplanabilen şeyler için geçerlidir. Farklı modeller, farklı şeyleri ifade etmeyi veya analiz etmeyi kolaylaştırmaktadır: lambda kalkülüsü fonksiyonel programlamayı açıklığa kavuştururken, devreler paralelliği ve donanım maliyetlerini ortaya koymaktadır; kuantum modelleri ise fiziksel fenomenleri yakalamaktadır, bu nedenle her biri farklı sorular için doğru bakış açısını sunmaktadır.
- Tüm hesaplama modelleri eşdeğer midir?
- Tüm makul klasik modeller, Church–Turing tezini destekleyerek aynı fonksiyon sınıfını hesaplamaktadır. Ancak verimlilik açısından büyük farklılıklar gösterebilmektedirler ve kuantum süperpozisyonu gibi farklı kaynakları kullanan modeller, aynı fonksiyonları hesaplarken bile belirli problemleri daha hızlı çözebilmektedir.