Teorik bilgisayar bilimindeki zombi yanılgısı

 (scottaaronson.blog)
1 puan yazan GN⁺ 2024-07-11 | 1 yorum | WhatsApp'ta paylaş
  • Teorik bilgisayar biliminde hesaplanabilirlik ve NP-hard kavramları, tek tek tamsayılara ya da tek bir doğru/yanlış sorusuna değil; fonksiyonlara, dillere ve sonsuz dizilere uygulanır
  • Sipser’in örneğinde “Tanrı varsa her zaman 1, yoksa her zaman 0 döndüren f fonksiyonu”, her iki durumda da sabit bir fonksiyon olduğu için hesaplanabilirdir
  • P vs NP, girdi alan bir problem değil tek bir evet/hayır sorusu olduğundan, kendi başına NP-hard ya da hesaplanamaz olarak adlandırılamaz
  • Busy Beaver fonksiyonunun tamamı hesaplanamazdır, ancak BB(6) gibi belirli bir değer, herhangi bir tamsayı k için print k programı var olduğundan aynı şekilde ele alınamaz
  • Tekrarlanan karışıklığın özü, sonsuz nesneler için olan kavramları tekil problemlere uygulamaktır; durma probleminin hesaplanamazlığı ile Gödel’in eksiklik teoremini karıştırma alışkanlığı da aynı türdendir

Sipser örneğinin öğrettiği hesaplanabilirliğin kapsamı

  • Michael Sipser’in Introduction to the Theory of Computation kitabında, hesaplanabilirliğin tanımını ortaya koyan bir ödev sorusu vardır
    • f:{0,1}*→{0,1}, Tanrı varsa her zaman 1 döndüren, yoksa her zaman 0 döndüren bir fonksiyon olarak tanımlanır
    • Soru, f’nin hesaplanabilir olup olmadığıdır ve yanıt dinî inançtan bağımsızdır
  • f hesaplanabilirdir
    • Her zaman 1 döndüren sabit fonksiyon hesaplanabilirdir
    • Her zaman 0 döndüren sabit fonksiyon da hesaplanabilirdir
    • f bu ikisinden biri ise, f de hesaplanabilirdir
  • Aynı yapıya sahip paralel bir soru da aynı sezgiyi verir
    • “Tanrı varsa n=3, yoksa n=5 iken n asal mıdır” sorusunda, n tamamen belirlenmemiş olsa da {3,5} kümesinin bir elemanı olduğu bilgisiyle asal denebilir
    • f için de aynı durum geçerlidir: sadece hangi sabit fonksiyon olduğu değişir, ama hesaplanabilir olduğuna hükmetmek için yeterince belirlenmiştir

Hesaplanabilirlik, program yazmanın zorluğu değil varlığıyla ilgilidir

  • Hesaplanabilirlik, fonksiyonlara ve sonsuz dizilere uygulanan bir kavramdır
  • Tek bir evet/hayır sorusuna ya da tek bir tamsayıya aynı şekilde hesaplanabilirlik atfedilmez
  • Temel soru, girdileri çıktılara eşleyen bir bilgisayar programının var olup olmadığıdır
  • O programı seçmenin, bulmanın ya da yazmanın ne kadar zor olduğu, hesaplanabilirlik tanımının parçası değildir
    • Programı yazmak için Tanrı’nın varlığı sorusunu çözmek gerekse bile, bu durum hesaplanabilirlik yargısını değiştirmez

P vs NP’ye neden NP-hard denemez

  • “P versus NP sorusunun kendisi NP-hard olduğu için mi çözülemiyor” sorusu son 25 yılda birçok kez tekrarlandı
  • NP-hard, 3SAT, Independent Set, Clique gibi girdi alan fonksiyonlara ya da dillere uygulanır
    • Girdi bir Boolean formula, graph vb.dir
    • Çıktı, o girdiye ilişkin yanıttır
    • Bir problem polinomsal zamanda çözülebiliyorsa ve indirgeme yoluyla NP içindeki tüm diller ya da fonksiyonlar da polinomsal zamanda çözülebiliyorsa, o problem NP-hard olarak adlandırılır
  • P vs NP, bir fonksiyon ya da dil değil, tek bir evet/hayır sorusudur
    • Cevabının Zermelo-Fraenkel küme kuramı aksiyomlarından bağımsız olma ihtimali dışlanmış değildir
    • Ancak bu sorunun kendisini hesaplanamaz ya da NP-hard olarak adlandırmak mümkün değildir
  • P vs NP sorusuna tam doğru cevabı veren hızlı bir program biçimsel olarak vardır
    • P=NP ise “P=NP” yazdıran program
    • P≠NP ise “P≠NP” yazdıran program

