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

 (sligocki.com)
1 Punkte von GN⁺ 2024-05-25 | 1 Kommentare | Auf WhatsApp teilen
  • Ein neuer Champion unter den 3-State-4-Symbol-Busy-Beaver-Turingmaschinen wurde gefunden; berechnet wurde, dass er beim Anhalten ((2 \uparrow^{15} 5) + 14) Nicht-Null-Symbole hinterlässt
  • Diese Zahl ist selbst in Knuths Up-Arrow-Notation enorm groß und wird als Untergrenze (BB(3,4) > Ack(14)) zusammengefasst, die die 14. Ackermann-Zahl übertrifft, definiert durch (Ack(n)=n \uparrow^n n)
  • Das Kernverhalten der TM lässt sich in etwa zu (B(k,n,m) \to B(k,0,g_{k-1}^n(m))) komprimieren, der Nachweis erfordert jedoch doppelte Induktion
  • Dank Matthew Houses geschlossener Auswertungsformel (g_k^n(0)=\frac{2 \uparrow^k (n+2)}{2}-2) lässt sich der endgültige Score (\sigma=(2 \uparrow^{15}5)+14) exakt angeben
  • Diese TM simuliert eine Funktion auf Ackermann-Niveau auch ohne Collatz-artige Restklassen-Verzweigungen und dient zudem als Verifikationsbeispiel für den in Entwicklung befindlichen Inductive Proof Validator

Größenordnung des neuen Busy-Beaver-Champions

  • Pavel Kropitz hat einen neuen Champion unter den 3-State-4-Symbol-Busy-Beavern entdeckt
  • Diese TM kann eine Funktion auf „Ackermann-Niveau“ berechnen und hinterlässt beim Anhalten die folgende Anzahl von Nicht-Null-Symbolen auf dem Band
    • ((2 \uparrow^{15} 5) + 14)
  • Der Wert ist selbst in Knuths Up-Arrow-Notation enorm groß, daher lässt sich die Untergrenze wie folgt zusammenfassen
    • (BB(3,4) > Ack(14))
  • Dabei ist (Ack(14)) die 14. Ackermann-Zahl, definiert durch (Ack(n)=n \uparrow^n n)
  • Soweit bekannt ist dies unter den tatsächlich bei der Suche gefundenen TMs der erste Fall, der eine Funktion auf Ackermann-Niveau simulieren kann

Definition der TM und Endkonfiguration

  • Der Übergangsstring der TM lautet wie folgt
    • 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC
  • Die Übergangstabelle ist für die Zustände A, B, C und die Symbole 0, 1, 2, 3 definiert
    • A: 1RB, 3LB, 1RZ, 2RA
    • B: 2LC, 3RB, 1LC, 2RA
    • C: 3RB, 1LB, 3LC, 2RC
  • Die Endkonfiguration lautet wie folgt
    • (0^\infty ;; 3^{2 g_{15}^{3}(0) + 1} ;; 2^{16} ;; 1 ;; \text{ Z> } ;; 0^\infty)
  • Aus dieser Konfiguration wird der Score (\sigma) exakt berechnet
    • (\sigma = 2 g_{15}^{3}(0) + 18 = (2 \uparrow^{15} 5) + 14)

Entdeckung und Verifikationsprozess

  • Pavel Kropitz teilte diese TM am 25. April 2024 auf Discord
  • Der damalige Code konnte keine menschenlesbare Untergrenze für den Score angeben und zeigte das Ergebnis als Halt(SuperPowers(13)) an
    • Das bedeutet, dass der Beweis 13 Ebenen von Induktionsregeln benötigt
  • Anschließend begann die Verifikation mit dem neuen Inductive Proof Validator
  • Am 20. Mai 2024 wurde die Verifikation abgeschlossen; dabei wurde die exakte Definition von (g_k^n(m)) extrahiert, wodurch sich die Untergrenze (\sigma > 2 \uparrow^{15} 3) ergab
  • Matthew House entdeckte am 22. Mai 2024 die folgende einfache geschlossene Auswertungsformel
    • (g_k^n(0) = \frac{ 2 \uparrow^k (n+2) }{2} - 2)
  • Mit dieser Auswertungsformel lässt sich der exakte Wert von (\sigma) ausdrücken

