BusyBeaver(6) gerçekten çok büyük

• Busy Beaver 6. sayısı (BB(6)) için alt sınır, yakın zamanda yeni araştırmalarla büyük ölçüde artırıldı
• Daha önce BB(6) > 10↑36,534 olarak biliniyordu, ancak 2022'de BB(6) > 10↑1510 olarak yukarı yönlü güncellendi
• Son olarak BBchallenge'da BB(6) > 10↑10,000,00010 olarak yeniden yükseltildi, ardından 2 ↑↑ (2 ↑↑ (2 ↑↑ 9)) seviyesine kadar güncellendi
• BB(6)'nın büyüklüğü hayal gücünü aşıyor; bu sayı tüm evreni sayısız kez doldurabilecek düzeyde
• Bu gelişmeler, matematiksel mantık ve hesaplama kuramının sınırlarını ve potansiyelini yeniden düşünmek için bir fırsat sunuyor

---

BB(6) ile ilgili son araştırma sonuçlarına genel bakış

• Son birkaç yılda dünyanın ve araştırma ortamının zorlu hissedildiği bir dönem sürdü
• Ancak Busy Beaver araştırmalarındaki bu ilerleme, araştırmaya duyulan saf tutkuyu yeniden hatırlatmaya vesile oldu
• 2022'de Pavel Kropitz, BB(6) > 10↑1510 olduğunu kanıtladı
  • BB(6), 6 duruma sahip bir Turing makinesinin tamamen sıfırlardan oluşan bir bant üzerinde durmadan önce en fazla kaç adım çalışabileceğini ifade eder
  • Buradaki ^1510, 10'un kendi üzerine 15 kez yinelenen üs alma işlemiyle oluşturulan değerini (tetrasyon) ifade eder
• Daha önceki çalışmalarda BB(5)'in 47,176,870 olduğu ortaya konmuştu (BBchallenge ekibi); bu, değerin gözlemlenebilir gerçekliğin kapsamını aşan bölgeye sıçramaya başladığı nokta olarak görülebilir

Son alt sınır güncelleme süreci

• BBchallenge'dan "mxdys", BB(6) > 10↑10,000,00010 olduğunu kanıtladı
  • Bu kanıt, Coq diliyle yazılmış resmi bir ispat temeline dayanıyor
• Ardından alt sınır tekrar BB(6) > 2 ↑↑ (2 ↑↑ (2 ↑↑ 9)) olarak güncellendi
  • ↑↑, tetrasyonu (üs almanın tekrarı) ifade eder; burada 2'nin 2 ile tetrasyonu ve ardından ortaya çıkan sonuçla tekrar tetrasyonun 9 kez uygulanması söz konusudur
  • Bu büyüklük, mevcut sezgisel kavrayışların tümünü aşan bir alana karşılık geliyor
• Not olarak, pentasyon tetrasyonun tekrarı anlamına gelir; bu tür işlemler çarpma, üs alma ve tetrasyonun ötesine geçen işlemlerdir

Dev sayıların büyüklüğünü anlamak

• Gazetecinin isteği üzerine 10↑10,000,00010 sayısının büyüklüğünü açıklamak gerekiyordu
• Bu sayı, 10↑10,000,00010 adet evreni kumla doldurmaya yetecek kadar çok kum tanesine karşılık gelir
• Bu da BB(6) değerinin fiili gözlemlenebilir dünyayı çok çok geride bıraktığını anlatır

BB algoritmasının özsel sınırları üzerine düşünceler

• BB(6) değerinin olağanüstü büyüklüğü, Busy Beaver fonksiyonunun gerçek potansiyelini gösteriyor
• BB(n) değerinin küme kuramı (ZFC) aksiyom sistemi içinde bağımsız hale geldiği noktanın n=20~30 civarında olduğu tahmin ediliyordu; ancak muhtemelen n=7~9 için bile zaten bağımsız olabilir
  • Şu anda n=643 için bağımsız olduğu resmi olarak biliniyor

Ek: son etkinlik ve konuşma haberleri

• Yazar yakın zamanda Prag'da düzenlenen STOC'2025 etkinliğine katılarak çeşitli araştırmacılarla bir araya geldi ve yeni bilgiler edindi
• Kendi kuantum hızlandırma durum değerlendirmesi hakkındaki açılış konuşması slaytlarını da paylaştı
• Bu konuyla ilgili daha ayrıntılı izlenimlerini daha sonra paylaşmayı planlıyor

