Church–Turing tezi

Açılış sahnesi

Kerem, masaya bir liste yazıyor. Birinci satırda Turing'in makineleri. İkinci satırda Post'un kutular üzerinde çalışan işçisi. Üçüncü satırda Markov'un yeniden yazma kuralları. Dördüncü satırda Church'ün işlevleri tanımlama yöntemi. Beşinci satırda Gödel ile Herbrand'ın özyinelemeli işlevleri. Beş tanım, beş farklı fikirden doğmuştu: biri bir insanın kâğıt üzerindeki hareketlerinden, biri işaret dizilerinin değiştirilmesinden, biri işlevlerin birbirinden tanımlanmasından. Ama Kerem'in okuduğu kaynaklara göre, beşinin de hesaplayabildiği işlevler tam olarak aynıydı.

Tolga, bu örtüşmenin, bütün bu tanımların aynı şeyi, sezgisel algoritma kavramını yakaladığının bir kanıtı olup olmadığını soruyor. Selin, bir gün beşinden de güçlü bir altıncı tanımın bulunup bulunamayacağını merak ediyor. Lina, sezgisel bir kavramın kesin bir tanımla ne zaman "yakalanmış" sayılabileceğini, bir çevirinin özgün metni ne zaman karşıladığını sorar gibi düşünüyor. Barış, farklı mahkemelerin aynı belirsiz kavramı farklı yollardan aynı biçimde yorumlamasının, o kavramın anlamının belirlendiği anlamına gelip gelmediğini soruyor. Defne ise canlı bir hücrenin ya da bir fiziksel sistemin, bir Turing makinesinin hesaplayamadığı bir şeyi hesaplayıp hesaplayamayacağını merak ediyor. Bu ders, Mantık ve Akıl Yürütme programının Metalojik ve Hesaplanabilirlik kursunda, sezgisel olarak hesaplanabilir olan her şeyin bir Turing makinesiyle hesaplanabildiğini söyleyen tezin ne tür bir iddia olduğunu, birbirinden bağımsız tanımların örtüşmesinin onu nasıl desteklediğini ve tezin kanıtlanabilir bir teorem mi, bir tanım mı, yoksa bir doğa yasası mı olduğunu soruyor.

Bu derste ne olacak

Önce bu dersin yerini belirleyelim. Algoritma dersi, algoritmanın sezgisel kavramını ve Markov'un yeniden yazma kurallarını tanıttı. Turing makinesi dersi ise Turing'in insan hesapçı çözümlemesini, Post'un işçi modelini ve evrensel makineyi inceledi. Metateori modülünün Karar verilebilirlik dersinde, karar verilemezlik sonuçlarına yöneltilen bir itiraza cevap verirken, bu tezin adı ve bağımsız tanımların örtüşmesi kısaca anılmıştı. Akademinin önceki bir programında da Carnap'ın açımlama kavramı tanımlanmıştı. Bu ders, o kısa anmayı bir tartışmaya dönüştürüyor: tezin ne dediğini, neye dayandığını ve ne tür bir iddia olduğunu inceliyor.

Sonra üç kaynağa bakacağız. Alonzo Church, 1936'da yayımladığı Temel Sayılar Kuramının Çözümsüz Bir Problemi makalesinde, etkin olarak hesaplanabilir işlevleri, kendi tanımladığı bir sınıfla özdeşleştirmeyi önerir. Stephen Kleene, 1952'de yayımladığı Üst Matematiğe Giriş kitabında, bu önerileri Church'ün tezi ve Turing'in tezi adlarıyla ele alır ve onları destekleyen kanıtları sistemli biçimde toplar. Robin Gandy ise 1980'de yayımladığı Church'ün Tezi ve Mekanizmalar İçin İlkeler makalesinde, tezin insan hesapçıdan mekanik aygıtlara genişletilip genişletilemeyeceğini inceler.

Ardından üç itirazı tartacağız: tezin kanıtlanamadığı için gerekçesiz olduğu, sezgisel olarak hesaplanabilir ama Turing makinesiyle hesaplanamayan bir işlevin bulunabileceği ve bazı fiziksel sistemlerin Turing makinelerinin sınırını aşabileceği itirazları.

Sonda, bir hesaplanabilirlik iddiasını değerlendirmenin dört adımını göstereceğiz: iddianın hangi sezgisel kavramı konu aldığını belirlemek, bu kavramın hangi kesin tanımla karşılandığını yazmak, iddianın kolay ve zor yönlerini ayırmak ve iddianın bir insan hesapçı hakkında mı yoksa bir fiziksel sistem hakkında mı olduğunu sormak.

