BB(3, 4) > Ack(14) sonucu

 (sligocki.com)
1 puan yazan GN⁺ 2024-05-25 | 1 yorum | WhatsApp'ta paylaş
  • Yeni bir 3-state 4-symbol Busy Beaver şampiyonu TM bulundu ve durduğunda ((2 \uparrow^{15} 5) + 14) adet sıfır olmayan sembol bıraktığı hesaplandı
  • Bu sayı Knuth up-arrow gösterimiyle bile çok büyük olduğundan, (Ack(n)=n \uparrow^n n) olarak tanımlanan 14. Ackermann number’ı aşan (BB(3,4) > Ack(14)) alt sınırı olarak özetleniyor
  • TM’nin temel davranışı (B(k,n,m) \to B(k,0,g_{k-1}^n(m))) biçimine yakın şekilde sıkıştırılabiliyor, ancak bunu göstermek için çift tümevarım gerekiyor
  • Matthew House’un kapalı biçimli değerlendirme ifadesi (g_k^n(0)=\frac{2 \uparrow^k (n+2)}{2}-2) sayesinde nihai skor (\sigma=(2 \uparrow^{15}5)+14) tam olarak yazılabiliyor
  • Bu TM, Collatz tarzı kalan dallanması olmadan Ackermann düzeyi fonksiyonları simüle ediyor ve geliştirilmekte olan Inductive Proof Validator için de bir doğrulama örneği olarak kullanılıyor

Yeni Busy Beaver şampiyonunun ölçeği

  • Pavel Kropitz yeni bir 3-state 4-symbol Busy Beaver şampiyonu keşfetti
  • Bu TM “Ackermann düzeyi” fonksiyonları hesaplayabiliyor ve durduğunda bantta şu sayıda sıfır olmayan sembol bırakıyor
    • ((2 \uparrow^{15} 5) + 14)
  • Knuth up-arrow gösterimiyle bile çok büyük bir değer olduğundan, alt sınır şöyle özetleniyor
    • (BB(3,4) > Ack(14))
  • Burada (Ack(14)), (Ack(n)=n \uparrow^n n) olarak tanımlanan 14. Ackermann number’dır
  • Bilinen kapsam içinde, gerçek arama sırasında bulunan TM’ler arasında Ackermann düzeyi fonksiyon simüle edebilen ilk örnektir

TM tanımı ve nihai konfigürasyon

  • TM geçiş dizgesi şöyledir
    • 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC
  • Geçiş tablosu A, B, C durumları ve 0, 1, 2, 3 sembolleri için tanımlanmıştır
    • A: 1RB, 3LB, 1RZ, 2RA
    • B: 2LC, 3RB, 1LC, 2RA
    • C: 3RB, 1LB, 3LC, 2RC
  • Nihai konfigürasyon şöyledir
    • (0^\infty ;; 3^{2 g_{15}^{3}(0) + 1} ;; 2^{16} ;; 1 ;; \text{ Z> } ;; 0^\infty)
  • Bu konfigürasyonda skor (\sigma) tam olarak hesaplanır
    • (\sigma = 2 g_{15}^{3}(0) + 18 = (2 \uparrow^{15} 5) + 14)

Keşif ve doğrulama süreci

  • Pavel Kropitz bu TM’yi 25 Nisan 2024’te Discord’da paylaştı
  • O sırada kod, insan tarafından okunabilir bir skor alt sınırı belirleyemiyor ve sonucu Halt(SuperPowers(13)) olarak gösteriyordu
    • Bu, kanıt için 13 katmanlı tümevarım kuralı gerektiği anlamına geliyordu
  • Daha sonra yeni Inductive Proof Validator kullanılarak doğrulama başlatıldı
  • 20 Mayıs 2024’te doğrulama tamamlanınca (g_k^n(m))’nin kesin tanımı çıkarıldı ve bununla (\sigma > 2 \uparrow^{15} 3) alt sınırı elde edildi
  • Matthew House 22 Mayıs 2024’te şu basit kapalı biçimli değerlendirme ifadesini keşfetti
    • (g_k^n(0) = \frac{ 2 \uparrow^k (n+2) }{2} - 2)
  • Bu değerlendirme ifadesiyle (\sigma)’nın tam değeri ifade edilebilir hale geldi