Verhaltensanalyse und Beweis durch doppelte Induktion

  • Die folgende Konfiguration wird definiert
    • (B(k, n, m) = 0^\infty ;; 3^{2m+1} ;; 2^k ;; \text{ A> } ;; 1^n)
  • Die Anfangskonfiguration erreicht nach 241 Schritten den folgenden Zustand
    • (0^\infty ;; \text{A>} ;; 0^\infty \xrightarrow{241} B(16,3,0);;2;;0^\infty)
  • Die Kernregel lautet wie folgt
    • (B(k,n,m) \to B(k,0,g_{k-1}^n(m))), wobei (k \ge 1)
  • (g_k) ist durch die folgende Rekursion definiert
    • (g_0(m)=m+1)
    • (g_{k+1}(m)=g_k^{2m+2}(0))
  • Das Gesamtverhalten ist so einfach, dass es fast zu einer einzigen Regel komprimiert werden kann; diese Regel selbst muss jedoch durch doppelte Induktion bewiesen werden
  • Lemmata und Korollare behandeln den Prozess, in dem der Zustand B die Blöcke 3 und 2^k verarbeitet und 1en erzeugt
    • (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)
  • Satz 3 zeigt, dass die Kernregel für alle (k \ge 1, n \ge 0, m \ge 0) gilt
    • Der Basisfall (k=1) wird per Induktion über (n) behandelt
    • Der Induktionsschritt verwendet zugleich die Annahme über (k) und die Induktionsannahme über (n)

Berechnung des exakten Werts

  • Für (g_k) gibt es eine relativ einfache geschlossene Auswertung, die nur Knuths Up-Arrow-Notation und Arithmetik verwendet
  • Für alle (k \ge 0, m \ge 0) gilt Folgendes
    • (2 g_{k+1}(m) + 4 = 2 \uparrow^k (2m+4))
    • Dabei ist (a \uparrow^0 b = ab) definiert
  • Dieses Ergebnis wird per Induktion über (k) bewiesen
    • Im Basisfall (k=0) ergibt sich (g_1(m)=2m+2)
    • Im Induktionsschritt wird die wiederholte Anwendung von ((2 \uparrow^k)^n) verwendet
  • Die geschlossene Form beruht auf dem Zufall, dass (2 \uparrow^k 2 = 4) für alle (k) gilt
    • Wären die Parameter leicht anders und hätte sich eine Form wie ((2 \uparrow^k)^{2m+2}5) ergeben, wäre eine geschlossene Darstellung vermutlich schwer zu finden gewesen
  • Als Korollar gilt für alle (k \ge 0, n \ge 0) Folgendes
    • (2 g_k^n(0) + 4 = 2 \uparrow^k (n+2))
  • Der endgültige Score folgt direkt so
    • (\sigma = 2 g_{15}^{3}(0) + 18 = (2 \uparrow^{15} 5) + 14)

Permutationsergebnisse bei geändertem Startzustand

  • Wird der Startzustand auf B oder C geändert, ergeben sich kleinere verwandte Resultate
    • (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)
  • Der Score beim Start im Zustand B lautet wie folgt
    • (\sigma_B = 2 g_6^3(0) + 9 = (2 \uparrow^6 5) + 5)
  • Beim Start im Zustand C hält die TM nach 72 Schritten an; der Score lautet wie folgt
    • (\sigma_C = 2 g_0^3(0) + 3 = (2 \uparrow^0 5) - 1 = 9)
  • Auch die erste Permutation mit Start in B ist eine weitere hochplatzierte BB(3,4)-TM
  • Umgewandelt in TNF ergibt sich der folgende Übergangsstring
    • 1RB3RB1LC2LA_2LA2RB1LB3RA_3LA1RZ1LC2RA

