Sonsuzluğun Tuhaf Matematiği ile Bilgisayar Bilimi Arasında Yeni Bir Köprü

• Sonsuz kümelerin yapısını inceleyen teknik bir alan olan betimleyici küme kuramının algoritmik bir dille yeniden yorumlanabileceği ortaya kondu
• Matematikçi Anton Bernshteyn, sonsuz grafik problemlerinin bilgisayar ağlarındaki iletişim problemleri olarak yeniden yazılabildiğini kanıtladı
• Bu bağlantı, ölçülebilirlik (measurability) ile dağıtık algoritmaların verimliliği arasında bir karşılık ilişkisi olduğunu gösteriyor
• Araştırmacılar bu köprü sayesinde iki alandaki teorem ve problemleri karşılıklı dönüştürerek yeni sonuçlar elde ediyor
• Sonsuzluk ile hesaplama arasındaki sınırı yeniden tanımlayan bu keşif, matematik ile bilgisayar bilimi arasındaki işbirliği olanaklarını genişletiyor

---

Giriş: Küme kuramı ve sonsuzluk dünyası

• Modern matematiğin temeli küme kuramına dayanır ve matematikçilerin çoğu problemlerini bu varsayım üzerinden ele alır
• Ancak betimleyici küme kuramcıları (descriptive set theorists), sonsuz kümelerin doğasını araştırmayı sürdüren küçük bir araştırmacı grubudur
• 2023'te Anton Bernshteyn, betimleyici küme kuramı ile bilgisayar bilimi arasında derin bir bağlantı keşfetti
  • Belirli sonsuz küme problemlerinin bilgisayar ağlarındaki iletişim problemlerine dönüştürülebileceğini gösterdi
• Bu sonuç, mantık ile algoritmaları, sonsuz ile sonluyu birleştiren bir köprü olarak değerlendiriliyor

Betimleyici küme kuramının arka planı

• Küme kuramının kökeni, farklı sonsuzluk büyüklüklerini kanıtlayan Georg Cantor'un çalışmalarına dayanır
• Kümelerin büyüklüğünü ifade eden kavramlar arasında kardinalite (cardinality) ve ölçü (measure) bulunur
  • Örnek: 0~1 aralığındaki reel sayılar kümesi ile 0~10 aralığındaki reel sayılar kümesi aynı kardinaliteye sahiptir, ancak ölçüleri sırasıyla 1 ve 10'dur
• Betimleyici küme kuramı, ölçülebilir kümeler ile ölçülemez kümeleri ayırır ve bunları karmaşıklık hiyerarşileri içinde sınıflandırır
• Bu hiyerarşi, başka matematik alanlarında da (ör. olasılık kuramı, dinamik sistemler, grup kuramı) uygun araçların seçilmesi için bir ölçüt olur

Sonsuz grafikler ve boyama problemi

• Bernshteyn, sonsuz grafikleri inceleyerek her grafiğin düğüm ve kenarlarını sonsuz bağlı yapılar olarak modelliyor
• Örnek: Bir çember üzerindeki noktaları sabit aralıklarla bağlarsanız, aralık rasyonel olduğunda kapalı bir halka, irrasyonel olduğunda ise sonsuz bağlı bir yapı oluşur
• Grafiğin düğümlerini iki renkle boyarken, seçim aksiyomu (axiom of choice) kullanılırsa bu mümkün olur ama sonuç ölçülemez bir küme olur
• Buna karşılık sürekli bir boyama yöntemi kullanılırsa üç renk gerekir, ancak ölçülebilir bir küme elde edilir
• Bu fark, küme kuramsal karmaşıklık hiyerarşisindeki konumu belirleyen temel bir unsur olarak işlev görür

Dağıtık algoritmalarla karşılaşma

• 2019'da Bernshteyn, dağıtık algoritmalar (distributed algorithms) üzerine bir bilgisayar bilimi konuşması dinledikten sonra benzerliği fark etti
  • Örnek: Wi-Fi yönlendiricilerinin birbirine parazit yapmaması için frekansları (renkleri) farklı seçmesi problemi
• Her düğüm, rengini belirlemek için yalnızca komşu düğümlerle iletişim kuran bir yerel algoritma (local algorithm) kullanır
• İki renk verimsiz kalırken, üç renge izin verildiğinde problem verimli biçimde çözülebilir
• Bernshteyn, bu renk sayısı eşiğinin (threshold) betimleyici küme kuramındaki ölçülebilir boyama probleminin eşiğiyle aynı olduğunu fark etti

