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

 (scottaaronson.blog)
2 puan yazan GN⁺ 2025-06-29 | 1 yorum | WhatsApp'ta paylaş
  • BB(6) için bilinen alt sınır yeniden ciddi biçimde yükseldi; 6 durumlu Turing makinesinin en uzun durma süresinin, gözlemlenebilir gerçekliğin ölçeğini çok aşan bir sayı olduğu doğrulandı
  • BB(6), 0’larla dolu bir banttan başlayan 6 durumlu, 2 sembollü Turing makinesinin durmadan önce çalıştırabileceği en yüksek adım sayısını ifade eder
  • Pavel Kropitz’in 2022’deki iyileştirmesinin ardından mxdys, alt sınırı yeniden 10’un 10 milyon kez tekrarlı üssü alınmış halinden daha büyük bir seviyeye çıkardı
  • Son sonuç, BB(6)’nın en az 2 pentated to 5 olduğunu gösteriyor; tekrarlı üslemeden bir seviye daha yüksek bir işlem de devreye giriyor
  • BB(5) 47.176.870 olarak belirlenmişti, ancak BB(6) ezici ölçüde büyüyerek BB(n)’in ZFC aksiyom sisteminden bağımsız hale geldiği noktanın n=7, 8, 9 olabileceği tahminlerine yol açıyor

BB(6)’nın alt sınırı yeniden büyüdü

  • 2022’den önce BB(6) için yalnızca yaklaşık BB(6) > 10^36.534 biliniyordu; Pavel Kropitz bunu 10’un 15 kez tekrarlı üssü alınmış halinden daha büyük bir seviyeye iyileştirdi
  • Tetrasyon (tetration) tekrarlı üs alma anlamına gelir
    • Örneğin 10’un 15 kez üst üste yığıldığı sayı, 10’un 10’un 10’un … biçiminin 15 kez sürdüğü sayıdır
  • BBchallenge organizatörü Tristan Sterin, ekip üyesi mxdys’in BB(6) alt sınırını yeniden yükselttiğini duyurdu
    • İlk iyileştirme: BB(6) > 10’un 10 milyon kez tekrarlı üssü alınmış hali
    • Bu sonuç için bir Coq doğruluk kanıtı bulunuyor
  • mxdys’in sonraki iyileştirmesi, BB(6)’nın en az 2 tetrated to 2 tetrated to 2 tetrated to 9 olduğunu gösterdi
    • Özellikle BB(6) en az 2 pentated to 5
    • Pentasyon (pentation), tekrarlı tetrasyondur; tetrasyonun üslemenin tekrarından bir seviye daha yüksek bir işlem olması gibi, bundan da bir seviye yukarıdadır

BB(5) ile BB(6) arasındaki uçurum

  • BB(6), 6. Busy Beaver sayısıdır
    • 6 durumlu Turing makinelerini kapsar
    • Alfabe {0,1}
    • Girdi bandı başlangıçta tamamen 0’dır
    • Durmadan önce mümkün olan en yüksek çalışma adımı sayısını ifade eder
  • Uluslararası BBchallenge ekibi geçen yıl BB(5)’i 47.176.870 olarak belirledi
  • BB(5)’ten BB(6)’ya geçerken Busy Beaver fonksiyonu on milyonlar mertebesinden, gözlemlenebilir gerçekliğin kapsamını aşan bir büyüklüğe sıçrıyor

Büyüklük hissinin neredeyse işlemediği bir sayı

  • BB(6) > 10’un 10 milyon kez tekrarlı üssü alınmış hali olduğu aşamada bile sezgisel bir açıklama neredeyse imkânsızdı
  • Örneğin bu kadar kum tanesi olsaydı, gözlemlenebilir evrenin kopyalarının yaklaşık aynı sayıda olanını doldurabileceği benzetmesi yapılıyor
  • Bu benzetme, söz konusu sayının 10^100 gibi kozmik ölçekli sayılardan bile ezici biçimde büyük olduğu için, bölme yapılsa bile geriye neredeyse asıl sayıyla aynı ölçekte bir büyüklük kaldığını gösteriyor