Busy Beaver’da tekrarlanan aynı karışıklık

  • Busy Beaver 5 değerinin belirlendiğine dair yazının yorumlarında da benzer sorular tekrarlandı
    • “BB(n) değerinin hesaplanamaz hale geldiği en küçük n nedir?”
    • “BB(6) zaten hesaplanamaz olabilir mi?”
  • Busy Beaver fonksiyonu hesaplanamazdır
  • Ancak BB(6) gibi tekil tamsayılara hesaplanabilirlik kavramı bu şekilde uygulanmaz
    • BB(6) hangi tamsayı k çıkarsa çıksın, print k programı vardır
    • Bu program o tamsayıyı yazdırır
  • Bunun yerine sorulabilecek şey, hangi n için BB(n) değerinin ZF küme kuramı gibi bir aksiyom sisteminde kanıtlanamaz olduğudur
    • Aaronson ve Adam Yedidia bu soruyu 2016’da ele aldı
    • Mevcut rekor n=745’tir; bu da Aaronson ile Adam’ın n=8000 sonucunu iyileştiren bir değerdir
  • Her belirli tamsayı “hesaplanabilir” sayılabilir; hesaplanamaz olan şey BB fonksiyonunun tamamıdır

“Zombi yanılgısı” neden yaşamaya devam ediyor

  • Tekrarlanan karışıklığın özü, sonsuz diziler ve fonksiyonlar için tasarlanmış kavramların tekil tamsayılara ve açık problemlere yanlış uygulanmasıdır
  • Durma probleminin hesaplanamazlığı ile Gödel’in eksiklik teoreminin karıştırıldığı örnekler de aynı türden bir karışıklıktır
    • İkisi yakından ilişkilidir
    • Gödel, tekil önermeler hakkında konuşmayı mümkün kılar
    • Turing hesaplanabilirliği, belirli bir aksiyom sistemine göreli değil, mutlak bir kavramdır
  • Bu açıklama, aynı eğitsel yanılgı yeniden ortaya çıktığında başvurulabilecek bir referans noktası işlevi görür
  • Son soru, bu “zombi” benzeri yanılgıların nasıl etkisiz hale getirilebileceğine odaklanır

İlgili okumalar