Davranış analizi ve çift tümevarım kanıtı

  • Şu konfigürasyon tanımlanır
    • (B(k, n, m) = 0^\infty ;; 3^{2m+1} ;; 2^k ;; \text{ A> } ;; 1^n)
  • Başlangıç konfigürasyonu 241 adım sonra şu duruma ulaşır
    • (0^\infty ;; \text{A>} ;; 0^\infty \xrightarrow{241} B(16,3,0);;2;;0^\infty)
  • Temel kural şöyledir
    • (B(k,n,m) \to B(k,0,g_{k-1}^n(m))), burada (k \ge 1)
  • (g_k) şu özyineleme ile tanımlanır
    • (g_0(m)=m+1)
    • (g_{k+1}(m)=g_k^{2m+2}(0))
  • Tüm davranış neredeyse tek bir kurala sıkıştırılacak kadar basittir, ancak bu kuralın kendisi çift tümevarım ile kanıtlanmalıdır
  • Yardımcı önerme ve sonuçlar, B durumunun 3 ve 2^k bloklarını işleyerek 1’ler üretme sürecini ele alır
    • (3;;2^k;;\text{<B} \xrightarrow{2k+1} 2^k;;\text{<B};;1)
    • (3^m;;2^k;;\text{<B} \xrightarrow{(2k+1)m} 2^k;;\text{<B};;1^m)
  • Teorem 3, tüm (k \ge 1, n \ge 0, m \ge 0) için temel kuralın geçerli olduğunu gösterir
    • (k=1) temel durumu (n) üzerinde tümevarımla ele alınır
    • Tümevarım adımında (k) üzerindeki varsayım ve (n) üzerindeki tümevarım varsayımı birlikte kullanılır

Tam değerin hesaplanması

  • (g_k) için yalnızca Knuth up-arrow ve aritmetik kullanan görece basit bir kapalı biçimli değerlendirme vardır
  • Tüm (k \ge 0, m \ge 0) için şu geçerlidir
    • (2 g_{k+1}(m) + 4 = 2 \uparrow^k (2m+4))
    • burada (a \uparrow^0 b = ab) olarak tanımlanır
  • Bu sonuç (k) üzerinde tümevarımla kanıtlanır
    • Temel durumda (k=0), (g_1(m)=2m+2) olur
    • Tümevarım adımında ((2 \uparrow^k)^n)’in tekrarlı uygulanması kullanılır
  • Kapalı biçim, (2 \uparrow^k 2 = 4)’ün tüm (k)’lerde geçerli olması tesadüfüne dayanır
    • Parametre biraz değişip ((2 \uparrow^k)^{2m+2}5) biçimini alsaydı, kapalı biçimli bir ifade elde etmenin zor olacağı düşünülüyor
  • Sonuç olarak tüm (k \ge 0, n \ge 0) için şu geçerlidir
    • (2 g_k^n(0) + 4 = 2 \uparrow^k (n+2))
  • Nihai skor doğrudan şöyle türetilir
    • (\sigma = 2 g_{15}^{3}(0) + 18 = (2 \uparrow^{15} 5) + 14)

Başlangıç durumunu değiştiren permütasyon sonucu

  • Başlangıç durumu B veya C olarak değiştirilirse daha küçük ilgili sonuçlar elde edilir
    • (0^\infty ;; \text{B>} ;; 0^\infty \xrightarrow{86} B(7,3,0);;2;;0^\infty)
    • (0^\infty ;; \text{C>} ;; 0^\infty \xrightarrow{20} B(1,3,0);;2;;0^\infty)
  • Başlangıç durumu B olduğunda skor şöyledir
    • (\sigma_B = 2 g_6^3(0) + 9 = (2 \uparrow^6 5) + 5)
  • Başlangıç durumu C olduğunda 72 adımda durur ve skor şöyledir
    • (\sigma_C = 2 g_0^3(0) + 3 = (2 \uparrow^0 5) - 1 = 9)
  • B’den başlayan ilk permütasyon da bir başka üst sıralardaki BB(3,4) TM’dir
  • TNF’ye dönüştürüldüğünde şu geçiş dizgesi elde edilir
    • 1RB3RB1LC2LA_2LA2RB1LB3RA_3LA1RZ1LC2RA

Collatz tarzı kuralların olmadığı basitlik

  • Bu TM’nin ilginç yönlerinden biri, beklenenden basit olmasıdır
  • Değerin kalanına göre farklı davranan Collatz-like kural yoktur
  • Collatz-like TM’lerin hâkimiyetinin bitip bitmediğini söylemek için henüz çok erken
  • Ackermann düzeyi Collatz-like TM’lerin hâlâ mevcut olabileceği, ancak seçim yanlılığı nedeniyle hemen görünmeyebileceği yönünde bir tahmin var
  • Bu TM’nin ilk Ackermann düzeyi TM olarak keşfedilmesinin nedeni, Ackermann düzeyi fonksiyon üzerinde modular arithmetic uygulamadan da durma kanıtı verilebilecek kadar basit olması olabilir