Einfachheit ohne Collatz-artige Regeln

  • Einer der interessanten Punkte an dieser TM ist, dass sie einfacher ist als erwartet
  • Es gibt keine Collatz-like-Regel, die je nach Restklasse eines Werts unterschiedlich agiert
  • Ob die Dominanz Collatz-like TMs vorbei ist, lässt sich noch nicht sagen
  • Es gibt die Vermutung, dass noch Ackermann-level Collatz-like TMs existieren könnten, die aufgrund von Selektionsverzerrungen nicht unmittelbar sichtbar sind
  • Der Grund, warum diese TM als erste Ackermann-level TM gefunden wurde, könnte darin liegen, dass sie einfach genug ist, um einen Haltebeweis zu ermöglichen, ohne modulare Arithmetik über einer Ackermann-level Funktion zu implementieren

Inductive Proof Validator

  • Diese TM eignete sich als Testfall für den in Entwicklung befindlichen Inductive Proof Validator
  • Ziel des Projekts ist es, ein standardisiertes Zertifikatsformat für „Induktionsbeweise“ zu schaffen
  • „Induktionsbeweise“ wird hier als Oberbegriff für Forward Reasoning und regelbasierte Analyse insgesamt verwendet
  • Die Idee ist, dass jeder, der einen „inductive decider“ hat, die entsprechende Regel in diesem Format beschreiben kann und der Validator dann den Beweis prüft
  • Das System ist noch sehr roh und nicht einsatzbereit, wurde aber mit etwas Handarbeit bereits verwendet, um das Verhalten mehrerer TMs zu beweisen, darunter diese TM

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-05-25
Hacker-News-Kommentare

  • Man könnte leicht annehmen, dass Turingmaschinenprogramme, die sehr lange laufen, tief verschachtelt oder Spaghetti-Code sind, aber dieser neue Champion ist fast ein Gegenbeispiel.
    Es gibt nur drei Zustände, A, B und C; B übergibt die Kontrolle an A und C, aber A und C „kennen“ einander nicht und kehren nur zu B zurück.
    Wäre es wirklich Spaghetti-Code, könnte jeder Zustand zu jedem anderen Zustand übergehen, aber das hier ist eine Art modulare Struktur.
    Außerdem schreibt er niemals ein Leerzeichen, und jede Anweisung ändert entweder den Zustand oder die Farbe, daher gibt es auch keine „faulen Anweisungen“ wie B1 -> 1LB, die nur die Position bewegen.

    • Selbst innerhalb des bbchallenge-Projekts wird darüber diskutiert, ob die Eigenschaften der aktuellen langlebigen Champions tatsächlich die Eigenschaften der am längsten laufenden Maschinen dieser Größe sind oder ob nur der Straßenlaternen-Effekt sichtbar ist, also Eigenschaften, die sich für automatische Suche und Beweisführung leicht finden lassen.
      Das lässt sich nicht wissen, bevor man den gesamten Suchraum entweder deterministisch oder heuristisch ausgeschlossen hat.
      Für alle Größen oberhalb von BB(5, 2) erwartet man Maschinen, die für immer laufen, deren chaotische oder pseudorandomisierte Natur sich ohne große Fortschritte in der Zahlentheorie jedoch nicht beweisen lässt.
      Allerdings halte ich es für unwahrscheinlich, dass lange laufende Maschinen vollständig chaotisch sind.
      Wenn sie zufallsartig Symbole aufs Band schreiben würden, würden sie bald eine Haltekonfiguration, eine zyklische Konfiguration oder ein vereinfachtes Muster erreichen.
      Möglich sind aber Maschinen, die auf höherer Ebene etwas Chaotisches simulieren, zwischen den einzelnen Hochlevel-Schritten absurd viel Zeit verbrauchen und dann doch anhalten.
    • Eine Turingmaschine mit n Zuständen und s Symbolen kann nur in höchstens n verschiedene Zustände übergehen.
      Deshalb können bei s=4 oder s=2 nur sehr kleine Turingmaschinen wie Spaghetti-Code aussehen.

  • Der neue BB(3,4)-Rekordhalter sieht so aus:
    0 1 2 3
    A 1RB 3LB 1RZ 2RA
    B 2LC 3RB 1LC 2RA
    C 3RB 1LB 3LC 2RC
    Das (t', d, s') in Zeile s, Spalte t bezeichnet den Übergang, wenn sich die Maschine im Zustand s befindet und das Symbol unter dem Bandkopf t ist.
    Dabei wird das Symbol t mit t' überschrieben, dann entsprechend der Richtung d nach links oder rechts bewegt und anschließend der Zustand auf s' gesetzt; wenn s' == Z, hält die Maschine an.
    Das entspricht 3*4*log2(4*2*log2(4+1)), also ungefähr 64 Bit Informationsgehalt.
    Dagegen übertrifft schon BBλ(49) mit nur 49 Bit Grahams Zahl bei weitem https://oeis.org/A333479

    • Die Anzahl unterschiedlicher Turingmaschinen zu zählen ist nicht trivial.
      Die obige Rechnung ist die weiteste Methode, bei der jedes Feld als beliebige Kombination aus (Symbol, Richtung, Zustand) betrachtet wird, und überschätzt daher die benötigten Bits zur Beschreibung einer beliebigen Turingmaschine erheblich.
      Für BB(3, 4) kommt man mit Tree Normal Form, also dem Brady-Algorithmus (https://nickdrozd.github.io/2022/01/14/bradys-algorithm.html), auf nur etwa 600 Milliarden verschiedene Turingmaschinen und damit auf weniger als 40 Bit.
    • In diesem Programm wirkt das 1R in 1RZ wie ein willkürlich gewählter Wert.
      Da dort angehalten wird, ist es egal, was auf dem Band bleibt oder wohin sich der Kopf bewegt.
      Eigentlich ist auch das Schreiben der 1 nicht wichtig, aber wenn stattdessen 0 geschrieben würde, wäre es wohl nicht optimal gewesen.
      An dieser Stelle stand bereits eine 2, sie wird zu 1, aber nach der Anzahl der Symbole auf dem Band wäre 2 genauso gezählt worden.
    • Ich verstehe nicht ganz, wie der Term log2(4+1) zustande kommt.
      Wenn man 3*4*log2(4*2*log2(4+1)) ausrechnet, kommt ungefähr 51 heraus, und aus Sicht eines Nichtfachmanns hätte ich eher 3*4*log2(4*2*4) = 60 erwartet.
      Vielleicht ist eher 3*4*log2(4*2*log2(3*3*4-1)) ≈ 64 gemeint?

  • Ich war neugierig auf die Funktionsweise und habe es hier implementiert: turingmachine.io/?import-gist=c862f28918f3d889f964797694d28fcc
    Wenn man es kurz laufen lässt, sieht man, was passiert.
    Zustand B ersetzt 0 durch 2 und 1 durch 1 und wechselt nach C, während Zustand C 3 durch 2 ersetzt und nach A wechselt.
    Um also 2 -> 1 zu korrigieren, muss man jedes Mal durch alle 3 hindurch, wodurch die aufeinanderfolgenden 3er-Abschnitte wiederholt exponentiell anwachsen.

    • Eine Turingmaschine zu bauen, die ewig exponentiell wächst, ist ziemlich einfach.
      Der wirklich schwer verständliche Teil ist, warum sie nach unvorstellbar vielen Schritten am Ende doch anhält.

  • Das klingt alles wie extremes Code Golf.
    In eine andere Richtung könnte man sich BitGrid ansehen.
    Bei BitGrid hat jede Zelle nur 4 Bit Zustand, daher kann ein 4x4-Zellraster unmöglich über 2^64 hinauszählen.
    Es wäre interessant herauszufinden, wie weit es tatsächlich zählen kann, und bei kleinen Gittern dürften die Randverbindungen das Ergebnis dominieren.
    https://esolangs.org/wiki/Bitgrid
    https://github.com/mikewarot/Bitgrid

  • Diese Tabelle scheint wohl die Beschreibung einer Turing-Maschine zu sein; es wäre hilfreich, wenn es Material gäbe, das erklärt, wie man sie lesen soll.

    • Die Zustände A, B, C entsprechen den Zielen von goto, und die Farben 0, 1, 2, 3 sind die Daten während der Ausführung.
      In jedem Zustand wird die aktuelle Farbe gelesen, und abhängig davon wird die Anweisung ausgeführt, „welche Farbe ausgegeben werden soll, ob man sich nach links oder rechts bewegen soll und in welchen Zustand gewechselt werden soll“.
      Beim Umsetzen in C lässt sich das direkt mit switch (SCAN) sowie WRITE, RIGHT/LEFT und goto ausdrücken.
      Ich frage mich, ob es Spielraum gibt, diese Logik in einem stärker strukturierten Stil neu zu schreiben oder andere Optimierungen vorzunehmen.
    • Jede Zeile ist ein Zustand, und jede Spalte ist das Symbol, das gerade vom Band gelesen wurde.
      Zum Beispiel bedeutet die erste Zeile, erste Spalte: „Symbol 0 wurde gelesen und der aktuelle Zustand ist A“.
      Die Zellen der Tabelle geben die auszuführende Aktion an; 1RB bedeutet „ändere das Bandsymbol zu 1, bewege dich ein Feld nach rechts und wechsle dann in Zustand B“.
      Zustand Z ist der Haltezustand.
    • In Python kann man Funktionen L() und R() für das Bewegen des Bandindex nach links bzw. rechts definieren, dann eine Tabelle erstellen, die (Zustand, aktuelles Symbol) auf (zu schreibendes Symbol, Bewegungsfunktion, nächster Zustand) abbildet, und das Ganze wiederholen, solange state != 'Z' gilt.
    • Eine einfache Erklärung gibt es unter https://bbchallenge.org/story#turing-machines.
      1RZ kann man als Halteübergang verstehen, da es für Zustand Z keine Regel gibt.
      Auf Wikipedia gibt es auch ausführlichere Beispiele für Zustandstabellen von Turing-Maschinen unter https://en.wikipedia.org/wiki/Turing_machine#Formal_definition, und die Ausführungsspur genau dieser Turing-Maschine ist unter https://bbchallenge.org/1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC zu sehen.
    • Ich habe ein kleines Repository erstellt, das die aktuellen Rekordhalter sammelt und auch Beispiele zeigt, wie man sie in Wolfram Language ausführt: https://datarepository.wolframcloud.com/resources/The-Busy-Beaver-Competition/
      Das muss jetzt wohl auch aktualisiert werden.

  • Dass als Zitat für ein wichtiges Resultat der theoretischen Informatik ein Discord-Link dient.

    • Ich verstehe nicht, warum das problematisch sein soll.
      Die Vorstellung, dass die einzig gültige Form der Veröffentlichung wissenschaftlicher Ergebnisse ein sogenanntes peer-reviewtes Journal sei, ist ein Relikt aus einer Zeit vor 200 Jahren, als die wissenschaftliche Gemeinschaft klein genug war, um innerhalb von Dunbars Zahl zu liegen.
      Dass man bis heute daran festhält, liegt daran, dass einige einflussreiche Wissenschaftler und Verlage davon profitieren, nicht daran, dass es für den wissenschaftlichen Fortschritt echte Vorteile hätte.
      Im Gegenteil könnte das sogar eine ziemlich große Mitverantwortung an der heutigen Reproduzierbarkeitskrise tragen.
      Ich unterstütze die wissenschaftliche Methode sehr stark, aber das traditionelle Peer Review hat seine Haltbarkeit längst überschritten.
      https://en.wikipedia.org/wiki/Dunbar%27s_number
    • Es ist immerhin ein öffentlicher Discord-Server, und auf https://bbchallenge.org findet man den Einladungslink oben rechts.
      Ich würde das weniger als Zitat denn eher als Quellenangabe sehen.
      Die Hauptargumentation, die das Ergebnis stützt, wird im Blogbeitrag in strengerer Form reproduziert und steht daher für sich allein; der Discord-Link liefert nur historischen Kontext für Interessierte.
    • Wenn man an solchen Chats teilnimmt, ist das ähnlich, als würde man an einer Tafel im Aufenthaltsraum Ideen entwickeln und gemeinsam weiterdenken, mit dem Unterschied, dass man auf die Interaktion verweisen kann.
      Wenn man das zu gegebener Zeit mit Literatur absichern kann, ist das eine positive Entwicklung.
    • Ich verstehe den Unmut, aber ein erheblicher Teil der beeindruckenden Fortschritte in der jüngeren Mathematik kam aus schneller Zusammenarbeit und rascher Iteration.
      So war es zum Beispiel bei dem Projekt zur Verbesserung von Zhangs oberer Schranke für Primzahllücken, und in dieser Hinsicht lassen sich andere Kommunikationswerkzeuge womöglich nicht ohne Weiteres durch Discord ersetzen.
      Man muss dorthin gehen, wo die Menschen tatsächlich sind.
    • Die Suche nach größeren Busy-Beaver-Zahlen ist nicht gerade im strengen Sinne Grundlagenforschung, sondern eher unterhaltsame Mathematik.
      Wenn es wirklich so grundlegend wäre, wäre es nicht in einem Blog veröffentlicht worden, sondern als Journalartikel durch Peer Review gegangen.

  • Die Anzahl möglicher Turing-Maschinen, die sich mit nicht allzu vielen Symbolen wie 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC beschreiben lassen, ist begrenzt.
    Umso erstaunlicher ist es, dass einige davon vor dem Halten derart absurd viele Schritte ausführen können.

    • Von diesen Turing-Maschinen mit 3 Zuständen und 4 Symbolen gibt es 2^60.
      Noch erstaunlicher müsste sein, dass ein 49-Bit-Lambda-Term, dessen Ausgabe bzw. Normalform die Graham-Zahl übersteigt, existiert.

  • Ehrlich gesagt verstehe ich das nicht zu 100 % und es sind wohl Ergebnisse mit kaum praktischem Nutzen, aber trotzdem zieht mich das mehr an als unglaublich nützliche Fortschritte bei LLMs.
    Vermutlich, weil mich einfache mathematische Wahrheiten natürlicherweise stärker anziehen als „komplexe“ ingenieurtechnische Resultate.

  • Müsste es nicht BB(5) > BB(3,4) heißen?
    Auf https://bbchallenge.org steht, dass man versucht, die Vermutung zu beweisen oder zu widerlegen, dass BB(5) etwa 47 Millionen beträgt, aber BB(3,4) scheint viel größer zu sein.

    • Stimmt, es sieht nach BB(3, 4) >>> BB(5, 2) aus.
      BB(5) = BB(5, 2), und BB(3, 4) hat 12 Übergänge in der Tabelle (3*4), während BB(5, 2) nur 10 hat, daher ist das nicht allzu überraschend.
      Es scheint aber auch zu gelten, dass BB(3, 4) >> BB(6, 2) ist.
      Beide haben gleich viele Übergänge, daher scheint bei solchen kleinen Turing-Maschinen eine größere Zahl von Symbolen ziemlich wertvoll zu sein.