İki dünyanın eşdeğerliğinin kanıtı

• Bernshteyn, verimli yerel algoritmalar ↔ ölçülebilir boyama yöntemleri arasındaki eşdeğerliği matematiksel olarak kanıtladı
• Sonlu grafiklerde her düğüme benzersiz bir numara verilebilir, ancak sayılamaz sonsuz grafiklerde bu mümkün değildir
• Bunun üzerine, komşu düğümler arasında çakışmayan bir etiketleme yöntemi tasarlayarak algoritmaların sonsuz grafiklere de genişletilmesini sağladı
• Sonuç olarak, “her yerel algoritma, betimleyici küme kuramındaki ölçülebilir bir boyama yöntemine karşılık gelir” ifadesi kanıtlandı
• Bu, hesaplanabilirlik ile tanımlanabilirlik (definability) arasındaki derin matematiksel bağı gösteriyor

Araştırmanın genişlemesi ve uygulamalar

• Václav Rozhoň ve diğerleri bu bağlantıyı kullanarak ağaç (tree) grafiklerinin boyama problemini çözdü ve dinamik sistemler araştırmaları için araçlar ortaya çıkardı
• Ters yönde ise, küme kuramı yöntemleri kullanılarak problem zorluğunu tahmin etme çalışmalarının da geliştirildiği görülüyor
• Bu köprü, yalnızca problem çözme aracı olmanın ötesinde, küme kuramının sınıflandırma sistemini yeniden kurmaya da katkı sağlıyor
• Betimleyici küme kuramcıları artık bilgisayar biliminin sistematik sınıflandırma yaklaşımını referans alarak sınıflandırılmamış problemleri düzenleyebiliyor
• Bernshteyn, bu araştırmanın sonsuzluk kavramının pratik matematiğin bir parçası olarak görülmesine katkı sunmasını umuyor

[GN⁺]

Hacker News görüşleri

• Bu tür sonuçların dağıtık bilişim gibi gerçek alanlarda uygulanıp uygulanamayacağını merak ediyorum. Yoksa sadece saf matematiksel bir ilgi olarak mı kalıyor, emin değilim

  • Bu hiç de aptalca bir soru değil. Teknik içgörüler, dağıtık algoritmalar ya da hesaplama karmaşıklığı kuramında yeni imkansızlık teoremlerine yol açabilir. Mesh networking gibi olası uygulamalar da ilginç

• “Tüm modern matematik küme kuramı üzerine kuruludur” sözü fazla kesin. Lean ve Rocq gibi modern matematik araçları, biçimselleştirilmiş matematik(formalized mathematics) temelinde gelişiyor ve bu da tip kuramı(type theory) üzerine kurulu

  • Matematikçi değilim ama ZFC'nin hâlâ geçerli bir temel sistem olduğunu düşünüyorum. Bağımlı tipler(dependent types) teorem ispatlarını yönetmek için yararlı, ama daha fazla teorem ispatlamanızı sağlamıyor. Lawrence Paulson'ın Isabelle/HOL'u tip tabanlı değil ama matematiğin büyük kısmını ispatlayabiliyor
  • Ama pratikte matematikçiler biçimselleştirilmiş matematiği neredeyse hiç kullanmıyor. Bilseler bile zahmetli olduğu için onu temel dil olarak kullanmıyorlar
  • Matematiğin dili ile o dil hakkında ispat yaptığınız biçimsel dili karıştırmamak gerekir. İlki neredeyse tamamen kümeleri, ikincisi ise zorunlu olarak tipleri kullanır
  • Daha doğru söylemek gerekirse, matematiğin temelleri krizi küme kuramının biçimselleştirilmesi ile büyük ölçüde sona erdi

• “cons’es all the way down” ifadesi, özyinelemeli yapıyı hicveden şakalı bir anlatım