Merkez soru

Sorumuz şu: sezgisel olarak hesaplanabilir olan her şeyin bir Turing makinesiyle hesaplanabildiğini söyleyen tez ne tür bir iddiadır ve neye dayanır?

Ölçülü iddiam şu: Church–Turing tezi, sezgisel bir kavram ile kesin bir kavram arasında bir özdeşlik kurar. Etkin olarak hesaplanabilir işlevler, yani bir insanın kurala uyarak, sonlu adımda hesaplayabildiği işlevler, tam olarak Turing makinesiyle hesaplanabilen işlevlerdir. Tez bir teorem değildir, çünkü iki yanından biri kesin olarak tanımlanmamıştır. Ama keyfi bir tanım da değildir. İki yönü vardır ve bu yönler farklı ağırlıktadır. Kolay yönü, her Turing makinesinin yaptığı hesabın sezgisel olarak etkin olduğudur; bu, makinenin tanımına bakarak görülür. Zor yönü, sezgisel olarak etkin her hesabın bir Turing makinesiyle yapılabildiğidir. Bu yön üç tür kanıta dayanır. Birincisi örtüşmedir: Church'ün, Gödel ile Herbrand'ın, Turing'in, Post'un ve Markov'un birbirinden çok farklı tanımlarının aynı işlevleri kapsadığı kanıtlanmıştır. İkincisi çözümlemedir: Turing'in tanımı, bir insanın kurala uyarak hesap yaparken ne yaptığının dikkatli bir çözümlemesinden türetilmiştir. Üçüncüsü karşı örneğin yokluğudur: sezgisel olarak etkin olduğu kabul edilen hiçbir işlevin bu tanımların dışında kaldığı gösterilmemiştir. Bu yüzden tez en iyi bir açımlama olarak anlaşılır: belirsiz bir gündelik kavramın, onun yerine geçmeye elverişli kesin bir kavramla değiştirilmesi. Tezin insan hesapçı hakkındaki biçimi ile fiziksel sistemler hakkındaki biçimi ayrı iddialardır. Birincisi güçlü bir kavramsal dayanağa sahiptir. İkincisi ise fizik hakkında deneysel bir iddiadır ve Gandy'nin gösterdiği gibi, ek varsayımlar gerektirir.

Sıfır noktası

Bir öğrenci Church–Turing tezini ilk duyduğunda, onu bir teorem sanar. Teorem ya da tanım gibi görünür, çünkü mantık kitaplarında teoremlerin arasında durur. Ama tez, öteki teoremlerden farklı bir yapıdadır. Bir teorem, kesin olarak tanımlanmış kavramlar arasında bir ilişki kurar ve bir kanıtla gösterilir. Tez ise kesin bir kavramı, Turing makinesiyle hesaplanabilirliği, kesin olmayan bir kavramla, sezgisel etkin hesaplanabilirlikle özdeşleştirir.

Bu yüzden tez, bir kanıtla gösterilemez. Bir kanıt, kesin kavramlar arasında işler. Sezgisel bir kavram ise kanıtın bir öncülü olamaz, çünkü onun tam olarak neyi kapsadığı bilinmez. Ama tez, bu yüzden bir tahmin ya da bir inanç da değildir. Onu destekleyen güçlü nedenler vardır ve bu nedenler, bir kanıttan farklı ama bir kanıt kadar ciddi bir yapı taşır.

Tezin önemi, karar verilemezlik sonuçlarında ortaya çıkar. Turing makineleri için kanıtlanan bir sonuç, örneğin durma probleminin çözümsüzlüğü, kesin bir teoremdir. Ama bu sonucun "hiçbir algoritma bu sorunu çözemez" biçiminde okunabilmesi, tezin kabul edilmesine bağlıdır. Tez, kesin sonuçları sezgisel kavramlara bağlayan köprüdür.

Görüşler ve pozisyonlar

Church–Turing tezinin ne tür bir iddia olduğu konusunda üç görüş var.

Birinci görüş, tanım görüşüdür. Buna göre tez, "etkin olarak hesaplanabilir" ifadesinin bir tanımıdır. Church'ün kendisi tezi bir tanım olarak sunmuştu. Bir tanım doğru ya da yanlış olmaz; yalnızca yararlı ya da yararsız olur.

İkinci görüş, deneysel hipotez görüşüdür. Buna göre tez, doğrulanmaya ve çürütülmeye açık bir hipotezdir. Post'un sözleriyle, bir doğa yasası gibi sürekli doğrulanması gerekir. Bir gün Turing makinelerinin yapamadığı bir hesabı yapan bir yöntem bulunursa, tez çürür.