ZFC bağımsızlığı tahmini düşebilir

  • BB(6)’nın bu kadar büyümesi, Busy Beaver fonksiyonuna dair tüm düşüncelerin değiştiği anlamına gelmiyor
  • BB(6)’nın 10^36.534 gibi görece küçük bir seviyede değil, tekrarlı işlemler alanında olma olasılığı zaten açıktı
  • Gerçek alt sınırın bu ölçekte doğrulanmasıyla, BB(n) değerinin ZFC küme kuramı aksiyom sisteminden bağımsız hale geldiği noktaya ilişkin tahminler düşebilir
    • Önceden n=20 veya 30 civarı düşünülebilirdi
    • Şimdiyse n=7, 8, 9 olabileceği düşünülüyor
  • ZFC bağımsızlığına dair şu anda bilinen sonuç, BB(n)’in n=643’te ZFC’den bağımsız hale geldiği düzeyde

Ayrı güncelleme: STOC 2025

  • STOC 2025’in düzenlendiği Prag’da çeşitli araştırmacılarla buluşuldu ve yeni bilgiler edinildi
  • STOC genel oturum konuşmasının başlığı The Status of Quantum Speedups
  • İlgilenen okurlar bu konuşmanın PowerPoint slaytlarına göz atabilir

İlgili okumalar

