Church-Turing tezi, mantık, matematik ve bilgisayar bilimlerinde verimli, sistematik veya mekanik bir yöntem kavramına atıfta bulunur. Sezgisel hesaplanabilirlik kavramının bir açıklaması olarak formüle edilmiştir ve genel özyinelemeli işlevlerle ilgili olarak daha çok Church'ün tezi olarak adlandırılır. Aynı zamanda bilgisayarla hesaplanabilir fonksiyonlar teorisine de atıfta bulunur. Tez, bilgisayarların henüz var olmadığı 1930'larda ortaya çıktı. Daha sonra adını Amerikalı matematikçi Alonso Church ve İngiliz meslektaşı Alan Turing'den almıştır.
Sonuca ulaşmak için yöntemin verimliliği
Modern bir bilgisayara benzeyen ilk cihaz, İngiliz matematikçi Alan Turing tarafından yaratılan Bombie makinesiydi. Dünya Savaşı sırasında Alman mesajlarını deşifre etmek için kullanıldı. Ancak tezi ve algoritma kavramının resmileştirilmesi için daha sonra Turing makineleri olarak adlandırılan soyut makineler kullandı. tez sunarhem matematikçiler hem de programcılar için ilgi çekiciydi, çünkü bu fikir ilk bilgisayarların yaratıcılarına ilham verdi.
Hesaplanabilirlik teorisinde, Church-Turing tezi, hesaplanabilir fonksiyonların doğası hakkında varsayım olarak da bilinir. Doğal sayılar üzerinde algoritmik olarak hesaplanabilen herhangi bir fonksiyon için, onu hesaplayabilen bir Turing makinesi olduğunu belirtir. Veya başka bir deyişle buna uygun bir algoritma vardır. Bu yöntemin etkililiğinin iyi bilinen bir örneği, totolojiyi test etmek için yapılan doğruluk tablosu testidir.
İstenen herhangi bir sonucu elde etmenin bir yolu şu durumlarda "etkili", "sistematik" veya "mekanik" olarak adlandırılır:
- Yöntem, sınırlı sayıda kesin talimat cinsinden belirtilir, her talimat sınırlı sayıda karakter kullanılarak ifade edilir.
- Hatasız çalışacak, belirli sayıda adımda istenen sonucu üretecektir.
- Yöntem, bir insan tarafından kağıt ve kalem dışında herhangi bir ekipman olmadan gerçekleştirilebilir
- Eylemi gerçekleştiren kişinin anlayışı, sezgisi veya ustalığı gerektirmez
Daha önce matematikte, "etkili bir şekilde hesaplanabilir" gayri resmi terimi, kalem ve kağıtla hesaplanabilen fonksiyonlara atıfta bulunmak için kullanılıyordu. Ancak algoritmik hesaplanabilirlik kavramı, somut olan her şeyden daha sezgiseldi. Şimdi, bir hesaplama algoritması olan doğal bir argümana sahip bir fonksiyon ile karakterize edildi. Alan Turing'in başarılarından biri,Yöntem etkinlik koşulu kullanılıyorsa, resmi olmayan bir yüklemin yardımıyla değiştirilebilecek resmi olarak kesin bir yüklemin temsili. Kilise de aynı keşfi yaptı.
Özyinelemeli işlevlerin temel kavramları
Turing'in yüklemleri ilk bakışta değiştirmesi, meslektaşının önerdiğinden farklı görünüyordu. Ancak sonuç olarak, her birinin aynı matematiksel fonksiyon setini seçmesi anlamında eşdeğer oldukları ortaya çıktı. Church-Turing tezi, bu kümenin, verim koşullarını sağlayan bir yöntemle değerleri elde edilebilen her fonksiyonu içerdiği iddiasıdır. İki keşif arasında bir fark daha vardı. Turing, çalışmasını bir integral veya gerçek değişkenle hesaplanabilir fonksiyonları kapsayan olarak tanımlarken Church'ün yalnızca pozitif tamsayı örneklerini dikkate almasıydı.
Genel özyinelemeli işlevler
Church'ın orijinal formülasyonu, hesaplamanın λ-hesabı kullanılarak yapılabileceğini belirtir. Bu, genel özyinelemeli işlevleri kullanmaya eşdeğerdir. Church-Turing tezi, başlangıçta düşünülenden daha fazla türde hesaplamayı kapsar. Örneğin, hücresel otomatlar, birleştiriciler, kayıt makineleri ve ikame sistemleri ile ilgili. 1933'te matematikçiler Kurt Gödel ve Jacques Herbrand, genel özyinelemeli işlevler adı verilen bir sınıfın resmi bir tanımını oluşturdular. Birden fazla argümanın mümkün olduğu işlevleri kullanır.
Yöntem oluşturmaλ-hesabı
1936'da Alonso Church, λ-hesabı adı verilen bir belirleme yöntemi yarattı. Doğal sayılarla ilişkilendirildi. λ-hesabı içinde, bilim adamı kodlamalarını belirledi. Sonuç olarak, bunlara Kilise numaraları denir. Doğal sayılara dayalı bir fonksiyona λ-hesaplanabilir denir. Başka bir tanım vardı. Church'ün tezindeki fonksiyona iki koşulda λ-hesaplanabilir denir. İlki şuna benziyordu: eğer Kilise öğeleri üzerinde hesaplanmışsa ve ikinci koşul, λ-hesabının bir üyesi tarafından temsil edilme olasılığıydı.
Ayrıca 1936'da, meslektaşının çalışmalarını incelemeden önce Turing, şimdi kendi adını taşıyan soyut makineler için teorik bir model yarattı. Banttaki karakterleri manipüle ederek hesaplamalar yapabilirler. Bu aynı zamanda kuantum olasılıksal hesaplama gibi teorik bilgisayar biliminde bulunan diğer matematiksel etkinlikler için de geçerlidir. Church'ün tezinin işlevi ancak daha sonra bir Turing makinesi kullanılarak doğrulandı. Başlangıçta, λ-hesabına güvendiler.
İşlev hesaplanabilirliği
Doğal sayılar karakter dizileri olarak uygun şekilde kodlandığında, soyut makine gerekli algoritmayı bulup bu işlevi teybe yazdırırsa, doğal sayılar üzerindeki bir fonksiyonun Turing-hesaplanabilir olduğu söylenir. 1930'larda var olmayan böyle bir cihaz, gelecekte bilgisayar olarak kabul edilecekti. Soyut Turing makinesi ve Church'ün tezi, bir gelişme çağının habercisiydi.bilgi işlem cihazları. Her iki bilim adamı tarafından resmi olarak tanımlanan işlev sınıflarının çakıştığı kanıtlandı. Bu nedenle, sonuç olarak, her iki ifade de birleştirildi. Hesaplamalı fonksiyonlar ve Church'ün tezi de hesaplanabilirlik kavramı üzerinde güçlü bir etkiye sahipti. Ayrıca matematiksel mantık ve ispat teorisi için önemli bir araç haline geldiler.
Yöntemin gerekçesi ve sorunları
Tezle ilgili çelişkili görüşler var. 1936'da Church ve Turing tarafından önerilen "çalışan hipotez" için sayısız kanıt toplandı. Ancak, verili olanlardan etkin biçimde hesaplanabilir yeni işlevleri keşfetmek için bilinen tüm yöntemler veya işlemler, o zamanlar var olmayan makine yapım yöntemleriyle bağlantılıydı. Church-Turing tezini kanıtlamak için, her gerçekçi hesaplama modelinin eşdeğer olduğu gerçeğinden yola çıkılır.
Farklı analizlerin çeşitliliği nedeniyle, bu genellikle özellikle güçlü bir kanıt olarak kabul edilir. Etkili bir şekilde hesaplanabilir bir fonksiyonun sezgisel kavramını daha kesin olarak tanımlamaya yönelik tüm girişimlerin eşdeğer olduğu ortaya çıktı. Önerilen her analizin aynı fonksiyon sınıfını, yani Turing makineleri tarafından hesaplanabilenleri ayırdığı kanıtlanmıştır. Ancak bazı hesaplama modellerinin farklı görevler için zaman ve bellek kullanımı açısından daha verimli olduğu ortaya çıktı. Daha sonra özyinelemeli fonksiyonların temel kavramlarının ve Church'ün tezinin oldukça varsayımsal olduğu belirtildi.
Tez M
Turing'in tezi ile bir bilgisayar cihazı tarafından hesaplanabilen her şeyin onun makinesi tarafından hesaplanabileceği iddiası arasında ayrım yapmak önemlidir. İkinci seçeneğin kendi tanımı vardır. Gandhi ikinci cümleye "Tez M" diyor. Şöyle devam eder: "Bir cihaz tarafından hesaplanabilen her şey, bir Turing makinesi tarafından da hesaplanabilir." Tezin dar anlamıyla, doğruluk değeri bilinmeyen ampirik bir önermedir. Turing'in Tezi ile "M Tezi" bazen karıştırılır. İkinci versiyon genel olarak yanlıştır. Turing ile hesaplanamayan fonksiyonları hesaplayabilen çeşitli koşullu makineler tanımlanmıştır. İlk tezin ikinciyi içermediğini, ancak yanlışlığıyla tutarlı olduğunu belirtmek önemlidir.
Tezin ters anlamı
Hesaplanabilirlik teorisinde, Church'ün tezi, bir genel özyinelemeli fonksiyonlar sınıfı tarafından hesaplanabilirlik kavramının bir açıklaması olarak kullanılır. Amerikalı Stephen Kleene daha genel bir formül verdi. Algoritmalar tarafından hesaplanabilen kısmi özyinelemeli tüm kısmi işlevleri çağırdı.
Ters ima genellikle Church'ün ters tezi olarak adlandırılır. Pozitif tam sayıların her özyinelemeli fonksiyonunun verimli bir şekilde değerlendirilmesi gerçeğinde yatmaktadır. Dar anlamda, bir tez basitçe böyle bir olasılığı ifade eder. Ve daha geniş anlamda, bu koşullu makinenin içinde bulunup bulunamayacağı sorusundan soyutlar.
Kuantum bilgisayarlar
Hesaplanabilir fonksiyon kavramları ve Church'ün tezi matematik, makine teorisi ve diğer birçok bilim için önemli bir keşif haline geldi. Ancak teknoloji çok değişti ve gelişmeye devam ediyor. Kuantum bilgisayarların, modern olanlardan daha kısa sürede birçok ortak görevi gerçekleştirebileceği varsayılmaktadır. Ancak durma sorunu gibi sorular devam ediyor. Bir kuantum bilgisayar buna cevap veremez. Ve Church-Turing tezine göre başka bir bilgi işlem cihazı da yok.