Inductive Proof Validator

  • Bu TM, geliştirilmekte olan Inductive Proof Validator için uygun bir test örneğiydi
  • Projenin amacı, “tümevarım kanıtı” için standartlaştırılmış bir sertifika biçimi oluşturmaktır
  • Burada “tümevarım kanıtı”, ileri akıl yürütme ve kural tabanlı analizin genelini ifade eden kapsayıcı bir terim olarak kullanılır
  • Elinde bir “inductive decider” olan herkesin ilgili kuralları bu biçimde yazabilmesi ve validator’ın bu kanıtı denetleyebilmesi hedeflenir
  • Sistem hâlâ oldukça ham ve gerçek kullanım için hazır değil, ancak biraz manuel çalışmayla bu TM dahil olmak üzere çeşitli TM’lerin davranışını kanıtlamakta kullanıldı

İlgili okumalar

1 yorum

 
GN⁺ 2024-05-25
Hacker News yorumları

  • Çok uzun süre çalışan Turing makinesi programlarının derin biçimde karmaşık ya da spagetti kod olacağını düşünmek kolay, ancak bu yeni şampiyon neredeyse buna karşı bir örnek
    Yalnızca A, B, C olmak üzere üç durumu var; B denetimi A ve C’ye devrediyor, ama A ile C birbirini “bilmiyor” ve yalnızca B’ye geri dönüyor
    Gerçek spagetti kod olsaydı her durum diğer tüm durumlara geçebilirdi; bu ise bir tür modüler yapı
    Ayrıca boş hücreyi asla yazdırmıyor ve her komut ya durumu ya da rengi değiştirdiği için B1 -> 1LB gibi yalnızca konumu hareket ettiren “tembel komut” da yok

    • bbchallenge projesi içinde de şu an uzun süre çalışan şampiyonların özelliklerinin gerçekten o boyuttaki en uzun çalışan makinelerin özellikleri mi, yoksa yalnızca otomatik arama ve kanıtlaması kolay özellikleri gösteren bir sokak lambası etkisi mi olduğu tartışılıyor
      Tüm arama uzayı kesin olarak ya da sezgisel yöntemlerle elenmeden bunu bilmek mümkün değil
      BB(5, 2)’yi aşan tüm boyutlarda, sonsuza kadar çalışması beklenen ama sayı teorisinde büyük ilerlemeler olmadan kanıtlanamayan kaotik, sözde rastgele makineler bulunuyor
      Yine de uzun süre çalışan bir makinenin tamamen kaotik olamayacağı düşünülüyor
      Çünkü banda rastgele sayı gibi semboller saçarsa kısa süre içinde bir durma yapılandırmasına, döngüsel yapılandırmaya ya da basitleştirilmiş bir desene ulaşacaktır
      Buna rağmen daha yüksek düzeyde kaotik bir şeyi simüle eden, her yüksek düzey adım arasında saçma derecede çok zaman harcayıp sonra duran makineler mümkün
    • n durumlu, s sembollü bir Turing makinesi en fazla n farklı duruma geçiş yapabilir
      Bu yüzden s=4 ya da s=2 ise yalnızca çok küçük Turing makineleri spagetti kod gibi olabilir

  • Yeni BB(3,4) rekor sahibi şöyle
    0 1 2 3
    A 1RB 3LB 1RZ 2RA
    B 2LC 3RB 1LC 2RA
    C 3RB 1LB 3LC 2RC
    s satırı, t sütunundaki (t', d, s'), durum s iken bant kafasının altındaki sembol t olduğundaki geçişi ifade eder
    t sembolünü t' ile üzerine yazar, d yönüne göre sola/sağa hareket eder, ardından durumu s' olarak değiştirir; s' == Z ise durur
    Bu 3*4*log2(4*2*log2(4+1)), yani yaklaşık 64 bit bilgi miktarıdır
    Buna karşılık yalnızca 49 bitlik BBλ(49) Graham sayısını çok geride bırakır https://oeis.org/A333479

    • Farklı Turing makinelerinin sayısını saymak basit değildir
      Yukarıdaki hesap, her hücrenin keyfi bir (sembol, yön, durum) kombinasyonuna sahip olabileceğini varsayan en geniş yaklaşım olduğu için, rastgele bir Turing makinesini tanımlamak için gereken bit sayısını epey fazla hesaplar
      BB(3, 4) için Tree Normal Form, yani Brady algoritması (https://nickdrozd.github.io/2022/01/14/bradys-algorithm.html) kullanılırsa farklı Turing makinesi sayısı yalnızca yaklaşık 600 milyar olduğundan 40 bitin altında çıkar
    • Bu programda 1RZ içindeki 1R rastgele seçilmiş bir değer gibi görünüyor
      Çünkü orada durduğu için bantta ne kaldığının ya da kafanın nereye hareket ettiğinin önemi yok
      Aslında 1 yazması da önemli değil; ama 0 yazsaydı muhtemelen optimal olmazdı
      O konumda zaten 2 yazılıydı ve 1e dönüşüyor, ancak bant üzerindeki sembol sayısı ölçütüne göre 2 de aynı şekilde sayılmış olurdu
    • log2(4+1) teriminin nereden geldiğinden pek emin değilim
      3*4*log2(4*2*log2(4+1)) hesaplanınca yaklaşık 51 çıkıyor; uzman olmayan biri olarak 3*4*log2(4*2*4) = 60 olacağını düşünürdüm
      Acaba 3*4*log2(4*2*log2(3*3*4-1)) ≈ 64 mü diye merak ediyorum

  • Nasıl çalıştığını merak ettiğim için burada uyguladım: turingmachine.io/?import-gist=c862f28918f3d889f964797694d28fcc
    Kısa süre çalıştırınca neler olduğu görülüyor
    B durumu 0ı 2ye, 1i 1e çevirip C’ye geçiyor; C durumu ise 3ü 2ye çevirip A’ya geçiyor
    Bu yüzden 2 -> 1 düzeltmesini yapmak için tüm 3lerden bir kez geçmek gerekiyor; dolayısıyla 3’lerden oluşan kesintisiz aralığı tekrar tekrar üstel biçimde büyütüyor

    • Sonsuza kadar üstel büyüyen bir Turing makinesi yapmak oldukça kolay
      Gerçekten anlaşılması zor kısım, hayal edilemeyecek kadar çok adımdan sonra neden sonunda durduğu

  • Bunların hepsi aşırı code golf gibi geliyor
    Başka bir yönde BitGrid denen şeye bakılabilir
    BitGrid’de her hücrenin durumu yalnızca 4 bit olduğundan, 4x4 hücrelik bir ızgara ne olursa olsun 2^64ten fazlasını sayamaz
    Gerçekte nereye kadar sayabildiğini bulmak ilginç olabilir; küçük ızgaralarda kenar bağlantıları sonucu belirleyecektir
    https://esolangs.org/wiki/Bitgrid
    https://github.com/mikewarot/Bitgrid

  • Bu tablo muhtemelen Turing makinesi açıklaması gibi görünüyor; nasıl yorumlanacağını anlamak için bakılabilecek iyi bir kaynak olsa güzel olurdu

    • durum A, B, C, goto hedeflerine karşılık geliyor; renk 0, 1, 2, 3 ise çalışma sırasındaki veri
      Her durumda mevcut renk okunuyor ve o renge göre “hangi rengin yazılacağı, sola/sağa hareket edilip edilmeyeceği, hangi duruma gidileceği” komutu çalıştırılıyor
      C’ye aktarınca switch (SCAN) ile WRITE, RIGHT/LEFT, goto olarak birebir ifade edilebilir
      Bu mantığı daha yapılandırılmış bir tarzda yeniden yazma ya da başka optimizasyonlar yapma alanı var mı merak ediyorum
    • Her satır bir durum, her sütun ise banttan az önce okunan sembol
      Örneğin ilk satırın ilk sütunu “sembol 0 okundu ve mevcut durum A” anlamına geliyor
      Tablodaki hücreler gerçekleştirilecek eylemi gösteriyor; 1RB, “banttaki sembolü 1 olarak değiştir, sağa bir hücre ilerle, ardından durum Bye geç” demek
      Durum Z, durma durumuna karşılık geliyor
    • Python’da bant indeksini sola/sağa hareket ettiren L(), R() fonksiyonları tanımlayıp, (durum, mevcut sembol) değerini (yazılacak sembol, hareket fonksiyonu, sonraki durum) değerine eşleyen bir tablo oluşturduktan sonra state != 'Z' olduğu sürece döndürmek yeterli
    • Kısa bir açıklama https://bbchallenge.org/story#turing-machines adresinde var
      1RZ, durum Z için kural olmadığından durma geçişi olarak anlaşılabilir
      Wikipedia’da daha ayrıntılı Turing makinesi durum tablosu örnekleri de var: https://en.wikipedia.org/wiki/Turing_machine#Formal_definition; bu belirli Turing makinesinin yürütme izi ise https://bbchallenge.org/1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC adresinde görülebilir
    • Mevcut rekor sahiplerini bir araya getirip Wolfram Language ile çalıştırma örneği de gösteren küçük bir depo hazırlamıştım: https://datarepository.wolframcloud.com/resources/The-Busy-Beaver-Competition/
      Görünüşe göre şimdi bunu da güncellemek gerekecek

  • Temel bilgisayar biliminin önemli bir sonucu için atıfın Discord bağlantısı olması da neyin nesi

    • Neden olmasın, bilmiyorum
      Bilimsel sonuçları yayımlamanın tek geçerli yolunun sözde hakemli dergiler olduğu fikri, bilim topluluğunun Dunbar sayısına sığacak kadar küçük olduğu 200 yıl öncesinden kalma bir miras
      Bugün hâlâ buna tutunulmasının nedeni, bazı güçlü akademisyenlerin ve yayıncıların bundan çıkar sağlaması; bilimsel ilerleme açısından gerçek bir avantajı olması değil
      Hatta modern tekrarlanabilirlik krizinde epey büyük bir payı olması da muhtemel
      Bilimsel yöntemi güçlü biçimde destekliyorum ama geleneksel hakemliğin raf ömrünün çoktan dolduğunu düşünüyorum
      https://en.wikipedia.org/wiki/Dunbar%27s_number
    • Yine de bu herkese açık bir Discord sunucusu ve davet bağlantısını https://bbchallenge.org sitesinin sağ üstünde bulabilirsiniz
      Bunları atıftan çok kaynak gösterimi gibi görüyorum
      Sonucu destekleyen ana argüman blog yazısında daha sıkı bir biçimde yeniden kurulmuş olduğu için bağımsız olarak ayakta duruyor; Discord bağlantıları yalnızca ilgilenenler için tarihsel bağlam sağlıyor
    • Böyle sohbetlere katılınca, dinlenme odasındaki tahtada bir fikir bulup birlikte geliştirmeye benziyor; farkı, etkileşimi alıntılayabiliyor olmak
      Uygun zamanda literatürle desteklenebiliyorsa bu olumlu bir değişim
    • Şikâyeti anlıyorum ama yakın dönem matematiğindeki etkileyici ilerlemelerin önemli bir kısmı hızlı işbirliği ve yinelemeden çıktı
      Örneğin Zhang’ın asal aralık üst sınırını iyileştiren proje böyleydi; bu açıdan başka iletişim araçları Discord’un yerini kolayca tutmayabilir
      Gerçek insanların toplandığı yere gitmek gerekiyor
    • Daha büyük Busy Beaver sayıları bulmak, tam olarak temel bir iş olmaktan ziyade eğlencelik matematiğe daha yakın
      Gerçekten temel olsaydı bloga koymak yerine hakem değerlendirmesinden geçecek bir dergi makalesi olurdu

  • 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC gibi çok büyük olmayan miktarda sembolle tanımlanabilen Turing makinelerinin sayısı sınırlı
    Ama bunların bazılarının durmadan önce böylesine akıl almaz sayıda adım çalışabilmesi gerçekten şaşırtıcı

    • Böyle 3 durumlu 4 sembollü Turing makinesinden 2^60 tane var
      Çıktısı, yani normal formu Graham sayısını aşan 49 bitlik lambda terimi daha da şaşırtıcı olmalı

  • Açıkçası %100 anlamıyorum ve muhtemelen neredeyse hiç işe yaramayacak sonuçlar bunlar; ama inanılmaz derecede faydalı LLM ilerlemelerinden çok bunlar beni daha fazla çekiyor
    Sanırım “karmaşık” mühendislik sonuçlarındansa basit matematiksel gerçeklere doğal olarak daha çok çekildiğim için

  • BB(5) > BB(3,4) olması gerekmiyor mu?
    https://bbchallenge.org sitesinde BB(5)’in yaklaşık 47 milyon olduğu varsayımını kanıtlamaya ya da çürütmeye çalıştıkları yazıyor; BB(3,4) ise bundan çok daha büyük görünüyor

    • Doğru, BB(3, 4) >>> BB(5, 2) gibi görünüyor
      BB(5) = BB(5, 2) ve BB(3, 4) tablosunda 12 geçiş (3*4) varken BB(5, 2)de yalnızca 10 geçiş var; bu yüzden pek şaşırtıcı değil
      Ama BB(3, 4) >> BB(6, 2) gibi de görünüyor
      İkisinde geçiş sayısı aynı olduğundan, bu küçük Turing makinelerinde sembol sayısının daha fazla olması epey değerli görünüyor