Üçüncü görüş, açımlama görüşüdür. Buna göre tez, belirsiz bir gündelik kavramın, onun yerine geçmeye elverişli kesin bir kavramla değiştirilmesidir. Carnap'ın tanımladığı anlamda bir açımlamadır. Bir açımlama, tanımdan fazlasıdır, çünkü sezgisel kavrama sadık olmalıdır. Ama bir hipotez de değildir, çünkü sezgisel kavram kesinleşmeden önce tam olarak neyi kapsadığı sorulamaz.

Bu ders üçüncü görüşü temel alır ve birinci ile ikinci görüşün birer gözlemini kabul eder. Birinci görüş, tezin kesin kavramı sezgisel kavramın yerine koyduğunu doğru görür. Ama bu yerine koymanın keyfi olmadığını, sezgisel kavrama sadık olması gerektiğini hesaba katmaz. İkinci görüş, tezin karşı örneklere açık olduğunu doğru görür. Ama bir karşı örneğin ne olacağını, sezgisel kavram belirsiz kaldığı sürece kesin olarak söylemek zordur. Üçüncü görüş, iki gözlemi birlikte tutar.

Argümanın yapısı

Bir hesaplanabilirlik iddiasını değerlendirmek için dört adım izlenebilir.

Birinci adım, iddianın hangi sezgisel kavramı konu aldığını belirlemektir. Değerlendiren, iddianın bir insanın kurala uyarak yaptığı hesap hakkında mı, bir makinenin yaptığı hesap hakkında mı, yoksa herhangi bir fiziksel sürecin davranışı hakkında mı olduğunu yazar.

İkinci adım, bu kavramın hangi kesin tanımla karşılandığını yazmaktır. Değerlendiren, iddianın Turing makineleri, özyinelemeli işlevler ya da başka bir kesin tanım üzerinden mi kurulduğunu belirtir.

Üçüncü adım, iddianın kolay ve zor yönlerini ayırmaktır. Değerlendiren, kesin tanımın sezgisel kavramın içinde kaldığını söyleyen yönü, sezgisel kavramın kesin tanımın içinde kaldığını söyleyen yönden ayırır ve her birinin neye dayandığını yazar.

Dördüncü adım, iddianın bir insan hesapçı hakkında mı yoksa bir fiziksel sistem hakkında mı olduğunu sormaktır. Değerlendiren, iddiayı desteklemek için kavramsal bir çözümlemenin mi, yoksa fizik hakkında deneysel bilginin mi gerektiğini belirler.

En güçlü itiraz

Bu yaklaşıma üç yönden ciddi itiraz yapılabilir.

Church–Turing tezini ciddiye alan düşünce şu cevabı verebilir. Tez, sezgisel olarak etkin hesaplanabilir işlevlerin tam olarak Turing makinesiyle hesaplanabilen işlevler olduğunu söyler. Bir yanı kesin olarak tanımlanmadığı için teorem değildir. Tolga'nın iki yönünde görüldüğü gibi, kolay yönü tanımlardan neredeyse kendiliğinden çıkar, zor yönü ise ayrı dayanaklar gerektirir. Kerem'in denklik listesinde görüldüğü gibi, bu dayanakların ilki birbirinden bağımsız tanımların kanıtlanmış örtüşmesidir. Church tezi baştan bu örtüşmeye dayandırdı. Kleene, teze bugünkü adıyla yer verdi ve onu destekleyen kanıtları örtüşme, karşı örneğin yokluğu ve Turing'in çözümlemesi olarak üç grupta topladı. Lina'nın açımlamasında görüldüğü gibi, tez en iyi, belirsiz bir kavramı kesin bir kavramla değiştiren ve bunu yaparken onun kenarlarını keskinleştiren bir açımlama olarak anlaşılır. Barış'ın yorum birliğinde görüldüğü gibi, tanımların kavramın her yerinde tam olarak örtüşmesi, keskin bir çekirdeğin varlığını düşündürür. Gandy, tezin makul fiziksel ilkeleri karşılayan mekanik aygıtlara genişletilebildiğini gösterdi. Ama Defne'nin hücresinde görüldüğü gibi, tezin fiziksel sistemler hakkındaki biçimi, fizik hakkında deneysel bir iddiadır ve insan hesapçı hakkındaki tezden ayrı tutulmalıdır.

Açık kalan sorular

