BusyBeaver(6) ist wirklich riesig

• Die sechste Busy-Beaver-Zahl (BB(6)) hat durch neue Forschungsergebnisse kürzlich eine stark erhöhte Untergrenze erhalten
• Zuvor war BB(6) als BB(6) > 10↑36,534 bekannt, 2022 wurde dies jedoch auf BB(6) > 10↑1510 angehoben
• Kürzlich wurde bei BBchallenge BB(6) > 10↑10,000,00010 gezeigt und anschließend weiter auf 2 ↑↑ (2 ↑↑ (2 ↑↑ 9)) aktualisiert
• Die Größe von BB(6) übersteigt jede Vorstellung; diese Zahl ist so groß, dass sie das gesamte Universum unzählige Male füllen könnte
• Diese Fortschritte sind ein Anlass, die Grenzen und das Potenzial der mathematischen Logik und der Berechenbarkeitstheorie neu wahrzunehmen

---

Überblick über die jüngsten Forschungsergebnisse zu BB(6)

• In den letzten Jahren fühlten sich die Weltlage und das Forschungsumfeld anhaltend schwierig an
• Der Fortschritt in der Busy-Beaver-Forschung war jedoch ein Anlass, sich wieder an die reine Begeisterung für Forschung zu erinnern
• 2022 bewies Pavel Kropitz, dass BB(6) > 10↑1510 gilt
  • BB(6) bezeichnet, wie oft eine Turing-Maschine mit 6 Zuständen auf einem vollständig mit Nullen beschriebenen Band maximal arbeiten kann, bevor sie anhält
  • Dabei steht ^1510 für den Wert, bei dem 10 15-mal als Potenz auf sich selbst iteriert wird (Tetration)
• Frühere Forschung hatte gezeigt, dass BB(5) den Wert 47,176,870 hat (Team BBchallenge); dies markiert den Punkt, an dem solche Zahlen explosionsartig in Bereiche jenseits der beobachtbaren Realität anwachsen

Prozess der jüngsten Aktualisierung der Untergrenze

• „mxdys“ von BBchallenge bewies BB(6) > 10↑10,000,00010
  • Dieser Beweis basiert auf einem formalen Beweis, der in der Sprache Coq geschrieben wurde
• Danach wurde die Untergrenze erneut auf BB(6) > 2 ↑↑ (2 ↑↑ (2 ↑↑ 9)) aktualisiert
  • ↑↑ bezeichnet Tetration, also die Iteration von Potenzierung; hier wird 2 mit 2 tetratiert und dieses Ergebnis wiederum in einer 9-fachen verschachtelten Form verwendet
  • Zahlen dieser Größenordnung liegen jenseits jeder bisherigen intuitiven Vorstellung
• Zur Einordnung: Pentation bedeutet die Iteration von Tetration und ist damit eine Operation jenseits von Multiplikation, Potenzierung und Tetration

Die Größe solcher Zahlen begreifen

• Auf Bitte eines Journalisten musste die Größenordnung von 10↑10,000,00010 erläutert werden
• Diese Zahl reicht aus, um 10↑10,000,00010 Universen vollständig mit Sand zu füllen
• Damit wird verdeutlicht, dass die Werte von BB(6) weit über die tatsächlich beobachtbare Welt hinausgehen

Überlegungen zu den grundlegenden Grenzen des BB-Algorithmus

• Die enorme Größe von BB(6) zeigt das wahre Potenzial der Busy-Beaver-Funktion
• Es wurde geschätzt, dass der Punkt, an dem der Wert BB(n) vom Axiomensystem der Mengenlehre (ZFC) unabhängig wird, ungefähr bei n=20~30 liegt; inzwischen erscheint es jedoch plausibel, dass dies bereits bei n=7~9 der Fall sein könnte
  • Derzeit ist offiziell bekannt, dass Unabhängigkeit bei n=643 vorliegt

Anhang: Neuigkeiten zu jüngsten Veranstaltungen und Vorträgen

