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

BB(3, 4) > Ack(14)

• 22 Mayıs 2024
  • Pavel, 3 durumlu 4 sembollü bir Turing makinesi (Turing Machine, TM) keşfetti
  • Bu makine "Ackermann düzeyi" bir fonksiyon hesaplıyor ve tam olarak (2↑155)+14 adet sıfır olmayan sembolle duruyor
  • Knuth yukarı ok gösterimi biraz kullanışsız hale geldiği için bu şu şekilde yaklaşık ifade edilebilir: BB(3,4)>Ack(14)
  • Burada Ack(14), 14. Ackermann sayısı olarak tanımlanır: Ack(n)=n↑nn
  • Bu makine, "vahşi doğada" keşfedilen ve Ackermann düzeyi bir fonksiyonu simüle edebilen ilk TM'dir

Makine

• Durum geçiş tablosu

  | 0   | 1   | 2   | 3   |
  | --- | --- | --- | --- |
  | A   | 1RB | 3LB | 1RZ | 2RA |
  | B   | 2LC | 3RB | 1LC | 2RA |
  | C   | 3RB | 1LB | 3LC | 2RC |
  

• Son yapılandırma

  • 0∞32g153(0)+12161 Z> 0∞
  • Tam olarak σ=2g153(0)+18=(2↑155)+14 adet sıfır olmayan sembol bant üzerinde kalır

Attribution

• Keşfeden kişi
  • Bu TM, Pavel Kropitz(@uni) tarafından keşfedildi ve 25 Nisan 2024'te Discord'da paylaşıldı
  • Onun kodu, TM skoru için insan tarafından okunabilir bir sınır belirleyemiyordu ve yalnızca Halt(SuperPowers(13)) olarak belirtilmişti
  • Bu sonucu doğrulamaya yeni bir "indüktif ispat doğrulayıcısı" kullanarak başladı
  • 20 Mayıs 2024'te gkn(m) için tam tanımı çıkardı ve σ>2↑153 sınırını elde etti
  • Matthew House(@LegionMammal978), 22 Mayıs 2024'te gkn(0)=2↑k(n+2)2−2 için basit bir kapalı form buldu

Analiz

• B(k,n,m) tanımı

  B(k,n,m)=0∞32m+12k A> 1n
  

• İspat

  0∞A>0∞→241B(16,3,0)20∞
  B(k,n,m)→B(k,0,gk−1n(m)) if k≥1
  B(k,0,m)2→10∞32m+12k1Z>
  

• gk(m) tanımı

  g0(m)=m+1
  gk+1(m)=gk2m+2(0)
  

Çift indüksiyonla ispat

• Ana kural

  B(k,n,m)→B(k,0,gk−1n(m))
  

• Lemma 1

  For all k≥1: 32k<B→2k+12k<B1
  

• Sonuç 2

  For all k≥1,m≥0: 3m2k<B→(2k+1)m2k<B1m
  

• Teorem 3

  For all k≥1,n≥0,m≥0: B(k,n,m)→B(k,0,gk−1n(m))
  

Kesin değer

• Teorem

  For all k≥0,m≥0: 2gk+1(m)+4=2↑k(2m+4)
  

• Sonuç

  For all k≥0,n≥0: 2gkn(0)+4=2↑k(n+2)
  

• Sonuç cümlesi

  σ=2g153(0)+18=(2↑155)+14
  

Permütasyonlar

• B durumundan başlatma

  σB=2g63(0)+9=(2↑65)+5
  

• C durumundan başlatma

  σC=2g03(0)+3=(2↑05)−1=9 (72 adımda durur)
  

• Dönüştürülmüş TNF

  | 0   | 1   | 2   | 3   |
  | --- | --- | --- | --- |
  | A   | 1RB | 3RB | 1LC | 2LA |
  | B   | 2LA | 2RB | 1LB | 3RA |
  | C   | 3LA | 1RZ | 1LC | 2RA |
  

Collatz değil

• İlginç nokta
  • Bu TM şaşırtıcı derecede basit
  • Collatz benzeri bir kural yok
  • Bu durum, Collatz benzeri Ackermann düzeyi TM'lerin var olma ihtimalini dışlamaz

İndüktif İspat Doğrulayıcısı