1 yorum

 
GN⁺ 2025-06-29
Hacker News yorumları

  • bbchallenge Discord sunucusunda, en yeni BB(6) şampiyonunun ulaştığı 2^^2^^2^^9dan çok daha büyük olan Graham's Number'ı aşmak için kaç Turing makinesi durumunun gerekeceği üzerine hararetli tahminler yapılıyor.
    Functional busy beaver'a https://oeis.org/A333479 bakınca, Graham düzeyinde davranışın şaşırtıcı derecede erken ortaya çıkabileceği görülüyor. 49 bitlik bir lambda terimi yeterli.
    Bu boyutun altındaki kapalı lambda terimi sayısı yalnızca 77.519.927.606 https://oeis.org/A114852; benzersiz 6 durumlu Turing makinelerinin sayısı ise 4^12*23836540=399910780272640 https://oeis.org/A107668.
    Sadece 6 durumla pentasyona ulaşıldığına göre, artık 7 durumun Graham's Number'ı aşabileceğini düşünen epey kişi var. Yine de ben bunun hâlâ oldukça şaşırtıcı olacağını düşünüyorum. Birkaç gün önce onlardan biriyle, önümüzdeki 10 yıl içinde BB(7)>Graham's kanıtının çıkıp çıkmayacağı üzerine büyük bir bahse girdim; herkesin ne düşündüğünü merak ediyorum.

    • Uzmanmış gibi yapamam ama BB(7) muhtemelen Graham's Number'dan büyüktür.
      BB'nin hesaplanabilir herhangi bir diziden daha hızlı büyümesi gerekir. Bunun BB(7) için somut olarak ne anlama geldiği nihayetinde biraz el kol hareketiyle anlatmaya benziyor; ama operatör gücü merdivenini çok hızlı tırmanması gerektiği hissini veriyor. Sonuçta tanımladığımız herhangi bir hesaplanabilir operatörden daha hızlı büyümeli; örneğin up-arrow^n ya da hesaplanabilir bir f fonksiyonu için up-arrow^f(n) de buna dahil.
      Sezgisel olarak, 47 milliondan 2^^2^^2^^9a giden büyüme, gerekli operatör gücü açısından 2^^2^^2^^9dan Graham's Number'a giden büyümeden niteliksel olarak daha büyük görünüyor. Graham's Number g_64 ve burada g kabaca up_arrow^nnin bir seviye üstünde; bu yüzden muhtemelen BB(7)>Graham's Number olabilir.

  • BB(748) gibi bir sayının, üstelik hesaplanamayan bir sayının “ZFC'den bağımsız” olabilmesi insanın başını döndürüyor. Bir tür kategori hatası gibi geliyor.

    • BB(748)'i ZFC'den bağımsız yapan şey değerin kendisi değil; 748 durumlu makinelerden biri olan TM_ZFC_INCin ZFC içindeki bir çelişkiyi, yani FALSE kanıtını arayıp onu bulduğunda ancak duracak şekilde tasarlanmış olmasıdır.
      Dolayısıyla BB(748)=N şeklindeki bir kanıt, TM_ZF_INCin N adım içinde durduğunu ya da asla durmayacağını göstermelidir. ZFC'nin tutarlı olduğu varsayılırsa, Gödel'in ünlü sonucu nedeniyle ikisi de imkânsızdır.
    • Hesaplanamayan şey BB(n)'dir. Yani keyfi bir n için BB(n) değerini çıktılayan bir algoritma yoktur.
      BB(748) hesaplanabilirdir. Tanım gereği 748 duruma sahip bir Turing makinesinin yazdığı 1'lerin sayısıdır ve o makine BB(748)i hesaplar.
      Sayının kendisi kelimenin tam anlamıyla hayal edilemeyecek kadar büyük bir tam sayıdan ibarettir. ZFC bağımsızlığı, bu sayının aradığımız sayı olduğunu kanıtlamaya çalıştığımızda devreye girer. Bunun için 748 durumlu Turing makinesinin özelliklerini yakalayabilen, ZFC'den daha güçlü bir teori gerekir.
    • Asıl şaşırtıcı olan, ZFC aksiyomları gibi bir peçeteye rahatça sığacak kadar kısa bir metnin aritmetik hakikati ya da insan etkinliğiyle çoğunlukla ilişkili fiziksel gerçekliğin yönlerini yakalamaya “yeterli” olacağını düşünmüş olmamız.
      6 durumlu bir Turing makinesinin davranışının birkaç satırlık metinle öngörülemez olabilmesi hiç şaşırtıcı değil.
      Gödel ilk eksiklik teoremini yayımlar yayımlamaz tüm matematik camiasının daha fazla aksiyom bulmak için son sürat koştuğunu sanırdım. Oysa neredeyse bir yüzyıl boyunca Gödel'in çalışması, ana akım bir programdan ziyade temeller alanının dar bir köşesinde kalan tuhaf bir olgu gibi ele alındı. Feferman, Friedman ve benzerlerini biliyorum; ama bu alandaki araştırma, matematiğin diğer çoğu konusuna kıyasla çok daha az.
    • Sayının kendisi ZFC'den bağımsız değildir. Tüm tam sayılar ZFC'de ifade edilebilir. ZFC'den bağımsız olan şey BB(748)'i hesaplama sürecidir.
    • Tek tek sayıların kendisi hesaplanamaz değildir. Herhangi bir sayı ile ZFC içindeki bir kanıt çifti olarak, o sayının BB(748)in değeri olduğunu ispatlayan bir şey yoktur.
      Bu nedenle ZFC'nin BB(748) değerini çıktılayacağını kanıtlayabildiği bir program da yoktur. Ama diğer tüm sayılar gibi, BB(748)i çıktılayan bir programın kendisi vardır.

  • BB(14)'ün Graham's Number'dan büyük olduğu biliniyor; ancak bu sonuçlara bakınca BB(7) de muhtemelen Graham's Number'dan büyük gibi görünüyor.
    Sezgisel olarak, pentasyondan Graham's Number'a gitmek için gereken teknik, 47,176,870den 2 5e gitmek için gereken teknikten daha basit hissettiriyor.

  • sol üst simgenin tetrasyonu, yani yinelenen üs almayı ifade ettiğini açıklayan notu görünce başta yazım hatası sandım. Tetrasyonla ilk kez karşılaşıyorum.

  • “10,000,000sub10 tane kum tanesi olduğunu hayal edin. O zaman gözlemlenebilir evrenden yaklaşık 10,000,000sub10 tanesini bu kumla doldurabilirsiniz” kısmını anlamadım
    Gerçekten gözlemlenebilir evrenin hacmini ortalama bir kum tanesinin hacmine bölüp çıkan değeri yuvarlayarak yok mu ediyorlar? Bu, genelde karşılaştırmalarda kullanılan evrenin toplam kütlesinden bile çok daha fazla basamak farkı demek

    • Evet. Bu orana bölmek, bu gösterimde “komşu” sayıların çok daha büyük değişimler yaratması nedeniyle pratikte neredeyse hiç etki etmiyor
      10↑↑10,000,000 / (evren başına kum tanesi sayısı), örneğin 10↑↑9,999,999dan bile ezici ölçüde büyüktür
      Böyle sayıları kullanan bir sistemde (çok büyük sayı)/(yalnızca evrensel ölçekte bir sayı) için bunu aynen yazmak dışında pek daha iyi bir ifade yoktur; çok büyük sayı tarafındaki gösterimde sonuçta neredeyse (çok büyük sayı)ya yuvarlanır
    • Tetrasyonda artık basamak sayısının ölçeğiyle değil, basamak sayısı ölçeğinin basamak sayısı ölçeğiyle uğraşırsınız
    • Bu tür karşılaştırmaların daha yaygın bir örneği: anlamlı basamaklar açısından 1 milyardan 1 milyonu çıkarsanız da 1 milyar kalır
    • Doğru. Bu sayı 10^100000dan ya da kaç kum tanesi sığdığı gibi niceliklerden o kadar büyük ki, o kadarına bölseniz bile pratikte değişmez. En azından 9,999,999sub10a yaklaşacak kadar aşağı inmez
    • Evet. Bu sadece sıradan bir sayı kadar basamak farkı. Sadece 10,000,000^10,000,000 bile bunu önemsiz kılacak kadar büyükken, hele üssün kendisini dokuz kez daha kuvvete yükselttikten sonra durum daha da böyledir

  • Scott Aaronson’ın How Much Math Is Knowable? [Harward CMSA]: https://www.youtube.com/watch?v=VplMHWSZf5c
    Birkaç ay önce HN’de de paylaşılmıştı: https://news.ycombinator.com/item?id=43776477

  • Yalnızca 5 durumlu Turing makineleriyle kanıtları numaralandırabilen en zengin mantık ne olabilir?

    • Bu soru neyi numaralandırma sayacağınıza bağlı değişir; ama bununla ilişkili bir soru şu: “Tüm 5 durumlu Turing makinelerinin durup durmayacağını kanıtlayamayan en zengin mantık nedir?” Yani bazı 5 durumlu Turing makinelerinin durup durmayacağının bağımsız olduğu en zengin mantığın ne olduğu soruluyor
      Bu sürüm üzerine biraz düşündüm, ama birinci dereceden mantık konusundaki uzmanlığım yetersiz olduğu için fazla ilerleyemedim. Bildiğim kadarıyla Skelet #17 https://bbchallenge.org/1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA, durmadığını matematiksel olarak kanıtlaması en zor makinelerden biri https://arxiv.org/abs/2407.02426; dolayısıyla Skelet #17’nin durmadığını kanıtlayabilen bir teori, muhtemelen diğer 5 durumlu makineleri de karara bağlayabilir
    • Sonlu bir ikili dizgenin mantıksal kanıtların numaralandırılması olarak nasıl yorumlanacağına tamamen bağlı

  • “BB(6), altıncı Busy Beaver sayısıdır; yani {0,1} alfabesine sahip 6 durumlu bir Turing makinesi başlangıçta tamamen 0’lardan oluşan bir bantta çalıştırıldığında, durmadan önce atabileceği azami adım sayısıdır” açıklamasını görünce, uzman olmayan biri olarak bana tersine fazla iyi anladım gibi geldi
    Bu kesinlikle onlarca yıldır bu araştırmayı yapan insanlara yönelik hardcore bir blog. Belirli bir okur kitlesi için çekinmeden yoğun ve teknik terimlerle dolu yazılmış bir metne tesadüfen denk gelmek epey hoş

    • Lisans düzeyinde bilgisayar bilimi eğitimi almış biri, Busy Beaver problemini ilk kez görse bile kabaca neler olup bittiğini sezebilecek kadar açıklama var
      Niş bir teknik terim olduğu doğru, ama buna yalnızca onlarca yılını vermiş kişilerin erişebileceğini düşünmek kendini hafife almak olur
    • Bu tanım, standart lisans düzeyi bilgisayar bilimi teorisi konusudur. Ancak yazılım mühendisliğinde standart olmayabilir

  • Bu kadar büyük bir sayıyı insan görselleştiremez. Sayıları ifade etmenin tek yolu basitçe saymak değildir
    Örneğin tek bir kum tanesinin bile sonsuz sayıda olası durumu olduğu düşünülebilir. Reel sayılar sonsuz olduğundan, tek bir kum tanesinin BB(6)yı ifade edebileceği de söylenebilir. Kombinasyonlar üstel olarak büyüyebildiği için bu tür bir yöntem ifade için yararlı olabilir

    • Bir noktadan sonra büyük sayılar “büyük nicelik” olmaktan çok biçimsel sistemlerin tutarlılık gücüne yaklaşır
      Yani mesele, bir sistemin yakalanana kadar ne kadar iyi çelişkisizmiş gibi davranabildiğidir. BB(3) üzerinden tutarlılık taklidi yapan çelişkili bir sistem, BB(6) üzerinden tutarlılık taklidi yapan bir sisteme göre çok daha hızlı “yakalanır”. Burada tutarlılık taklidi yapmak, belirli bir n için BB(n) adımdan daha uzun çalışan tüm programların durmadığını iddia etmek anlamına gelir
    • Evren en yakın Planck birimine yuvarlanıyorsa, tek bir kum tanesinin sahip olabileceği durum sayısı birdenbire o kadar da fazla olmaz
      Sonsuz hassasiyeti işin içine çekip konuyu kolay ele alınırmış gibi göstermek bana göre biraz el çabukluğu. Ölçeği anlatırken tam sayıları kullanmak daha iyi
    • Bu örnek kafa karıştırıcı. Kum tanesi sayısıyla gözlemlenebilir evren sayısı aynıysa, bu evren başına bir kum tanesi demek değil mi?

  • Gözlemlenebilir evrenin BB(6)’nın tam değerini yazacak kadar büyük olup olmadığını merak ediyorum

    • Gözlemlenebilir evreni kapalı bir sistem olarak görürsek Bekenstein sınırını uygulamayı deneyebiliriz
      R ≈ 46.5 billion light-years, yani gözlemlenebilir evrenin yarıçapını kullanıyoruz; E ≈ gözlemlenebilir evrenin toplam kütle-enerji içeriğini kullanıyoruz
      Kütle-enerji genelde normal maddeyi, karanlık maddeyi ve karanlık enerjiyi kapsar. Mevcut tahminlere göre gözlemlenebilir evren yaklaşık 10^53 kg kütle-enerji eşdeğerine sahip
      Bunu S ≤ 2πER/ℏc içine koyunca azami bilgi miktarı kabaca 10^120 bits mertebesinde çıkıyor
      S ≤ 2πER/ℏc
      S ≤ (2 × 3.141593 × 3.036e+71 × 4.399e+26)/(1.055e-34 × 299792458)
      S ≤ 2.654135e+124
      S ≤ 10^120
      Dolayısıyla imkânsız
    • Kesinlikle yeterli değil. Evrende saklanabilecek bilgi miktarı kabaca 10^120 bit civarında. Bir trilyon basamak kadar yanılıyor olsam bile sonuç değişmez
    • Yazıdaki başlangıç sayısı bile ¹⁵10. Bu, 10^(¹⁴10) anlamına geliyor; dolayısıyla basamak sayısı ¹⁴10 adet. Bu yüzden yazılamaz
    • Muhtemelen tam ifadenin tüm parçalarının aynı anda var olduğu bir durumdan söz ediliyor. Aynı anda var olmaları gerekmiyorsa, evrenin süresi sonsuz olursa “yazıp bitirmek” mümkün olabilir. Isıl ölümün burada nasıl devreye girdiğini bilmiyorum, o yüzden “mümkün olabilir” diyorum
      Ancak göreli uzay-zamanda “aynı anda” ifadesi iyi tanımlı değildir. Kardeş yorumlar, kozmik mikrodalga arka plan ışımasının ima ettiği referans çerçevesinde kesinlikle haklı. Yine de bazı referans çerçevelerinde, ifadeyi “aynı anda” mümkün kılacak şekilde uzay-zamanı dilimlemenin bir yolu olabilir mi diye merak ediyorum