• Der Autor nahm kürzlich an der Veranstaltung STOC'2025 in Prag teil, tauschte sich dort mit verschiedenen Forschenden aus und gewann neue Informationen
• Er teilte auch die Folien seines Keynote-Vortrags zum Stand der Quantenbeschleunigung
• Einen ausführlicheren Bericht dazu will er später veröffentlichen

[GN⁺]

Hacker-News-Kommentare

• Im bbchallenge-Discord-Server wurde geteilt, wie Leute darüber spekulieren, wie viele Zustände eine Turingmaschine haben müsste, um Graham's Number zu übertreffen. Selbst die 2^^2^^2^^9, die der jüngste BB(6)-Sieger erreicht hat, ist bereits eine gewaltige Zahl, doch es überrascht, dass ein Wachstum in der Größenordnung von Graham's Number vielleicht früher auftauchen könnte als gedacht. Erwähnt werden Material zum functional busy beaver [1], wonach schon 49-Bit-Lambda-Terme ausreichen könnten, die Tatsache, dass es von geschlossenen Lambda-Termen dieser Größe nur 77519927606 gibt [2], während es 399910780272640 verschiedene 6-Zustands-Turingmaschinen gibt [3]. Da Pentation inzwischen mit nur 6 Zuständen implementiert wurde, scheint unter vielen Beteiligten die Stimmung zu herrschen, dass 7 Zustände auch Graham's Number übertreffen könnten. Der Verfasser findet das trotzdem weiterhin überraschend. Er erwähnt, vor ein paar Tagen eine hohe Wette darauf abgeschlossen zu haben, ob innerhalb der nächsten 10 Jahre ein Beweis erscheinen wird, dass BB(7) Graham's Number übertrifft, und fragt nach den Meinungen anderer. (1, 2, 3 Links beigefügt)
  • Ich will nicht so tun, als wäre ich Experte, aber ich würde vorhersagen, dass BB(7) größer als Graham's Number ist. BB muss schneller wachsen als jede beliebige berechenbare Zahlenfolge, daher kann man bei der tatsächlichen Größe von BB(7) nur grob mit der Hand hinzeigen, aber die Richtung ist, dass es letztlich schneller wachsen muss als alle berechenbaren Operatoren, etwa up-arrow^n. Mein Eindruck ist, dass der Sprung von 47176870 zu 2^^2^^2^^9 hinsichtlich der Operatorstärke viel dramatischer ist als der Sprung von 2^^2^^2^^9 zu Graham's Number. Graham's Number ist g_64, was sich ebenfalls als ein Konzept eine Stufe über up-arrow^n interpretieren lässt, daher die Intuition, dass BB(7) Graham's Number übertreffen wird.
• Es wird als äußerst faszinierend beschrieben, dass eine nicht berechenbare Zahl wie BB(748) unabhängig von ZFC (dem Axiomensystem der Mengenlehre) ist. Das fühlt sich ehrlich gesagt fast wie ein Kategorienfehler an.
  • Der Grund, warum BB(748) unabhängig von ZFC ist, liegt nicht am Wert selbst, sondern daran, dass unter den 748 Zuständen eine Maschine TM_ZFC_INC steckt, die genau dann anhält, wenn sie in ZFC einen Widerspruch findet, also einen Beweis für Falschheit. Um zu beweisen, dass BB(748)=N gilt, müsste man zeigen, dass TM_ZFC_INC innerhalb von N Schritten anhält oder unendlich weiterläuft; nach Gödels Unvollständigkeitssatz ist das aber, sofern ZFC widerspruchsfrei ist, etwas, das sich gerade nicht beweisen lässt.
  • Noch erstaunlicher ist das Gefühl, dass schon ein Text mit so wenigen Zeilen, also die ZFC-Axiome selbst, genügend wichtige arithmetische Wahrheiten ausdrücken kann, um für Menschen bedeutsam zu sein. Dass man das Verhalten sogar von 6-Zustands-Turingmaschinen nicht einfach vorhersagen kann, ist dann nur natürlich. Nach der Veröffentlichung von Gödels Unvollständigkeitssätzen hätte sich die Mathematik vielleicht viel aktiver auf die Suche nach weiteren Axiomen machen sollen; stattdessen wurde das nur in Teilen der Grundlagenforschung aufgegriffen, was bedauert wird.
  • Der Wahrheitswert der Kontinuumshypothese, platonisch betrachtet also 1 oder 0, ist ein gutes Beispiel dafür, dass dieser Wert von ZFC unabhängig ist. Nicht einmal ein einziges Bit ist also durch ZFC garantiert, und zwar ganz ohne gigantische Zahlen.
  • Es wird sauber unterschieden: BB(n) ist nicht berechenbar, und BB(748) ist definitionsgemäß die Anzahl der von einer 748-Zustands-Turingmaschine geschriebenen Einsen und damit eine berechenbare Zahl. Das Label „unabhängig“ bedeutet hier, dass man zur Beweisführung, dass diese Zahl tatsächlich den gewünschten Wert hat, eine stärkere Theorie als ZFC braucht.
  • Nicht die Zahl selbst ist unabhängig von ZFC, sondern der Prozess, BB(748) zu berechnen. (Jede ganze Zahl lässt sich in ZFC ausdrücken.)