[GN⁺]

Hacker News görüşleri

• bbchallenge Discord sunucusunda, insanların Graham's Number'ı aşmak için kaç Turing makinesi durumunun gerekebileceğini tahmin edişini paylaşmışlar. Son BB(6) kazananının ulaştığı 2^^2^^2^^9 zaten inanılmaz büyük bir sayı, ama Graham sayısı türü büyümenin düşünüldüğünden daha erken ortaya çıkabilmesine şaşırıyor. Yalnızca 49 bitlik lambda terimlerinin bile yeterli olduğunu söyleyen functional busy beaver [1] kaynağından ve bu boyutta yalnızca 77519927606 kapalı lambda terimi bulunduğundan [2], buna karşılık tam 399910780272640 adet 6-durumlu Turing makinesi olduğundan [3] söz ediyor. Pentation'ın sadece 6 durumla gerçekleştirildiğinin görülmesiyle artık epey kişi 7 durumun Graham's Number'ı da aşabileceğine inanıyor; yine de kendisi bunu hâlâ şaşırtıcı buluyor. Birkaç gün önce, önümüzdeki 10 yıl içinde BB(7)'nin Graham's Number'ı aştığını gösteren bir ispat çıkıp çıkmayacağı üzerine büyük bir iddiaya girdiğini söyleyip başkalarının fikrini soruyor. (1, 2, 3 bağlantıları verilmiş)
  • Uzmanmış gibi davranmak istemediğini ama BB(7)'nin Graham's Number'dan büyük olacağını tahmin ettiğini söylüyor. BB'nin herhangi bir hesaplanabilir sayı dizisinden daha hızlı büyümesi gerektiğini, dolayısıyla gerçek BB(7)'nin ne kadar büyük olduğunu ancak kabaca sezebildiğini; ama sonuçta tüm hesaplanabilir işleçlerden (ör. up-arrow^n vb.) daha hızlı büyümesi gerektiğini belirtiyor. 47176870'den 2^^2^^2^^9'a giden büyümenin, 2^^2^^2^^9'dan Graham's Number'a gitmekten işleç gücü açısından çok daha dramatik bir sıçrama olduğu hissine sahip. Graham's Number'ın g_64 olduğunu ve bunun da up-arrow^n'den bir seviye üstte yorumlanabileceğini, bu yüzden BB(7)'nin Graham's Number'ı aşacağına dair sezgisini paylaşıyor.
• BB(748) gibi hesaplanamaz bir sayının ZFC'den (küme kuramı aksiyom sistemi) bağımsız olmasının çok ilginç olduğunu söylüyor. Bunun neredeyse bir kategori hatası gibi hissettirdiğini dürüstçe paylaşıyor.
  • BB(748)'in ZFC'den bağımsız olmasının nedeninin değerin kendisi değil, 748 durumdan biri olan TM_ZFC_INC'nin yalnızca ZFC içinde bir çelişki (yanlış bir ispat) bulunursa duracak şekilde tasarlanmış olması olduğunu açıklıyor. BB(748)=N olduğunu kanıtlamak için TM_ZFC_INC'nin N adım içinde durduğunu ya da sonsuza dek çalıştığını göstermek gerekir; fakat Gödel'in eksiklik teoremine göre, ZFC çelişkisizse bunların hiçbiri ZFC içinde ispatlanamaz.
  • Az sayıda metin satırının (yani ZFC aksiyomlarının kendisinin) insanlar için önemli aritmetik doğruları yeterince ifade edebiliyor olmasının asıl daha şaşırtıcı olduğunu düşünüyor. 6 durumlu bir Turing makinesinin davranışını bile kolayca öngöremediğimiz bir dünyada bunun doğal olduğunu söylüyor. Gödel'in eksiklik teoremi yayımlandıktan sonra matematik dünyasının daha fazla aksiyom arayışında çok daha aktif olması gerekirdi, ama bunun gerçekte yalnızca temel araştırmanın bazı bölümlerinde ele alınmış olmasından yakınıyor.
  • Süreklilik hipotezinin doğruluk değerinin (Platoncu bakışla 1 ya da 0) ZFC'den bağımsız olduğunun kanıtlanmış olması iyi bir örnek. Devasa bir sayı değil, yalnızca tek bir bit bile ZFC tarafından garanti edilemiyor.
  • BB(n)'nin hesaplanamaz olduğunu, ama BB(748)'in (tanım gereği) 748 durumlu bir Turing makinesinin yazdığı 1'lerin sayısı olduğu için hesaplanabilir bir sayı olduğunu açıkça ayırıyor. “Bağımsız” etiketinin asıl anlamının, bu sayının gerçekten istediğimiz değer olduğunu ZFC ile kanıtlamak için daha güçlü bir kurama ihtiyaç duyulması olduğunu açıklıyor.
  • Sayının kendisinin değil, BB(748)'i hesaplama sürecinin ZFC'den bağımsız olduğunu vurguluyor. (Her tam sayı ZFC içinde ifade edilebilir.)
