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

BB(3, 4) > Ack(14)

• 22. Mai 2024
  • Pavel hat eine Turing-Maschine (Turing Machine, TM) mit 3 Zuständen und 4 Symbolen entdeckt
  • Diese Maschine berechnet eine Funktion auf „Ackermann-Niveau“ und hält mit genau (2↑155)+14 von Null verschiedenen Symbolen an
  • Die Knuth-Aufwärtspfeil-Notation wird etwas unhandlich, daher kann man dies wie folgt annähern: BB(3,4)>Ack(14)
  • Dabei ist Ack(14) als die 14. Ackermann-Zahl definiert: Ack(n)=n↑nn
  • Diese Maschine ist die erste in „freier Wildbahn“ entdeckte TM, die eine Funktion auf Ackermann-Niveau simulieren kann

Maschine

• Zustandsübergangstabelle

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

• Endkonfiguration

  • 0∞32g153(0)+12161 Z> 0∞
  • Genau σ=2g153(0)+18=(2↑155)+14 von Null verschiedene Symbole bleiben auf dem Band zurück

Attribution

• Entdecker
  • Diese TM wurde von Pavel Kropitz(@uni) entdeckt und am 25. April 2024 auf Discord geteilt
  • Sein Code konnte keine menschenlesbare Schranke für den TM-Score angeben und wurde einfach als Halt(SuperPowers(13)) angegeben
  • Er begann, dieses Ergebnis mit einem neuen „Validator für induktive Beweise“ zu verifizieren
  • Am 20. Mai 2024 extrahierte er die genaue Definition von gkn(m) und erhielt die Schranke σ>2↑153
  • Matthew House(@LegionMammal978) fand am 22. Mai 2024 eine einfache geschlossene Form für gkn(0)=2↑k(n+2)2−2

Analyse

• Definition von B(k,n,m)

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

• Beweis

  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>
  

• Definition von gk(m)

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

Beweis durch doppelte Induktion

• Wichtige Regel

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

• Lemma 1

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

• Korollar 2

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

• Theorem 3

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

Exakter Wert

• Theorem

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

• Korollar

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

• Schlussfolgerung

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

Permutationen

• Start in Zustand B

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

• Start in Zustand C

  σC=2g03(0)+3=(2↑05)−1=9 (hält nach 72 Schritten an)
  

• Transformiertes TNF

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

Nicht Collatz

• Interessante Punkte
  • Diese TM ist überraschend einfach
  • Es gibt keine Collatz-ähnliche Regel
  • Das schließt die Möglichkeit einer Ackermann-TM im Collatz-Stil nicht aus

Inductive Proof Validator

• Projektziel
  • Entwicklung eines Validators für „induktive Beweise“
  • Entwicklung eines standardisierten Zertifikatsformats, damit verschiedene induktive Beweise verifiziert werden können
  • Noch in einer frühen Phase, aber bereits erfolgreich beim Beweis des Verhaltens mehrerer TMs

Meinung von GN⁺

• Interessante Punkte

  • Dieser Artikel hilft sehr dabei, die Komplexität von Turing-Maschinen und der Ackermann-Funktion zu verstehen
  • Faszinierend ist, dass mit einfachen Regeln komplexe Berechnungen durchgeführt werden können

• Kritische Sicht

  • Um die Komplexität dieser Maschine zu verstehen, ist mathematisches Hintergrundwissen erforderlich
  • Der Fokus liegt eher auf theoretischem Interesse als auf praktischen Anwendungen

• Verwandte Technologien

  • Ein Validator für induktive Beweise könnte einen großen Beitrag zur Entwicklung automatisierter mathematischer Beweissysteme leisten
  • Eine Anwendung auf andere komplexe Berechnungsprobleme ist ebenfalls möglich

• Zu beachten

  • Bei der Einführung dieser Technologie sollten Genauigkeit und Effizienz des Verifizierungsprozesses berücksichtigt werden
  • Das Verständnis und die Anwendung komplexer mathematischer Konzepte erfordern Zeit

[GN⁺]

Hacker-News-Kommentare

Zusammenfassung ausgewählter Hacker-News-Kommentare

• Ein einfaches Turingmaschinenprogramm
  Entgegen der Erwartung, dass ein Turingmaschinenprogramm komplizierter Spaghetti-Code sein müsste, ist dieses neue Programm relativ einfach. Es gibt drei Zustände (A, B, C), und Zustand B übergibt die Kontrolle an A und C, während A und C nichts voneinander wissen und die Kontrolle nur an B zurückgeben. Das ergibt eine modulare Struktur; bei echtem Spaghetti-Code könnte jeder Zustand die Kontrolle an jeden anderen Zustand übergeben.

• Interessante Merkmale
  Dieses Programm schreibt keine Leerzeichen, und jeder Befehl ändert entweder den Zustand oder die Farbe. Der neue Rekordhalter für BB(3,4) enthält ungefähr 64 Bit Information. BBλ(49) übersteigt mit 49 Bit Grahams Zahl bei weitem.

• Beispiel einer Implementierung
  Wer das Programm selbst implementiert hat, stellte fest: Zustand B ändert 0 zu 2 und 1 zu 1 und wechselt dann zu C; Zustand C ändert 3 zu 2 und wechselt dann zu A. Dadurch werden Folgen von 3en exponentiell verlängert.

• Ähnlichkeit mit Code Golf
  Das wirkt alles wie extremes Code Golf. Ein privates Hobbyprojekt namens BitGrid hat nur 4 Bit Zustand pro Zelle, und ein 4x4-Gitter kann bis maximal 2^64 zählen. Bei kleinen Gittern hat die Verbindung der Ränder großen Einfluss auf das Ergebnis.

• Bitte um Material zur Interpretation von Turingmaschinen
  Es wurde nach Material gefragt, das erklärt, wie man die Tabelle interpretiert. Es scheint sich um die Beschreibung einer Turingmaschine zu handeln.

• Die Grenzen von Turingmaschinen
  Die Anzahl der Turingmaschinen, die sich mit einer begrenzten Zahl von Symbolen beschreiben lassen, ist begrenzt. Erstaunlich ist, dass einige Turingmaschinen vor dem Anhalten eine enorme Zahl von Schritten ausführen können.

• Bitte um Erklärung, was daran besonders ist
  Es wurde um eine Erklärung gebeten, warum genau dieser Befehlssatz beeindruckend ist. Gefragt wurde auch, was eine Funktion auf dem Niveau der Ackermann-Funktion ist und was hier tatsächlich berechnet wird.

• Interesse an mathematischen Wahrheiten
  Ein scheinbar nutzloses Ergebnis ist interessanter als sehr nützliche Fortschritte bei LLMs. Der Grund sei eine natürliche Anziehungskraft einfacher mathematischer Wahrheiten.

• Vergleich von BB(5) und BB(3,4)
  Es wurde gefragt, ob BB(5) größer ist als BB(3,4). Auf bbchallenge.org wird BB(5) mit etwa 47 Millionen angegeben, während BB(3,4) viel größer sein soll.

• Positiver Hinweis zum Kontext des Autors
  Es wurde positiv hervorgehoben, dass der Autor etwas Kontext geliefert hat.