Church–Turing Tezi
Church–Turing tezi, herhangi bir etkili prosedürle hesaplanabilen her fonksiyonun bir Turing makinesi tarafından hesaplanabileceğini öne sürmekte, algoritmanın gayri resmi fikrini kesin bir matematiksel modelle eşitlemektedir.
Tanım
Church–Turing tezi, sezgisel olarak hesaplanabilen fonksiyonların, tam olarak bir Turing makinesi, eşdeğer olarak lambda kalkülüsü veya genel özyinelemeli fonksiyonlar (general recursive functions) tarafından hesaplanabilen fonksiyonlar olduğu iddiasıdır; sezgisel kavram resmi olarak tanımlanmadığı için bir teoremden ziyade bir tez olarak kabul edilmektedir.
Kapsam
Bu konu, tezin ifadesini, bağımsız olarak önerilen modellerden gelen yakınsak kanıtları, etkili hesaplanabilirlik hakkındaki orijinal tez ile daha güçlü fiziksel veya karmaşıklık-teorik varyantları arasındaki ayrımı ve tezin hesaplanabilirlik kuramında sezgi ile resmi kanıt arasında bir köprü olarak rolünü kapsamaktadır.
Temel sorular
- Algoritmanın gayri resmi kavramını resmi bir modelle özdeşleştirmek ne anlama gelmektedir?
- Bağımsız modellerin yakınsaması neden tez için güçlü bir kanıt olarak kabul edilmektedir?
- Tez matematiksel bir teorem mi, bir tanım mı, yoksa ampirik bir iddia mıdır?
- Fiziksel ve karmaşıklık-teorik versiyonlar orijinal ifadenin ötesine nasıl geçmektedir?
Temel kuramlar
- Hesaplama modellerinin yakınsaması
- Turing makineleri, Church'ün lambda kalkülüsü ve Gödel ile Herbrand'ın özyinelemeli fonksiyonlarının (recursive functions) tam olarak aynı fonksiyon sınıfını tanımladığı gösterilmiştir ve bu bağımsız mutabakat, tez için sunulan başlıca kanıttır.
- Teorem değil, tez statüsü
- Etkili prosedürün sezgisel kavramı resmileştirilmediği için iddia kanıtlanamaz; gayri resmi algoritmik argümanların resmi Turing makinesi yapılandırmalarının yerine geçmesine izin veren temel bir özdeşleştirme olarak kabul edilmektedir.
Klinik önem
Tez, etkili prosedürün herhangi makul bir kavramının Turing-eşdeğeri olduğu varsayıldığından, algoritmaları Turing makineleri yerine üst düzey sözde kodda (pseudocode) tanımlama günlük pratiğini meşrulaştırmaktadır; ayrıca fiziksel veya kuantum cihazların Turing-hesaplanabilirliğin ötesinde hesaplama yapıp yapamayacağına dair tartışmaları da şekillendirmektedir.
Tarihçe
1936'da Church, etkili hesaplanabilirliği lambda-tanımlanabilirlik (lambda-definability) ile özdeşleştirmeyi önermiş, Turing ise bağımsız olarak kendi makine modelini savunmuştur. Bunun ardından Turing, Kleene ve diğerleri, bunları ve özyinelemeli fonksiyonları (recursive functions) eşdeğer olarak kanıtlamışlardır. Başlangıçta şüpheci olan Gödel, Turing'in analizini kesin olarak görmeye başlamış ve birleşik iddia Church–Turing tezi olarak bilinir hale gelmiştir.
Tartışmalar
- Fiziksel hesaplama Turing sınırını aşabilir mi?
- Orijinal tez etkili prosedürlerle ilgilidir, ancak daha güçlü fiziksel versiyonlar, fiziksel olarak gerçekleştirilebilir hiçbir cihazın Turing-hesaplanabilir olmayan fonksiyonları hesaplayamayacağını iddia etmektedir. Hiperhesaplama (hypercomputation) önerileri ve kuantum mekaniğinin çıkarımları, klasik tez esasen sorgulanmadan kalsa bile, bu genişletilmiş iddiayı tartışmalı kılmaktadır.
Öne çıkan isimler
- Alonzo Church
- Alan Turing
- Kurt Gödel
- Stephen Kleene
İlgili konular
Temel eserler
- church1936
- turing1937
Sıkça sorulan sorular
- Neden bir teoremden ziyade bir tez olarak adlandırılmaktadır?
- Resmi bir modeli, etkili bir prosedürün gayri resmi fikrine bağlamaktadır ve bu gayri resmi fikrin hakkında bir şeyler kanıtlamak için matematiksel bir tanımı bulunmamaktadır. Güçlü kanıt, hesaplamayı resmileştirmeye yönelik her bağımsız girişimin aynı fonksiyon sınıfını ortaya çıkarmış olmasıdır, ancak bu destek bir kanıttan ziyade kavramsaldır.
- Kuantum bilgisayarlar Church–Turing tezini çürütmekte midir?
- Hayır. Kuantum bilgisayarlar bazı problemleri daha hızlı çözebilmektedir, ancak Turing makineleriyle tam olarak aynı fonksiyon sınıfını hesaplamaktadırlar; bu nedenle hesaplanabilir olanla ilgili orijinal tez geçerliliğini korumaktadır. Bunun yerine, hesaplanabilirlikten ziyade verimlilikle ilgili daha güçlü karmaşıklık-teorik versiyonla ilişkilidirler.