• BB(14)'ün Graham's Number'dan büyük olduğu iyi bilinen bir gerçek; bu yeni çalışmadan sonra BB(7)'nin de Graham's Number'a en azından ulaşacağına dair sezgisini söylüyor. Sezgisel olarak, pentation'dan Graham's Number'a gitme fikrinin, 47,176,870'den 2 <pentate> 5'e gitmekten daha basit geldiğini belirtiyor.
  • Bunun iyi bir bilgi olduğunu, kendi yazısına harika bir yanıt olabileceğini söylüyor.
• Scott Aaronson'ın “How Much Math Is Knowable?” [Harward CMSA] YouTube konuşmasını https://www.youtube.com/watch?v=VplMHWSZf5c ve yakın tarihli HN tartışmasını https://news.ycombinator.com/item?id=43776477 paylaşmış.
• “Sol üst köşe üssü”nün tetration, yani tekrarlı üs alma olduğunu söylüyor. ¹⁵10 ifadesinin 10'un 10'un... 15 kez tekrarlanması anlamına geldiğini açıklıyor. Bunu ilk kez gördüğü için başta yazım hatası sanmış.
  • Tekrarlı işlemler teması sürerken bu kez de “pentation” ile ilk kez karşılaştığını söylüyor.
  • Tetration'ı daha önce gördüğünü, ama Knuth'un up-arrow gösteriminin [1] daha yaygın ve genelleştirme için daha uygun olduğunu tercih olarak belirtiyor (1).
• BB(6)'nin, başlangıçta tamamen 0'lardan oluşan bant üzerinde duran 6 durumlu 2 sembollü ({0,1}) Turing makinesinin durmadan önce atabileceği en fazla adım sayısı olduğu açıklamasının uzman olmayan biri için çok faydalı olduğunu söylüyor. Bu alanın onlarca yıllık araştırmacılara yönelik yoğunlukta ve uzmanlaşmış terimlerle dolu olduğunu hissettiğini, ama tesadüfen böyle derin bir yazıya denk gelmenin hoşuna gittiğini paylaşıyor.
  • Bilgisayar mühendisliği lisans öğrencisi düzeyindeki biri için, busy beaver problemini ilk kez görse bile genel fikri kavrayabilecek içerik olduğunu düşünüyor. Elbette özel terimler çok, ama bunun yalnızca onlarca yıllık deneyimi olanlara yönelik bir konu gibi görülmemesi gerektiğini teşvik edici biçimde ekliyor.
  • Bu tanımın yazılım mühendisliğinden çok bilgisayar bilimi kuramında standart olduğunu belirtiyor.