• Projenin hedefi
  • Bir "indüktif ispat" doğrulayıcısı geliştiriliyor
  • Farklı indüktif ispatları doğrulayabilmek için standartlaştırılmış bir sertifika biçimi geliştiriliyor
  • Hâlâ erken aşamada, ancak birden fazla TM'nin davranışını ispatlamada başarı sağladı

GN⁺ görüşü

• İlginç tarafı

  • Bu yazı, Turing makineleri ile Ackermann fonksiyonunun karmaşıklığını anlamaya büyük katkı sağlıyor
  • Basit kurallarla karmaşık hesaplamalar yapılabilmesi etkileyici

• Eleştirel bakış

  • Bu makinenin karmaşıklığını anlamak için matematiksel arka plan bilgisi gerekiyor
  • Pratik uygulamalardan çok teorik ilgiye odaklanıyor

• İlgili teknolojiler

  • İndüktif ispat doğrulayıcısı, otomatik matematiksel ispat sistemlerinin geliştirilmesine büyük katkı sağlayabilir
  • Başka karmaşık hesaplama problemlerine de uygulanma potansiyeli var

• Dikkate alınması gerekenler

  • Bu teknolojiyi devreye alırken doğrulama sürecinin doğruluğu ve verimliliği dikkate alınmalı
  • Karmaşık matematiksel kavramları anlamak ve uygulamak zaman gerektirir

[GN⁺]

Hacker News görüşü

Hacker News yorumları derleme özeti

• Basit Turing makinesi programı
  Turing makinesi programının karmaşık bir spagetti kod olacağı düşüncesinin aksine, bu yeni program görece basit. Üç durum (A, B, C) var; B durumu denetimi A ve C'ye devrediyor, ancak A ile C birbirini bilmiyor ve denetimi yalnızca B'ye devrediyor. Bu, modüler bir yapı; gerçek bir spagetti kodda ise her durum denetimi diğer tüm durumlara devredebilir.

• İlginç özellikler
  Bu program boş hücre yazdırmıyor ve tüm komutlar durumu ya da rengi değiştiriyor. Yeni BB(3,4) rekor sahibi yaklaşık 64 bit bilgi içeriyor. BBλ(49), 49 bit ile Graham sayısını çok büyük ölçüde aşıyor.

• Uygulama örneği
  Programı bizzat uygulamayı deneyince, B durumunun 0'ı 2'ye, 1'i 1'e dönüştürüp C'ye geçtiği; C durumunun ise 3'ü 2'ye dönüştürüp A'ya geçtiği görülüyor. Bu da 3'lerden oluşan dizileri üstel olarak uzatıyor.

• Code golf ile benzerlik
  Bütün bunlar aşırı uçta bir code golf gibi görünüyor. BitGrid adlı kişisel hobi projesinde hücre başına yalnızca 4 bit durum var ve 4x4 bir grid en fazla 2^64'e kadar sayabiliyor. Küçük gridlerde kenar bağlantıları sonucu ciddi biçimde etkiliyor.

• Turing makinesi yorumlama kaynağı talebi
  Tablonun nasıl yorumlanacağına dair kaynak talebi var. Bunun bir Turing makinesi açıklaması olduğu anlaşılıyor.

• Turing makinesinin sınırları
  Sınırlı sayıda sembolle tanımlanabilen Turing makinelerinin sayısı da sınırlı. Bazı Turing makinelerinin durmadan önce inanılmaz derecede fazla adım çalışabilmesi şaşırtıcı.

• Neden özel olduğuna dair açıklama talebi
  Bu belirli komut kümesinin neden etkileyici olduğuna dair açıklama isteniyor. Ackermann fonksiyonu düzeyindeki bir fonksiyonun ne olduğu ve gerçekte ne hesapladığı merak ediliyor.

• Matematiksel doğrulara duyulan ilgi
  Faydasız gibi görünen bu sonuç, çok daha faydalı olan LLM ilerlemelerinden bile daha ilgi çekici geliyor. Bunun nedeni, basit matematiksel doğrulara doğal olarak çekilmek.

• BB(5) ile BB(3,4) karşılaştırması
  BB(5)'in BB(3,4)'ten büyük olup olmadığı soruluyor. bbchallenge.org sitesinde BB(5)'in yaklaşık 47 milyon olduğu yazıyor, ancak BB(3,4)'ün çok daha büyük olduğu söyleniyor.

• Yazarın bağlam sunması
  Yazarın bir miktar bağlam sunmuş olması olumlu karşılanıyor.