Teorik bilgisayar bilimindeki zombi yanılgısı

Teorik bilgisayar bilimindeki zombi yanılgısı

Giriş

• Michael Sipser'in "Introduction to the Theory of Computation" ders kitabında kusursuz bir ödev var
• Ödev: "f:{0,1}*→{0,1} fonksiyonu, Tanrı'nın var olup olmamasına göre 1 veya 0 döndürüyorsa, f hesaplanabilir mi?"
• Cevap: "Evet, f hesaplanabilirdir" (çünkü sabit fonksiyonlar hesaplanabilirdir)

Hesaplanabilirlik kavramı

• Hesaplanabilirlik, fonksiyonlara veya sonsuz dizilere uygulanır
• Tekil evet/hayır sorularına ya da tekil tamsayılara uygulanmaz
• Program yazmanın zorluğu, hesaplanabilirlikle ilgisizdir

P vs NP problemi

• P vs NP problemi tekil bir evet/hayır sorusudur
• NP-zorluk, fonksiyonlara veya dillere uygulanır
• P vs NP problemi hesaplanamaz veya NP-zor olamaz

Busy Beaver fonksiyonu

• Busy Beaver fonksiyonu hesaplanamazdır
• BB(6) gibi tekil tamsayılar hesaplanabilirdir
• Hesaplanamaz olan, BB fonksiyonunun tamamıdır

Teorik bilgisayar bilimindeki zombi yanılgısı

• Sonsuz dizilere ve fonksiyonlara uygulanan kavramları tekil tamsayılara ve açık problemlere yanlış uygulamak
• Durma probleminin hesaplanamazlığı ile Gödel eksiklik teoremini karıştırmak

Okura soru

• Bu zombi yanılgısının nasıl önlenebileceğine dair okura soru

GN⁺ Özeti

• Bu yazı, teorik bilgisayar biliminde sık ortaya çıkan yanlış anlamaları ele alıyor
• Hesaplanabilirlik, fonksiyonlara veya sonsuz dizilere uygulanır; tekil tamsayılara ya da evet/hayır sorularına değil
• P vs NP problemi tekil bir soru olduğundan, NP-zorluk kavramıyla ilgisizdir
• Busy Beaver fonksiyonu hesaplanamazdır, ancak tekil değerleri hesaplanabilirdir
• Bu yazı, teorik bilgisayar biliminin temel kavramlarını daha net anlamaya yardımcı olacaktır

[GN⁺]

Hacker News görüşleri

• Kolmogorov karmaşıklığını hesaplayan bir algoritmanın var olup olmadığı sonsuzlukla ilgilidir

  • Rastgele uzunluktaki dizelerin Kolmogorov karmaşıklığını hesaplayan bir algoritma yoktur
  • Ancak uzunluğu n'den küçük dizelerin Kolmogorov karmaşıklığını hesaplayan bir algoritma vardır
  • Bu, mümkün olan tüm dizeler için devasa bir arama tablosu oluşturularak yapılabilir
  • Sonlu problemler her zaman bir programla çözülebilir, ama sonsuz problemler için bu geçerli değildir

• Yapısalcı matematiğin insanların sezgileriyle daha iyi örtüştüğü görüşü

  • P=NP problemine yönelik bir programın var olduğuna dair henüz bir kanıt yok
  • Mark Braverman, tüm (ikinci dereceden) Julia kümelerinin hesaplanabilir olduğunu kanıtladı, ancak bu tekdüze biçimde hesaplanabilir değildir
  • Yapısalcı matematikte karmaşık düzlem birden çok bölgeye ayrılır ve her bölgedeki Julia kümesinin kompakt olduğu kanıtlanır

• Durma probleminin kararsızlığını anlamanın zor olmasının nedeni

  • return true ve return false programlarından biri her zaman doğru cevabı verir
  • Karar verilebilirlik ancak sonsuz makine/girdi kombinasyonlarına genişletildiğinde karar verilemez hale gelir

• Modal mantık gerektiren problem ifadesi

  • "f hesaplanabilir mi?" sorusu modal açıdan yanlış bir sorudur
  • "f hesaplanabilir olabilir mi?" sorusu daha doğrudur
  • Bu, derleyici yönergelerine veya pragma'lara benzer

• f fonksiyonunun kafa karıştırıcı ifadesi

  • f fonksiyonu, "God exists" değerine göre dallanmaz
  • f ister 0 ister 1 olsun hesaplanabilirdir
  • Karışıklık, serbest değişkenlerin dallanma koşulunun içine itilmesinden kaynaklanır

• Karar verilebilirlik, hesaplanabilirlik ve varlık gibi kavramların anlam farkı

  • Akademik bağlamla gündelik bağlamda anlamları farklıdır
  • Büyük sayılar akademik olarak vardır ve hesaplanabilirdir, ama pratikte evrene sığmazlar

• "God exists" ile ilgili soruların sorunu

  • "God exists" ifadesinin doğru mu yanlış mı olduğu net değildir
  • Bu, doğal dille matematiğin karıştırılmasından doğan bir sorundur

• Teorik bilgisayar bilimi ve karmaşıklık teorisinin CS lisans öğrencilerine zor gelmesinin nedeni

  • NP-hard gibi terimler, popüler benzetmeler ve hayal gücüyle ikame edilir

• Blogdaki metin vurgulama yöntemine yönelik şikayet

  • Seçilen metnin arka plan rengi değişmediği için sezgisel değil

• "God exists" ifadesini başka bir matematiksel önermeyle değiştirme önerisi

  • "God exists" ifadesi doğru ya da yanlış olacak şekilde açıkça tanımlanmalıdır