Lina'nın açımlaması, tezin sezgisel kavramı yalnızca yakalamadığını, onun belirsiz kenarlarını da keskinleştirdiğini gösterdi. Tezden sonra "etkin hesaplanabilir" ifadesini kullanan biri, tezden önce kullanandan farklı bir kavram mı kullanır? Bir açımlama, açımladığı kavramı değiştirir mi?

Kalmár türünden itiraza verilen cevap, etkin hesaplanabilirliği matematikçilerin yapabildiği her şeyden ayırdı. Öyleyse matematikçilerin yaratıcılığının bir sınırı var mıdır? Bir matematikçinin bulabildiği her sonucu, yeterince güçlü bir makine de bulabilir mi?

Defne'nin hücresi, bir fiziksel sürecin bir hesap yapıp yapmadığı sorusunu doğurdu. Bir fiziksel sürecin bir hesap sayılması için ne gerekir? Bir şelalenin akışı ya da bir gezegenin yörüngesi, bir işlevi hesaplıyor sayılabilir mi?

Yaygın hatalar

Kendin dene

Aklında kalsın

Beş cümlede dersin iskeleti.

Church–Turing tezi, sezgisel olarak etkin hesaplanabilir işlevlerin tam olarak Turing makinesiyle hesaplanabilen işlevler olduğunu söyler; bir yanı kesin olarak tanımlanmadığı için teorem değildir ve en iyi bir açımlama olarak anlaşılır.

Church'ün 1936 tarihli makalesi etkin hesaplanabilirliği kesin bir sınıfla özdeşleştirmeyi ilk kez önerdi, Kleene'nin Üst Matematiğe Giriş kitabı teze bugünkü adıyla yer verip onu destekleyen kanıtları örtüşme, karşı örneğin yokluğu ve Turing'in çözümlemesi olarak topladı, Gandy'nin 1980 tarihli makalesi ise tezin açıkça belirtilmiş fiziksel ilkeler altında mekanik aygıtlara genişletilebildiğini gösterdi.

Bir hesaplanabilirlik iddiası dört adımla değerlendirilir: hangi sezgisel kavramı konu aldığını belirlemek, hangi kesin tanımla karşılandığını yazmak, kolay ve zor yönlerini ayırmak ve bir insan hesapçı hakkında mı yoksa bir fiziksel sistem hakkında mı olduğunu sormak.

Tezin kanıtlanamadığı için gerekçesiz olduğu, sezgisel olarak hesaplanabilir ama Turing makinesiyle hesaplanamayan bir işlevin bulunabileceği ve fiziksel sistemlerin Turing makinelerinin sınırını aşabileceği itirazları, tezin bağımsız kanıt gruplarına dayanan bir açımlama olduğunu, etkin hesabın sezgiden değil kurala uymadan oluştuğunu ve fiziksel tezin insan hesapçı tezinden ayrı bir deneysel iddia olduğunu gördüğümüzde cevaplanabilir.

Bu yüzden Church–Turing tezi, Turing makineleri hakkında kanıtlanan kesin sonuçları, "hiçbir algoritma bunu yapamaz" gibi sezgisel sonuçlara bağlayan köprüdür ve bu köprünün sağlamlığı, bir kanıttan değil, birbirinden bağımsız dayanakların örtüşmesinden gelir.

Sonraki derse köprü

Church–Turing tezi, Turing makineleri hakkında kanıtlanan bir sonucu algoritmalar hakkında bir sonuç olarak okumaya izin veriyordu. Karar verilebilirlik dersinde görülen durma problemi, bu tür sonuçların ilki ve en temeliydi: bir programın durup durmayacağını her durumda belirleyen bir algoritma yoktu. Ama Kerem, o derste bu sonucun kanıtının yalnızca ana hatlarını gördüklerini hatırlıyor.

Tolga, kanıtın bir programı kendi kodu üzerinde çalıştırmaya dayandığını ve bunun, evrensel makinenin bir programın betimlemesini okuyabilmesi sayesinde mümkün olduğunu fark ediyor. Selin, bu yapının Cantor'un gerçek sayıların sayılamaz olduğunu gösteren köşegen argümanına benzediğini söylüyor. Defne, durma probleminin çözümsüzlüğünden, başka hangi soruların da çözümsüz olduğunun çıkarılabileceğini soruyor.

Bir sonraki ders bu soruya dönüyor. Durma problemi dersi, bir programın durup durmayacağını her durumda belirleyen bir algoritmanın neden var olamayacağını gösteren köşegen argümanının adımlarını, bu argümanın evrensel makineye ve kendine gönderime nasıl dayandığını ve durma probleminin çözümsüzlüğünden başka soruların çözümsüzlüğünün indirgeme yoluyla nasıl çıkarıldığını soruyor.