• Dass BB(14) größer als Graham's Number ist, sei ein bekannter Sachverhalt, und diese neue Arbeit gebe nun das Gefühl, dass auch BB(7) mindestens so groß sein dürfte wie Graham's Number. Intuitiv wirkt der gedankliche Weg von Pentation zu Graham's Number sogar einfacher als der von 47.176.870 zu 2 <pentate> 5.
  • Gute Info, das könnte eine hervorragende Antwort auf meinen Beitrag sein.
• Geteilt werden Scott Aaronsons YouTube-Vortrag „How Much Math Is Knowable?“ [Harward CMSA] https://www.youtube.com/watch?v=VplMHWSZf5c sowie ein aktueller HN-Diskussionsbeitrag https://news.ycombinator.com/item?id=43776477.
• Es wird erklärt, dass die „linke obere Hochstellung“ Tetration ist, also wiederholte Potenzierung. ¹⁵10 bedeutet demnach 10 hoch 10 hoch ... insgesamt 15-mal. Jemand teilt, dass ihm das Konzept neu war und er zunächst an einen Tippfehler dachte.
  • Im Anschluss an das Thema wiederholter Operationen reagiert jemand, dass er diesmal zum ersten Mal von „Pentation“ gehört habe.
  • Tetration habe ich schon früher gesehen, aber ich bevorzuge Knuths up-arrow-Notation [1], weil sie verbreiteter und besser zu verallgemeinern ist. (1)
• Die Erklärung, dass BB(6) die maximale Schrittzahl einer 6-Zustands-2-Symbol-({0,1})-Turingmaschine auf einem anfänglich mit 0 gefüllten Band bis zum Anhalten ist, war für Nichtfachleute sehr hilfreich. Es wurde deutlich, dass dieses Feld von hochverdichteten Inhalten und spezialisierter Terminologie für Forschende über Jahrzehnte geprägt ist, aber gleichzeitig war es faszinierend, zufällig auf einen so tiefgehenden Beitrag zu stoßen.
  • Wer auf dem Niveau eines Informatik-Bachelorstudiums ist, sollte auch beim ersten Kontakt mit dem busy-beaver-Problem grundsätzlich folgen können. Natürlich gibt es viel Spezialvokabular, aber man muss nicht das Gefühl haben, das sei nur für Menschen mit jahrzehntelanger Erfahrung zugänglich.
  • Es wird ergänzt, dass diese Definition eher in der theoretischen Informatik als im Software Engineering Standard ist.