• “10,000,000 sub10” tane kum tanesinin gözlemlenebilir evreni 10,000,000 sub10 kat doldurmaya yettiği açıklamasının kafasını karıştırdığını söylüyor. Bunun genelde gözlemlenebilir evrenin kütlesiyle karşılaştırılarak anlatıldığını, bu biçimin ise zaten gerçek madde miktarını çok aştığını belirtiyor.
  • Buna doğru diye yanıt veriliyor. Kum tanesi/evren oranıyla bölünse bile bunun kendisinin de neredeyse aynı mertebede dev bir sayı olduğu, dolayısıyla bitişik sayıların (bu gösterimde) akıl almaz derecede farklı kaldığı söyleniyor. 10↑↑10,000,000 / (kum tanesi/evren) ifadesinin de yine 10↑↑9,999,999'dan çok daha büyük olduğu açıklanıyor. Bizim sistemimizde (çok büyük) / (kozmik ölçekte büyük) ifadesinin hâlâ sadece (çok büyük) olarak kaldığı benzetmesi yapılıyor.
  • Tetration'da artık yalnızca basamak sayısı değil, “basamak sayısının basamak sayısı” düzeyinde bir büyüme olduğuna ek yapılıyor.
  • Bu sayının yaklaşık 10^100000 kum tanesiyle bile kayda değer biçimde azalmayacağı, yani bölmenin özünde etkisiz kalacağı tekrar vurgulanıyor.
  • 10,000,000^10,000,000 bile yeterince anlamsız derecede büyük olduğundan, buna bir kat daha üs kuyruğu eklenince karşılaştırmanın anlamını yitirdiği örnek olarak veriliyor.
  • Daha yaygın bir örnek olarak, anlamlı basamaklar mantığında 1 milyar - 1 milyon = 1 milyar demenin çok da uçuk olmadığı söyleniyor.
• 5 durumlu Turing makineleriyle ispatları sıralanabilir mantık sistemleri arasında en “zengin” olanın hangisi olabileceğini merak ediyor.
  • “Sıralama”yı hangi ölçüte göre tanımladığına bağlı olarak yanıtın değişebileceği söyleniyor. Bununla bağlantılı şu soru da anlamlı bulunuyor: “5 durumlu Turing makinelerinin durup durmadığını tamamen ispatlayamayan en güçlü mantık sistemi hangisidir?” Skelet #17 [0]'nin durmadığını matematiksel olarak kanıtlamanın çok zor olduğu, bu yüzden bunu ispatlayabilen bir kuram varsa geri kalan 5 durumlu Turing makinelerinin de tümünü karara bağlayabileceği yönünde kişisel görüş paylaşılıyor (0, 1).
  • Sonlu ikili dizgelerin mantıksal ispat listeleri olarak nasıl yorumlanacağının önce netleştirilmesi gerektiği belirtiliyor.
• Gözlemlenebilir evrenin BB(6)'nin tam değerini yazmaya yetecek kadar büyük olup olmadığını soruyor.
  • Gözlemlenebilir evren kapalı bir sistem olarak alınırsa, Bekenstein sınırı uygulanarak bilgi depolama üst sınırının yaklaşık 10^120 bit olduğu hesaplanabiliyor. Toplam kütle-enerjinin güncel tahminle yaklaşık 10^53 kg olduğu ve formüle konduğunda yine yaklaşık 10^120 bit çıktığı söyleniyor. Dolayısıyla bunun imkânsız olduğu sayısal gerekçeyle açıklanıyor.
  • Evrende depolanabilecek bilgi miktarının yaklaşık 10^120 bit olduğu ve bu tahminde katrilyonlarca kez hata yapılsa bile sonucun değişmeyeceği kadar “apaçık yetersiz” olduğu vurgulanıyor.
  • Bunun tüm değerin aynı anda saklanmasını varsaydığı düşünülüyor. Eşzamanlılık şartı yoksa sonsuz zaman boyunca kayıt tutmanın teorik olarak mümkün olabileceği, ama evrenin ısıl ölümü gibi pratik sınırların dikkate alınması gerektiği söyleniyor. CMB referans çerçevesinde imkânsız olduğu, ama başka uzay-zaman kesitlerinin düşünülebileceği soruluyor.
  • Yazıdaki ilk sayının bile zaten ¹⁵10, yani 10^(¹⁴10) biçiminde olduğu; dolayısıyla basamak sayısının kendisinin bile ¹⁴10 olduğu düşünülürse bunun kesinlikle imkânsız olduğu belirtiliyor.
  • Kısaca bunun mümkün olmadığı yeniden söyleniyor.
• Hesaplama karmaşıklığı kuramındaki bu tür sonuçları her gördüğünde, “süper yapay zeka tanrıdır” türü popüler söylemlerin tamamen temelsiz olduğunu daha iyi anladığını söylüyor. Evrendeki tüm atomları süper bilgisayara dönüştürüp kara delik enerjisini bile kullansak, BB(6)'nin durma durumunu hesaplamanın sonsuza kadar imkânsız olacağını belirtiyor.
  • Böyle bir korkuluk argümanının zaten baştan beri ikna edici olmadığını söyleyen kısa bir yanıt geliyor.