1 yorum

 
GN⁺ 2024-07-11
Hacker News yorumları

  • Hesaplanabilirlik kavramının kaçınılmaz olarak sonsuzu içermesi epey sezgiye aykırı gelebilir
    Örneğin, keyfi bir s dizgesi için Kolmogorov karmaşıklığı K(s)yi hesaplayan bir algoritma olup olmadığını sorarsanız, yanıt bilindiği üzere “yok”tur. Keyfi uzunlukta bir dizgeyi girdi alıp K(s)yi hesaplayan bir Turing makinesi yoktur; kanıt da durma problemini kullanarak kısa biçimde tamamlanır
    Ama uzunluğu nden küçük keyfi bir s dizgesi için K(s)yi hesaplayan bir algoritma olup olmadığını sorarsanız, yanıt “var”dır. Herhangi bir n için böyle bir algoritma vardır
    Yöntem hayal kırıklığı yaratacak kadar basittir: Olası 2^n dizgenin tamamı için K(s) değerlerini içeren devasa bir arama tablosu olan bir Turing makinesi yapmak yeterlidir. O tabloyu pratikte nasıl elde edeceğiniz ayrı bir konudur; belirli bir uygulama sonlu bir betimlemeye sahiptir ve K(s) de tüm sler için sonlu olduğundan algoritma vardır
    Bu yüzden sonlu nesnelere dair sonlu sorular, hesaplanabilirlik açısından pek ilginç olmayabilir. Çünkü her zaman tüm yanıtları çıktılacak bir program yazabilirsiniz; asıl ilginç olan, soru sonsuz bir nesne kümesine genişlediğinde sonlu bir şeyin sonsuz sayıda soruya yanıt verip veremeyeceğidir

    • Böyle bir açıklama, bilgisayar biliminin büyük bir bölümünü düpedüz gülünç ve anlamsız bir oyun gibi gösterebilir
      Aslında sonsuz, “herhangi tek seferlik bir numaradan yeterince büyük Nlerdeki yaklaşık, nihai, kararlı durum davranışının” yerini tutuyor
      Gerçek dünyada bu tür numaralar da önemlidir; big-O karşılaştırmalarında göz ardı edilen sabitler ve düşük dereceli terimler de gerçek performans için önemlidir. “Sabit çarpanın anlamsızlaşacağı kadar büyük problem” ile “sabit sözcüğünün örtük olarak ima ettiği aralığa girecek kadar küçük problem” arasında her zaman bir gerilim vardır. Örneğin 32 bit tamsayıların tamsayıymış gibi davranması böyledir
    • Elbette n, tanımı gereği sonlu bir sayı olduğu için böyle bir algoritma vardır
      Sonsuzluk açısından bakıldığında tüm sonlu sayılar aslında çok küçüktür. Evrenin ucundaki bir sandalyede oturup bakarsanız 1 mil de 1 milimetreden farksızdır
      Bu senaryo fiilen “bilgisayar üzerindeki Hilbert’in sonsuz oteli” gibidir. Mevcut programları birer oda kaydırırsanız yeni bir program ekleyebilirsiniz ve hesaplama için gereken tablo boyutu aynı kalır
      Daha genel olarak çoğu insanın sonsuzun, aleflerin ve transfinit matematiğin nasıl işlediğine dair sezgisi zayıftır. Günlük hayatla ilgisi de düşüktür; matematiğin, kategori teorisinin ve küme teorisinin belirimsel özellikleriyle derinden iç içedir. Sonsuzun herhangi bir sonlu sayıdan büyük olmasının yanı sıra bazı sonsuzların başka sonsuzlardan da daha büyük olabileceği, ilkokul düzeyindeki “sonsuz” kavramında kalan bir sezgiyle hemen görülebilecek bir şey değildir
      Daha ilginç soru, algoritmayı hesaplanabilir kılan herhangi bir n < ∞ olup olmadığıdır; bunun yanıtı elbette hayırdır ve Turing Ödülü de uçar gider
    • Bu, gerçek dünyadaki tüm bilgisayarların da yalnızca sonlu sayıda duruma sahip olması ve bu yüzden Turing makinesinden çok sonlu durum makinesine yakın olması durumuna benzer
    • Belirli tek bir s için K(s)yi hesaplayan basit bir algoritma olduğu da söylenebilir; dolayısıyla bu tür girdilerin sonlu bir kümesi için de mümkündür
      Olası tüm Turing makinelerini kısa uzunluktan başlayarak sıralayıp syi çıktılayan birini aramak yeterlidir. Daha kısa makinelerin hepsini denediyseniz ve hiçbiri syi çıktılamadıysa, syi çıktılayan en kısa makineyi bulmuşsunuz demektir; dolayısıyla onun uzunluğu K(s) olur. Aynı uzunlukta ya da daha uzun başka bir makine de syi çıktılayabilir, ama K(s) en küçük uzunluğa ilişkin değer olduğu için değişmez
    • P/Poly’nin P’ye göre sahip olabileceği ek güç akla geliyor. Devrenin kendisinin basit bir Turing makinesi tarafından çıktılanması gereken devre karmaşıklığı hiyerarşisi için genel bir ad vardı sanki, ama şu an aklıma gelmiyor

  • Deneyimime göre burada insanların sezgilerine klasik bilgisayar biliminden çok yapılandırmacı matematik daha iyi uyuyor
    Örneğin P=NP sorusunun yanıtını çıktılayan bir programın var olduğuna dair yapılandırmacı bir kanıt hâlâ yok
    Kendi makalemde de hesaplanabilir Julia kümeleriyle ilgili olarak bu sorunu ele aldım. Mark Braverman tüm ikinci dereceden Julia kümelerinin hesaplanabilir olduğunu kanıtladı, ama kendisi de bu kanıtın tekdüze biçimde hesaplanabilir olmadığını açıklıyor. Bunun yerine, istenen Julia kümesinin parametresini alıp çeşitli kümeleri istenen çözünürlükte çizmeye çalışan 5 makine kuruyor; her Julia kümesi için bunlardan biri doğru resmi çiziyor
    Yapılandırmacı matematikte kompakt kümenin yapılandırmacı kavramı, hesaplanabilir Julia kümeleri için gereken anlamdaki hesaplanabilir küme kavramıyla kabaca örtüşür. Ancak tüm ikinci dereceden Julia kümelerinin kompakt olduğu yapılandırmacı olarak kanıtlanamaz; olası parametrelerin karmaşık düzlemini çeşitli bölgelere ayırıp her bölge içinde ilgili Julia kümelerinin kompakt olduğunu kanıtlamak gerekir
    Klasik matematikte bu bölgelerin birleşimi tüm karmaşık düzlemdir; ama yapılandırmacılıkta bu sonuç geçerli değildir. Benzer biçimde klasik matematikte pozitif reel sayılar ile pozitif olmayan reel sayıların birleşimi tüm reel sayı doğrusudur, ancak yapılandırmacılıkta bu da geçerli değildir
    Yapılandırmacı yaklaşım, hesaplamayı gerçekten gerçekleştirmek için hangi ek bilginin gerektiğini tam olarak söyler. Yani verilen parametrenin karmaşık düzlemin hangi bölgesine ait olduğunu ortaya koymanız gerekir; ancak o zaman istenen görüntüyü elde etmek için 5 makineden hangisini çalıştıracağınızı bilirsiniz. Bu, çok daha tatmin edici bir yanıt gibi geliyor

    • Aaronson’ın verdiği P=?NP durumunda da yanıt “P=NP” gibi klasik bir yanıt değil, gerçek bir NP→P fonksiyonu olmalıdır
      İnsanlar içgüdüsel olarak dallanma ifadesinin hangi tarafında olduklarını bilmeleri gerektiğini bilirler; sadece klasik mantıkta eğitildikleri için bu gerçeği unutmuş değillerdir
    • “Her Julia kümesi için 5 makineden biri onu doğru çizer” noktası ilginç. Bunun özünde doğru kümeyi hesaplama olasılığının en az 1/5 olduğuna dair bir kanıta karşılık gelip gelmediğini merak ediyorum
      “5’inden hangisi doğru?” sorusu için henüz bulunmamış bir kanıt olduğunu mu düşündüğünü, yoksa ZFC içinde olduğu gibi karar verilemez olduğunu mu düşündüğünü de merak ediyorum

  • Bunun, durma probleminin karar verilemezliğini anlamayı zorlaştıran unsurlardan biri olduğunu düşünüyorum.
    “Bazı makinelerin durup durmayacağını belirlemenin herhangi bir makine için fazla karmaşık olduğu makineler vardır” demek istiyorsunuz; ama önemsiz return true ve return false programlarından biri, hangi makineyi ve girdiyi verirseniz verin her zaman doğru yanıtı verir.
    “O programlar Turing makineleri hakkında hiçbir şey bilmiyor, o yüzden dışlanmalı” diye itiraz etmek isteyebilirsiniz; ama karar verilebilirlik bundan ibaret değil. “Bu iki programdan hangisinin doğru olduğunu bulmak karar verilemezdir” diye de düşünebilirsiniz; fakat bunun da doğru ya da yanlış olarak belirlenmiş bir yanıtı vardır. Sorun ancak makine/girdi birleşimlerinden oluşan sonsuz kümeye genişletildiğinde karar verilemez hâle gelebilir.

    • Nesnelerin ailelerinde ortaya çıkan başka sorunlar da yeni başlayanlar için benzer şekilde anlaşılması zor olabilir.
      Örneğin keyfi bir sonlu boyutlu vektör uzayı, dual uzayı ve çift dual uzayıyla çeşitli şekillerde izomorfiktir; ancak ikincisi için tüm bu uzaylar boyunca tutarlı “doğal” bir izomorfizm seçilebilirken, ilki için bu yapılamaz.
      “Neden doğal olarak izomorfik değil? Baz uzunluğu aynı! Baza bağlı olup olmaması neden önemli? Diğer kanıtlar baz seçerken neden bu kabul edilebilir oluyor?” gibi kafa karışıklıkları doğar.

  • İfadeyle ilgili sorunun modal mantık gerektirmesi olduğunu düşünüyorum.
    “Tanrı varsa f:{0,1}*→{0,1} fonksiyonunu sabit 1 fonksiyonu olarak; Tanrı yoksa sabit 0 fonksiyonu olarak tanımlayalım. f hesaplanabilir mi? İpucu: Yanıt dini inanca bağlı değildir.”
    Doğru soru, f’nin hesaplanabilir olup olmayacağı, yani tüm x’ler için f(x)=M(x) koşulunu sağlayan bir Turing makinesi M’nin var olup olmadığıdır.
    Yanıt evettir. Çünkü hangi dünyada olursak olalım önemsiz bir Turing makinesi M=1_M ya da M=0_M vardır. Buna karşılık özgün ifade olan “f hesaplanabilir mi?” modal açıdan yanlış sorulmuş bir sorudur; Sleeping Beauty ya da Red Envelope paradoksları gibi, dilbilgisel olarak hatalı bir soruya daha yakındır.
    Başka bir açıdan bakınca, Tanrı’ya ya da fiilen doğru olabilecek bir olguya bağlılık, sonradan doldurulan ama kullanılmadan önce belirlenen bir derleyici direktifi ya da pragma gibidir. Doğru sorulduğunda mesele, fonksiyon ve hesaplanabilirliğin kesin tanımlarını açmaktan ibarettir; ikisi de Sipser’da açıkça tanımlanmıştır.

    • Benim tepkim de benzerdi ve Aaronson’ın yazısının yorumlarına bunu yazmıştım. Bu soru, Tanrı’nın var olup olmamasına göre sabit 1 fonksiyonunu ya da sabit 0 fonksiyonunu çağırabilen bir f fonksiyonuyla ilgili değil.
      Mesele, f etiketinin gösterdiği şeyin Tanrı varsa sabit 1 fonksiyonu, Tanrı yoksa sabit 0 fonksiyonu olması; biz sadece Tanrı’nın var olup olmadığını bilene kadar hangisi olduğunu bilmiyoruz. İki sabit fonksiyonun hesaplanabilirliği apaçık olduğundan, gerçekte bu bir hesaplanabilirlik sorunu değil, daha çok bir etiket sorunu.
    • Sleeping Beauty ya da Red Envelope paradokslarının burayla pek ilgisi yok gibi görünüyor. Bu paradokslar, saf matematiksel olasılık kavramlarını fiili gerçekliğe uygulama sürecinin bazen basit olmadığını göstermekten ibaret.
      Olasılık kuramının gerçekliğe uygulandığında işe yaraması olgusunun kendisi oldukça gizemlidir ve çeşitli bilimsel ve felsefi araştırmaların konusu olmuştur; bunu düşününce şaşırtıcı değildir.
      Önerdiğiniz “would f be” türü çözüm de pek çözüm sağlamıyor gibi. “Tanrı” sorusunun amacı, okuyucuyu belirli P-NP probleminden uzaklaştırıp sabit fonksiyonlar söz konusu olduğunda hesaplanabilirlik kavramının işe yaramadığını anlamasını sağlamaktır. Bu önerinin yararlı olması için özgün P-NP sorusuna da uygulanabilmesi gerekir; ama iyi tanımlanmış bir matematik sorusuna modal yaklaşımın nasıl girdiğini henüz göremiyorum.
    • Bu cümle biraz daha uzun yazılırsa ayrıştırma hatası azalacak gibi.
      “Tanrı varsa f:{0,1}→{0,1} fonksiyonunu sabit 1 fonksiyonu olarak tanımlayalım; Tanrı yoksa f:{0,1}→{0,1} fonksiyonunu sabit 0 fonksiyonu olarak tanımlayalım.”
    • “Tanrı” yerine hangi yüklemi koyarsanız koyun, içerdiği sonuç kesin konuşmak gerekirse klasik birinci mertebe mantıkta doğrudur ve muhtemelen birçok başka mantık sisteminde de doğrudur. Pragma benzetmesi yerinde.
      Böyle bir yüklemin kişinin Tanrı kavramına uyup uymadığı ayrı, matematik dışı bir meseledir.
      İnsanların klasik mantıkta yanlış bir önermenin her şeyi ima ettiğini öğrendiklerinde şaşırmasına benziyor. Matematikte katı biçimsel kurallar vardır ve “ima eder” ya da “eğer” gibi kelimelerin gündelik anlamlarına dair önyargıları bir kenara bırakmak önemlidir.
    • Zamana bağlı sürüm çok daha ilginç.
      G:t∈ℝ⁺->{0,1} fonksiyonunu, t zamanında Tanrı varsa 1, yoksa 0 olacak şekilde tanımlamak gibi.
      Elbette G’yi eylemsiz olmayan bir referans sisteminde analiz etmek daha da ilginçleşir.

  • Sipser, çoğu insanın hesaplama ile ampirik araştırma arasındaki farkı pek bilmemesinden yararlanıyor.
    “Tanrı var mı?” muhtemelen yanıtlanamayan bir soru olabilir; ama mesele bu değil. Bu yanıtı bulmak baştan beri hesaplamanın alanı değildir. Hesaplama yalnızca girdileri çıktılara eşleyen bir prosedürdür ve bu durumda Tanrı’nın var olup olmadığı girdilerden biridir.
    Girdi değerini fiilen bilemediğimiz için kafa karıştırıcıdır; ama program yine de vardır ve önemsiz bir programdır. Başka bir ikili ampirik soruyla da değiştirilebilir.
    Örneğin f:{0,1}* -> {0,1} fonksiyonu “Paris’te en az bir seyyar tuvalet varsa 1, yoksa 0” olsun. Bu hesaplanabilirdir ve doğru olan girdiyle fiilen çalıştırılması da mümkündür. Tanrı hakkındaki fonksiyon da hesaplanabilirdir; ancak yalnızca tahmin edilen girdiyle çalıştırılabilir. Çıktının içinde yaşadığımız evrenle anlamlı biçimde örtüştüğü garanti edilemese de hâlâ hesaplanabilir bir fonksiyondur.
    Daha basit olarak yalnızca f:{0,1}* -> {0,1} düşünülebilir. “Tanrı vardır” ve “Tanrı yoktur” ifadelerinin her biri olası bit dizileridir. Bunlardan biri girdi olarak alındığında 0, diğeri alındığında 1 çıktısı veren bir program var olabilir mi diye sorarsanız, elbette olabilir. Girdinin ampirik olarak doğru olup olmaması önemli değildir.

    • Aslında sorudaki fonksiyonlar girdiyi hiç kullanmıyor. Bunları boş kümeden {0, 1} kümesine giden fonksiyonlar olarak tanımlamak daha bile uygun olabilir.
      Sorudaki f bir fonksiyon değil, bir etikettir. Tanrı varsa f’nin gönderimi her zaman 1 çıktısı veren f1’dir; Tanrı yoksa her zaman 0 çıktısı veren f0’dır. Bu yüzden gerçekte bu bir hesaplanabilirlik sorunu değil, etiket sorunudur.

  • Matematikçiler ve bilgisayar bilimciler, konuşmayı kolaylaştırmak için ayrıntıları atlayan kısaltılmış ifadeler kullandıkları için bu tür şeyler hep olur
    “Her iki tarafı dx ile çarpalım” demekten farklı değil. “Gezgin satıcı problemi NP-zor mudur?” sorusu tek bir belirli örneği değil, bir problem ailesini anlatır. Belirli bir grafiği sabitlerseniz ortada N kalmaz; dolayısıyla elbette NP-zor değildir
    Bunu biliyorsanız söylemeye bile değmeyecek kadar açıktır, ama terimlerin anlamını bilmeyen biri için tamamen erişilmezdir
    Benim de geçmişte başka bir alanda benzer türde bir yanlış anlamam olmuştu. DNA’yı kod gibi görüyor, doğrudan ya da DNA’yı değiştirerek bir alt katman üzerinden mesaj alıp veren şeylerin o kodu çalıştırdığına inanıyordum. Genel olarak tamamen işe yaramaz bir model değildi, ama o modele ne zaman kapılmamak gerektiğini bilmem gerekiyordu
    Matematiksel arka planı olan bir biyolog için DNA’yı doğrudan Turing makinesi yürütme modeli olarak görmek bariz biçimde yanlıştı; benim içinse öyle değildi. Sonuçta mesele, temel bilginin yabancılığından kaynaklanıyor

  • Karar verilebilirlik, hesaplanabilirlik, varlık, hatta meyve gibi sözcüklerin bile akademik bağlamda ve gündelik bağlamda anlamları farklıdır. Gündelik anlamların sezgisini akademik bağlama taşıyınca bu tür “aptalca sorular” ortaya çıkar
    Wikipedia’da geçen bazı çok büyük sayılar akademik anlamda “vardır” ve “hesaplanabilir”dir, ama basamakları bizim evrenimize sığamaz

  • Dikkatli okumazsanız ifade kafa karıştırır
    “Tanrı varsa f:{0,1}*→{0,1} fonksiyonunu sabit 1 fonksiyonu, Tanrı yoksa sabit 0 fonksiyonu olarak tanımlayalım. f hesaplanabilir mi?” ifadesinde alternatifler fonksiyonun bir parçası değildir
    f fonksiyonu “Tanrı vardır” değerine göre dallanmıyor; dallanma meta-dilin içinde. f=0 mı f=1 mi bilmiyoruz, ama her iki durumda da olası iki fonksiyonun ikisi de hesaplanabilir olduğu için f de hesaplanabilirdir
    Daha da ötesi, f gerçekten bu dallanmayı içeriyor ve fonksiyonun tanım kümesi 0 (Tanrı yok) ile 1 (Tanrı var) olsa bile, tanım kümesindeki her değer için sonucu hesaplayabilmek anlamında yine hesaplanabilir bir fonksiyondur
    Karışıklığın özü, değeri bilinmiyor sayılan serbest bir değişkeni f’nin içindeki dallanma koşuluna itmekte yatıyor

  • “Tanrı varsa n=3, Tanrı yoksa n=5 olsun. n asal mıdır?” örneğine itiraz etmeye hazırım
    Burada n’nin 3 ya da 5 olduğunu ileri sürmek için üçüncü halin imkânsızlığı ilkesi kullanılıyor; oysa “Tanrı vardır” önermesi için bu ilkenin geçerli olduğuna dair bir gerekçe yok

    • Klasik mantıkta üçüncü halin imkânsızlığı ilkesi geçerlidir
      Bu durumda bu ilkenin gerekçelendirilip gerekçelendirilmediğini sorgulayacaksanız, neden yalnızca bunu sorun ettiğinizi de gerekçelendirmeniz gerekir. Neden patlama ilkesini de bırakıp paraconsistent logic içinde çalışmıyoruz? Kolmogorov da bu aksiyomda ciddi bir sorun olduğunu düşünmüş, başta bunun yapıcı mantıkla bağdaşmadığını sanmıştı
      Ayrıca bu önermenin tam biçimlendirmesine bağlı olarak üçüncü halin imkânsızlığı ilkesi zorunlu olmayabilir
    • Bu arada ders kitabı sürümünde sorunun açık bir ikili problem olduğunu varsaymanız gerektiği söyleniyor (Sipser 2. baskı, s. 162). Bunu yakalamanız epey keskin bir gözlem
    • “n asal mıdır?” sorusu da Tanrı varsa Tanrı’nın iradesine bağlıdır
      Tanrı zorunlu olarak fizik yasalarına ya da temel mantıksal zorunluluklara bağlı olmayabilir. Böyle bir Tanrı kavramı belirli bir teolojik akıl yürütme çizgisinden gelir; genel durum bu değildir
      İsterse Tanrı 6’yı tek sayı yapabilir. Tüm matematiği, mantıksal tutarlılığı ve bütün evreni değiştirebilir; ya da yalnızca 77’nin çift, diğer tüm sayıların tek olduğu bir dünya yaratıp tüm matematikçilerin bu düzeni tamamen tutarlı ve her zaman doğruymuş gibi görmesini sağlayabilir
      Bu yüzden yanıtın bir ölçüde dini inanca bağlı olduğu söylenebilir

  • Teorik bilgisayar bilimi ve karmaşıklık teorisi, CS lisans öğrencileri ya da komşu sektörlerde çalışanlar için parçacık fiziğinin sıradan insanlar nezdindeki yerine benziyor
    Sıradan insanların dolaşıklık sözcüğünü duymuş olması gibi biz de NP-zor sözünü duymuşuz; matematiksel çıkarımları doğrudan takip etmek yerine bunları berbat popüler benzetmeler ve hayallerle ikame ediyoruz

    • Yine de herkesin “hesaplanabilir” sözcüğünü yalnızca çok katı bir tanımla kullanması gerektiğini düşünmek için bir sebep yok. Gündelik tanım olan “bilgisayarın yapabildiği şey” de anlamlıdır
      Yazar, uzun bir eğitimden dolayı kendine çok katı bir hesaplanabilirlik tanımı seçmiş, sonra o sözcüğün belirli bir tanımı hakkında bütün bir yazı yazıp, aynı sözcüğü başka bir tanımla kullanan dünyadaki insanları aptalca sorular sormakla suçlamış olabilir
      İş yerinde akademisyenlerle ya da genel kitleyle konuşurken bu gerçekten çok sık yaşanıyor. Ortak terimleri belirlemek zor; kendi terminolojinize göre çizgiyi çekip başkalarından buna uymasını istemek yorucu