• Die Aussage, dass man mit 10,000,000 sub10 Sandkörnern das beobachtbare Universum 10,000,000 sub10-mal füllen könne, sorgt für Verwirrung. Üblicher sei ein Vergleich über die Masse des beobachtbaren Universums; in dieser Form liege der Wert ohnehin schon weit über der tatsächlich vorhandenen Materiemenge.
  • Ja, das stimmt. Selbst wenn man durch Sandkörner pro Universum teilt, bleibt die Zahl in derselben absurden Größenordnung, und benachbarte Zahlen liegen in dieser Notation extrem weit auseinander. Auch 10↑↑10,000,000 / (Sandkörner/Universum) ist noch weit größer als 10↑↑9,999,999. In unserem Zahlensystem wird also (sehr groß) / (kosmisch groß) effektiv immer noch zu (sehr groß).
  • Bei Tetration vergleicht man nicht mehr bloß die Stellenzahl, sondern die „Stellenzahl der Stellenzahl“.
  • Diese Zahl wird selbst durch etwa 10^100000 Sandkörner überhaupt nicht merklich kleiner, daher hat das Teilen im Wesentlichen keinen Einfluss.
  • Schon 10,000,000^10,000,000 ist grotesk groß; hängt man noch einen weiteren Exponenten-Schwanz daran, wird der Vergleich praktisch sinnlos.
  • Als vertrauteres Beispiel wird angeführt, dass es bei signifikanten Stellen keine grobe Vereinfachung ist zu sagen: 1 Milliarde − 1 Million = 1 Milliarde.
• Es wird die Frage aufgeworfen, was das „reichhaltigste“ logische System ist, dessen Beweise man mit einer 5-Zustands-Turingmaschine aufzählen könnte.
  • Je nachdem, wie man „aufzählen“ definiert, kann die Antwort unterschiedlich ausfallen. Sinnvoll ist auch die verwandte Frage: Was ist das stärkste logische System, das dennoch nicht alle Haltefragen für 5-Zustands-Turingmaschinen beweisen kann? Da es mathematisch sehr schwierig sei zu beweisen, dass Skelet #17 [0] nicht anhält, wird die persönliche Einschätzung geteilt, dass eine Theorie, die das leisten kann, vermutlich auch alle übrigen 5-Zustands-Turingmaschinen entscheiden könnte. (0, 1)
  • Man müsse zunächst präzisieren, wie endliche binäre Zeichenketten überhaupt als Aufzählung logischer Beweise interpretiert werden sollen, bevor man die Prämisse diskutieren kann.
• Es wird gefragt, ob das beobachtbare Universum groß genug wäre, um den exakten Wert von BB(6) aufzuschreiben.
  • Wenn man das beobachtbare Universum als geschlossenes System betrachtet und die Bekenstein-Grenze anlegt, liegt die maximale speicherbare Informationsmenge nur bei etwa 10^120 Bit. Nach aktuellen Schätzungen beträgt die gesamte Masse-Energie ungefähr 10^53kg; setzt man das in die Formel ein, landet man ebenfalls in der Größenordnung von 10^120 Bit. Damit ist es unmöglich.
  • Die im Universum speicherbare Informationsmenge liegt bei ungefähr 10^120 Bit, und selbst wenn man um viele Größenordnungen danebenläge, bliebe die Aussage gleich: Es ist ganz offensichtlich nicht genug.
  • Vermutlich wird angenommen, dass der gesamte Wert gleichzeitig gespeichert werden muss. Fällt die Bedingung der Gleichzeitigkeit weg, könnte eine Aufzeichnung theoretisch vielleicht über unendliche Zeit hinweg erfolgen, allerdings mit realen Grenzen wie dem Wärmetod des Universums. Im Referenzrahmen der kosmischen Hintergrundstrahlung ist es unmöglich, aber vielleicht könnte man über andere Raumzeit-Schnitte nachdenken.
  • Schon die erste Zahl im Artikel ist ¹⁵10, also von der Form 10^(¹⁴10); allein die Zahl der Stellen ist also ¹⁴10, daher völlig ausgeschlossen.
  • Eine knappe Bestätigung: unmöglich.
• Angesichts solcher Resultate aus der Komplexitätstheorie wird jedes Mal deutlicher, wie haltlos modische Thesen der Art „Superintelligenz ist Gott“ sind. Selbst wenn man alle Atome des Universums in einen Supercomputer verwandeln und zusätzlich die Energie schwarzer Löcher nutzen würde, könnte man den Haltezustand von BB(6) dennoch niemals vollständig ausrechnen.
  • Solche Strohmänner waren von Anfang an nicht überzeugend.