Beşinci Busy Beaver ile araştırmacılar hesaplamanın sınırlarına yaklaşıyor

• Giriş

  • 40 yıl önce Almanya'nın Dortmund kentinde bilgisayar bilimcileri, beşinci Busy Beaver'ı bulmak için bir araya gelip yarıştı
  • Busy Beaver, çalışma süresi son derece uzun olabilen basit bir bilgisayar programıdır
  • Bu programlar, matematiğin ünlü çözülmemiş problemleriyle ilişkilidir ve bilgisayar biliminin eski bir probleminden doğmuştur
  • İki yıl önce yüksek lisans öğrencisi Tristan Stérin, Busy Beaver Challenge'ı başlattı ve dünyanın dört bir yanından 20'den fazla katılımcı katkı sundu
  • Bugün ekip, BB(5) değerini 47,176,870 olarak doğruladı

• Duracak mı, durmayacak mı

  • Busy Beaver programları, Turing machine adı verilen kuramsal bir bilgisayar için yazılmış komutlardan oluşur
  • Turing machine, sonsuz bir bant üzerinde 0 ve 1 okuyup yazarak hesaplama yapar
  • Bir Turing machine'in durup durmayacağını ya da sonsuza kadar çalışıp çalışmayacağını öngörme problemine durma problemi denir
  • Durma probleminin genel bir çözümü yoktur; bu da Busy Beaver avını daha da cazip kılar

• Beaver'ın ortaya çıkışı

  • Matematikçi Tibor Radó, 1962'de Busy Beaver oyununu icat etti
  • Her kural grubunda en uzun süre çalışan Turing machine'e Busy Beaver denir
  • BB(n), n kurala sahip Busy Beaver makinesinin durmadan önce attığı adım sayısını ifade eder

• Brady'nin beaver sürüsü

  • Allen Brady, 1960'larda Busy Beaver avı tekniklerini geliştirdi ve 1974'te dördüncü Busy Beaver'ın değerini belirledi
  • BB(4), 107 adımdan sonra duran makine olarak doğrulandı

• Beşinci beaver

  • 1984'teki Dortmund yarışmasında beşinci Busy Beaver'ı bulmaya yönelik ilk büyük av başladı
  • 1989'da Heiner Marxen, 47,176,870 adımdan sonra duran bir makine keşfetti
  • 2003'te Georgi Georgiev, çözülmemiş 43 Turing machine bırakarak BB(5) avını durdurdu

• Tüm avcılar çağrılıyor

  • Tristan Stérin, 2022'de Busy Beaver Challenge'ı başlattı ve dünyanın dört bir yanından katkıcılar katıldı
  • Shawn Ligocki, 2022'de ekibe katıldı ve önemli katkılar yaptı
  • Justin Blanchard, ekibin en güçlü tekniklerinden biri olan kapalı bant dili yöntemini geliştirdi

• Canavara yaklaşırken

  • Skelet #1 ve #17 özellikle zor makinelerdi; ekip bunları çözmek için çeşitli fikirleri birleştirdi
  • Mayıs 2023'te mxdys adlı anonim bir katkıcı, Coq ispatını tamamladı

• Beaver'ların dolaştığı yer

  • Ekip resmî bir akademik makale hazırlıyor; bazıları ise bir sonraki beaver'ı bulmaya çalışıyor
  • BB(6), Collatz sanısına benzer bir problem nedeniyle çözülmesi zor görünüyor

GN⁺ görüşü

• Bu yazı, bilgisayar biliminin sınırlarını araştıran ilgi çekici bir örnek sunuyor
• Busy Beaver Challenge, işbirlikçi araştırmanın önemini gösteriyor
• BB(5)'in çözülmesi, bilgisayar bilimi ve matematik topluluğu için büyük anlam taşıyor
• Benzer özelliklere sahip projeler arasında Collatz sanısı araştırmaları bulunuyor
• Yeni bir teknoloji ya da açık kaynak benimsenirken işbirliği ve yeniden üretilebilirlik önemlidir

[GN⁺]

Hacker News görüşleri

• Scott Aaronson’ın blog gönderisine dair görüşler paylaşıldı

  • Bununla ilgili önceki bir başlık bağlantısı verildi

• Busy Beaver probleminin çeşitli varyasyonları var

  • Lambda hesabını kullanan bir varyasyon bulunuyor
  • Kolmogorov karmaşıklığı ile ifade edilen bir varyasyon da bulunuyor

• Bir mühendisin Busy Beaver problemini araştırmak için işinden ayrıldığına dair bir hikâye paylaşıldı

  • Bu mühendisin mxdys olup olmadığı merak ediliyor

• Coq ispatına değiniliyor

  • Bunun sıfırdan düzenlenmiş bir ispat değil, ilk kez düzenlenmiş bir ispat olabileceği öne sürülüyor

• Tibor Radó’nun orijinal Busy Beaver makalesinin okunmasının kolay ve eğlenceli olduğu görüşü paylaşılıyor

  • Makalenin modern bir sürümüne bağlantı veriliyor

• 5 durumlu 2 renkli Turing makinesi programlarının durma problemi çözülmüş durumda

  • Bunun 2 durumlu 4 renkli duruma uygulanıp uygulanamayacağı soruluyor

• İnsanların durma problemini sezgisel olarak çözebileceği yönündeki yanlış düşünceye değiniliyor

• Kişisel bir projede Cutting Stock problemini çözmek için program yazma deneyimi paylaşılıyor

  • Brady’nin programına benzer optimizasyon yöntemleri kullanılmış

• 5 durumlu Turing makinesi programlarının durup durmadığını kanıtlayabilmiş olmanın biraz şans eseri olduğu görüşü paylaşılıyor

• Scott Aaronson’ın blog gönderisine göre 16,679,880,978,201 adet 5 durumlu Turing makinesi var

  • Bunların yüzde kaçının durduğu merak ediliyor

• Busy Beaver fonksiyonunun değerleri paylaşılıyor

  • BB(5)’in 47,176,870 olduğu kanıtlandı
  • BB(6) en az 10^10^...^10 (15 katlı üs kulesi)