• “Sonunda sonsuzu hesaplayabiliyoruz” sözü beni duygulandırdı

  • Gelecek ay Bay Area'da The Dillinger Escape Plan'ın Calculating Infinity turnesi varmış. Etkinlik bağlantısı. Matematik, hacking ve mathcore hayranlarının burada kesişebileceğini düşündüğüm için paylaşıyorum
  • “Sonsuzu hesaplamak” sözüne “Ve ötesini de!” diye karşılık vererek şakayı sürdürüyor
  • Haskell'de let x = x in x tek satırıyla sayılabilir sonsuzluk(countable infinity) ifade edilebildiği söyleniyor
  • “Chuck Norris 1'den sonsuza kadar iki kez saydı” mem'iyle espri ekleniyor
  • “Bu gerçekten çok uzun sürdü /s” diyerek alaycı bir ifade ekleniyor

• “Bilgisayar bilimi yalnızca sonlu şeylerle ilgilenir” iddiasına katılmıyorum. Aslında bilgisayar bilimi sonsuzlukla derinden ilgilenir

  • Quanta'nın bunu bu şekilde ele alması olağan bir durum. Popüler bilim anlatımı gereği insan odaklı hikâyelere yoğunlaşıyor ve ayrıntıları atlama eğiliminde oluyor
  • Yine de bilgisayar bilimi sayılamaz sonsuzlukla(uncountable infinity) pek ilgilenmez. Ölçü kuramı(measure theory) daha çok o alanla uğraşır
  • Ben de başta “CS sonsuzluğu yaklaşıklar” diye düşünmüştüm ama aslında kilit sözcük yaklaştırma(approximation). Biz her zaman sonlu sınırlar içinde çalışıyoruz. Evren sonsuz olsa bile gözlemleyebildiğimiz aralık ışık hızı ile sınırlı
  • “Bilgisayar bilimi mantık kullanmaz” gibi cümleler fazla özensiz. Boolean mantığı bunun doğrudan kanıtı

• Uzun süre matematik çalıştım ve sonunda sonsuzluğun(infinity) var olmadığına inanmaya başladım. Matematik, sonsuzluk olmadan daha iyi olabilir diye düşünüyorum

  • Ben de yalnızca mühendislik düzeyinde matematik öğrendim ama sonsuzluğun bir sayı değil, bir süreç(process) olduğunu düşünüyorum. {1, 2, 3, ...} içindeki “...” sonu olmayan bir genişleme sürecini ifade eder. Sonsuzuncu asal sayı diye bir şey yoktur; sadece her zaman daha büyük bir asalın var olduğunu söyleyen bir üretim kuralı vardır
  • Ama sonsuzluğu kaldırırsanız matematik korkunç derecede karmaşık hâle gelir. Doğal sayıları sonsuza dek uzatmıyorsanız hesap yapmak çok kullanışsız olur
  • Matematik, var olup olmamaktan çok kavramsal faydayla ilgilenir. Çemberler de gerçekte var değildir ama kullanışlıdır. Sonsuzluk olmasa, sonunda bunu “x çok ama çok büyük sayılara giderken alınan limit” gibi bir biçimde yeniden icat etmek zorunda kalırdık
  • “8'de durmak yeterli” şakasıyla sonsuzluğun gereksizliği hicvediliyor
  • Sonsuzluk, hiç bitmeyen bir sürecin adından ibarettir. Bazı süreçler daha hızlı büyüdüğü için daha büyük sonsuzluklar vardır. Ben şahsen Riemann küre modelindeki sonsuzluk kavramını seviyorum

• node_modules'ün dosya sistemimde sonsuzluğun matematiğini birbirine bağladığı şakasıyla, bağımlılık patlaması hicvediliyor

• “Tüm modern matematik küme kuramı üzerine kuruludur” cümlesine itiraz edilerek, Tip Kuramı(Type Theory) diye bir şeyin de olduğu belirtiliyor

  • Type Theory, ZFC'den daha güçlü bir aksiyom sistemi. İlgili açıklama için MathOverflow yanıtına bakılabilir
  • Ancak ZF ya da ZFC kadar etkili olmuş bir tip kuramı aksiyom kümesi henüz yok
  • Teknik olarak betimsel küme kuramı(descriptive set theory), temelsel küme kuramından ayrıdır. Tip ve uzay kavramlarıyla kolayca yeniden kurulabilir ve bu çoğu zaman daha avantajlıdır. Matematiksel sonsuzluğu hesaplamalı bir bakışla yeniden yorumlamak yeni bir girişim değil
  • “Soyut nesne kümelerini organize etme disiplini” açıklaması küme kuramını fazla basitleştiriyor. Yine de matematiğin büyük kısmının hâlâ küme aksiyomlarından tanımlandığı doğru