BusyBeaver(6) ist wirklich riesig

 (scottaaronson.blog)
2 Punkte von GN⁺ 2025-06-29 | 1 Kommentare | Auf WhatsApp teilen
  • Die bekannte Untergrenze von BB(6) wurde erneut stark angehoben, womit bestätigt ist, dass die maximale Laufzeit einer 6-Zustands-Turing-Maschine vor dem Halt jede Größenordnung der beobachtbaren Realität bei Weitem übersteigt
  • BB(6) bezeichnet die maximale Zahl von Schritten, die eine Turing-Maschine mit 6 Zuständen und 2 Symbolen ausführen kann, wenn sie mit einem nur mit Nullen gefüllten Band startet, bevor sie anhält
  • Nach der Verbesserung durch Pavel Kropitz im Jahr 2022 hat mxdys die Untergrenze erneut auf ein Niveau angehoben, das größer ist als 10, 10 Millionen Mal iteriert potenziert
  • Das neueste Resultat zeigt, dass BB(6) mindestens 2 pentiert zu 5 ist, womit eine Operation auftritt, die noch eine Stufe über iterierter Potenzierung liegt
  • BB(5) wurde als 47.176.870 bestimmt, doch BB(6) ist überwältigend viel größer, was zu der Vermutung führt, dass der Punkt, an dem BB(n) unabhängig vom ZFC-Axiomensystem wird, schon bei n=7, 8 oder 9 liegen könnte

Die Untergrenze von BB(6) wächst erneut

  • Vor 2022 war für BB(6) nur etwa BB(6) > 10^36,534 bekannt, und Pavel Kropitz verbesserte dies auf ein Niveau, das größer ist als 10, 15-mal iteriert potenziert
  • Tetration bedeutet iterierte Potenzierung
    • Beispielsweise ist eine 15-mal aufgestapelte 10 eine Zahl der Form 10 hoch 10 hoch 10 hoch … mit insgesamt 15 Zehnern
  • BBchallenge-Organisator Tristan Sterin teilte mit, dass Teammitglied mxdys die Untergrenze von BB(6) erneut erhöht hat
    • Erste Verbesserung: BB(6) > 10, 10 Millionen Mal iteriert potenziert
    • Zu diesem Resultat gibt es einen Coq-Korrektheitsbeweis
  • Eine spätere Verbesserung von mxdys zeigt, dass BB(6) mindestens 2 tetratiert zu 2 tetratiert zu 2 tetratiert zu 9 ist
    • Insbesondere ist BB(6) mindestens 2 pentiert zu 5
    • Pentation ist iterierte Tetration und damit eine Operation, die noch eine Stufe über der iterierten Potenzierung liegt

Der extreme Unterschied zwischen BB(5) und BB(6)

  • BB(6) ist die sechste Busy-Beaver-Zahl
    • Sie bezieht sich auf Turing-Maschinen mit 6 Zuständen
    • Das Alphabet ist {0,1}
    • Das Eingabeband besteht anfangs nur aus 0
    • Gemeint ist die maximal mögliche Zahl an Ausführungsschritten vor dem Halt
  • Das internationale BBchallenge-Team bestimmte im vergangenen Jahr BB(5) als 47.176.870
  • Beim Übergang von BB(5) zu BB(6) springt die Busy-Beaver-Funktion von einer Größenordnung von zig Millionen zu Werten, die den Bereich der beobachtbaren Realität übersteigen

Zahlen, für die jedes Größengefühl versagt

  • Schon als BB(6) nur als größer als eine 10, 10 Millionen Mal iteriert potenzierte Zahl bekannt war, war eine intuitive Erklärung praktisch unmöglich
  • Als Vergleich wurde genannt, dass man mit so vielen Sandkörnern ungefähr ebenso viele Kopien des beobachtbaren Universums füllen könnte
  • Dieser Vergleich zeigt, dass die Zahl selbst gegenüber kosmisch großen Werten wie 10^100 so überwältigend ist, dass sie nach einer Division nahezu in derselben Größenordnung bleibt

Die geschätzte ZFC-Unabhängigkeit könnte früher einsetzen

  • Dass BB(6) nun so groß geworden ist, ändert nicht jede Vorstellung über die Busy-Beaver-Funktion
  • Dass BB(6) nicht nur auf einem relativ kleinen Niveau wie 10^36,534, sondern im Bereich iterierter Operationen liegen könnte, war grundsätzlich schon zuvor möglich
  • Da die tatsächliche Untergrenze nun in dieser Größenordnung bestätigt ist, könnte die Schätzung sinken, ab welchem Punkt der Wert von BB(n) unabhängig vom ZFC-Axiomensystem der Mengenlehre wird
    • Zuvor hätte man an n=20 oder 30 denken können
    • Jetzt könnte es auch n=7, 8 oder 9 sein
  • Das derzeit bekannte Resultat zur ZFC-Unabhängigkeit besagt, dass BB(n) bei n=643 unabhängig von ZFC wird

Separates Update: STOC 2025

  • In Prague bei der STOC 2025 traf der Autor mehrere Forschende und erfuhr neue Entwicklungen
  • Der Titel der STOC plenary lecture lautet The Status of Quantum Speedups
  • Interessierte Leser können die PowerPoint slides zu diesem Vortrag ansehen

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-06-29
Hacker-News-Kommentare

  • Auf dem bbchallenge-Discord-Server wird derzeit lebhaft darüber spekuliert, wie viele Zustände eine Turingmaschine wohl braucht, um Graham's Number zu übertreffen, die weit größer ist als 2^^2^^2^^9, erreicht vom aktuellen BB(6)-Champion.
    Wenn man sich den functional busy beaver https://oeis.org/A333479 ansieht, könnten Verhaltensweisen auf Graham-Niveau überraschend früh auftreten. Ein Lambda-Term mit 49 Bit reicht aus.
    Geschlossene Lambda-Terme bis zu dieser Größe gibt es nur 77.519.927.606 https://oeis.org/A114852, während es 4^12*23836540=399910780272640 eindeutige Turingmaschinen mit 6 Zuständen gibt https://oeis.org/A107668.
    Da Pentation schon mit 6 Zuständen erreicht wurde, glauben inzwischen mehrere Leute, dass 7 Zustände ausreichen könnten, um Graham's Number zu übertreffen. Ich finde das trotzdem immer noch ziemlich erstaunlich. Vor ein paar Tagen habe ich mit einem von ihnen eine große Wette darüber abgeschlossen, ob in den nächsten 10 Jahren ein Beweis für BB(7)>Graham's auftaucht; mich würde interessieren, wie ihr das seht.

    • Ich kann nicht so tun, als wäre ich Experte, aber BB(7) ist vermutlich größer als Graham's Number.
      BB muss schneller wachsen als jede berechenbare Folge. Was das konkret für BB(7) bedeutet, ist letztlich eher eine Handwaving-Erklärung, aber es fühlt sich so an, als müsste man die Leiter der Operatorstärken sehr schnell hinaufsteigen. Am Ende muss es schneller wachsen als jeder berechenbare Operator, den wir definieren, einschließlich etwa up-arrow^n oder up-arrow^f(n) für eine berechenbare Funktion f.
      Intuitiv wirkt der Sprung von 47 million zu 2^^2^^2^^9 in Bezug auf die benötigte Operatorstärke qualitativ größer als der Sprung von 2^^2^^2^^9 zu Graham's Number. Graham's Number ist g_64, wobei g ungefähr eine Stufe über up_arrow^n liegt; daher ist BB(7)>Graham's Number vermutlich wahrscheinlich.

  • Dass eine Zahl wie BB(748), noch dazu eine nicht berechenbare Zahl, „unabhängig von ZFC“ sein kann, macht mich ganz schwindlig. Das fühlt sich irgendwie wie ein Kategorienfehler an.

    • Was BB(748) unabhängig von ZFC macht, ist nicht der Wert selbst, sondern dass eine der Maschinen mit 748 Zuständen, TM_ZFC_INC, so konstruiert ist, dass sie in ZFC nach einem Widerspruch sucht, also nach einem Beweis von FALSE, und nur dann hält, wenn sie ihn findet.
      Daher müsste ein Beweis von BB(748)=N zeigen, dass TM_ZF_INC innerhalb von N Schritten hält, oder dass sie niemals hält. Wenn man annimmt, dass ZFC konsistent ist, ist beides wegen Gödels berühmtem Ergebnis unmöglich.
    • Nicht berechenbar ist BB(n), das heißt: Es gibt keinen Algorithmus, der für ein beliebiges n den Wert von BB(n) ausgibt.
      BB(748) ist berechenbar. Per Definition ist es die Anzahl der Einsen, die irgendeine Turingmaschine mit 748 Zuständen aufschreibt, und diese Maschine berechnet BB(748).
      Die Zahl selbst ist buchstäblich nur eine unvorstellbar große ganze Zahl. ZFC-Unabhängigkeit kommt ins Spiel, wenn man beweisen will, dass diese Zahl genau die gesuchte ist. Dafür braucht man eine Theorie, die stärker als ZFC ist und die Eigenschaften von Turingmaschinen mit 748 Zuständen erfassen kann.
    • Überraschender ist eher die Vorstellung, dass ein kurzer Text wie die ZFC-Axiome, der locker auf eine Serviette passt, „ausreichen“ sollte, um arithmetische Wahrheit oder die Aspekte der physischen Realität zu erfassen, die hauptsächlich mit menschlichem Handeln zusammenhängen.
      Dass das Verhalten einer Turingmaschine mit 6 Zuständen mit ein paar Zeilen Text unvorhersagbar sein kann, ist überhaupt nicht überraschend.
      Ich hätte gedacht, dass die gesamte Mathematikgemeinde direkt nach Gödels Veröffentlichung des ersten Unvollständigkeitssatzes mit Vollgas nach weiteren Axiomen gesucht hätte. Stattdessen wurde Gödels Arbeit fast ein Jahrhundert lang eher wie eine merkwürdige Tatsache aus einem engen Bereich der Grundlagenforschung behandelt, nicht wie ein Mainstream-Programm. Ich kenne Feferman, Friedman und andere, aber in diesem Gebiet wird im Vergleich zu den meisten anderen Themen der Mathematik viel weniger geforscht.
    • Die Zahl selbst ist nicht unabhängig von ZFC. Jede ganze Zahl ist in ZFC darstellbar. Unabhängig von ZFC ist der Prozess zur Berechnung von BB(748).
    • Einzelne Zahlen an sich sind nicht unberechenbar. Es gibt kein Paar aus einer Zahl und einem Beweis in ZFC, das belegt, dass diese Zahl der Wert von BB(748) ist.
      Daher gibt es auch kein Programm, von dem ZFC beweisen kann, dass es den Wert von BB(748) ausgibt. Aber wie bei jeder anderen Zahl existiert ein Programm, das BB(748) ausgibt.

  • Es ist bekannt, dass BB(14) größer als Graham's Number ist, aber angesichts dieses Ergebnisses scheint BB(7) vermutlich ebenfalls größer als Graham's Number zu sein.
    Intuitiv fühlt sich die Technik, die man braucht, um von Pentation zu Graham's Number zu gelangen, einfacher an als die Technik, die man braucht, um von 47,176,870 zu 2 5 zu kommen.

  • Als ich die Erklärung sah, dass linker Hochindex Tetration, also wiederholte Potenzierung, bedeutet, dachte ich zuerst, es sei ein Tippfehler. Tetration war mir neu.

    • Ich hatte es früher schon einmal gesehen, damals aber mit Knuths Pfeilschreibweise, die mir gefällt, weil sie sich leicht verallgemeinern lässt https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation.
    • Wenn man dem Gedanken der Wiederholung weiter folgt, bin ich diesmal erstmals auf Pentation gestoßen.

  • Ich verstehe die Stelle nicht: „Stell dir vor, es gäbe 10,000,000sub10 Sandkörner. Dann könnte man damit etwa 10,000,000sub10 beobachtbare Universen füllen.“
    Wird da wirklich der Wert „Volumen des beobachtbaren Universums geteilt durch durchschnittliches Sandkornvolumen“ weggerundet? Das wären viel mehr Größenordnungen Unterschied als die Gesamtmasse des Universums, die man normalerweise für Vergleiche heranzieht.

    • Ja. Durch dieses Verhältnis zu teilen hat in dieser Notation praktisch kaum einen Effekt, weil „benachbarte“ Zahlen in ihr viel größere Veränderungen bedeuten.
      10↑↑10,000,000 / (Sandkörner pro Universum) ist zum Beispiel immer noch überwältigend größer als 10↑↑9,999,999.
      In einem System, das solche Zahlen verwendet, gibt es für (eine extrem große Zahl)/(eine bloß kosmische Größenordnung) kaum eine bessere Darstellung, als es genau so zu schreiben; in der Notation der extrem großen Zahl wird es am Ende praktisch zu (eine extrem große Zahl) gerundet.
    • Bei Tetration geht es nicht mehr um die Größenordnung der Ziffernzahl, sondern um die Größenordnung der Größenordnung der Ziffernzahl.
    • Ein geläufigeres Beispiel für solche Vergleiche: In signifikanten Stellen betrachtet ist eine Milliarde minus eine Million immer noch eine Milliarde.
    • Genau. Diese Zahl ist so viel größer als Größen wie 10^100000 oder die Anzahl der Sandkörner, dass sie sich durch eine Division in dieser Größenordnung praktisch nicht ändert. Jedenfalls sinkt sie nicht annähernd in Richtung 9,999,999sub10.
    • Ja. Das ist nur ein Unterschied in der Ziffernzahl einer gewöhnlichen Zahl. Schon 10,000,000^10,000,000 ist groß genug, dass so etwas keine Rolle mehr spielt; umso mehr, wenn man danach auch noch den Exponenten selbst neun weitere Male potenziert hat.

  • Scott Aaronsons How Much Math Is Knowable? [Harward CMSA]: https://www.youtube.com/watch?v=VplMHWSZf5c
    War vor ein paar Monaten auch auf HN: https://news.ycombinator.com/item?id=43776477

  • Was ist die ausdrucksstärkste Logik, deren Beweise sich schon mit einer 5-Zustands-Turingmaschine aufzählen lassen?

    • Diese Frage hängt davon ab, was man als Aufzählung gelten lässt; eine verwandte Frage wäre aber: „Was ist die ausdrucksstärkste Logik, die nicht beweisen kann, ob alle 5-Zustands-Turingmaschinen halten?“ Also: Für welche ausdrucksstärkste Logik ist die Haltefrage einer bestimmten 5-Zustands-Turingmaschine unabhängig?
      Über diese Version habe ich etwas nachgedacht, bin aber mangels Expertise in Prädikatenlogik erster Stufe nicht weit gekommen. Soweit ich weiß, ist Skelet #17 https://bbchallenge.org/1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA eine der Maschinen, deren Nicht-Anhalten mathematisch am schwierigsten zu beweisen ist https://arxiv.org/abs/2407.02426; eine Theorie, die beweisen kann, dass Skelet #17 nicht hält, kann wahrscheinlich auch die übrigen 5-Zustands-Maschinen entscheiden.
    • Das hängt vollständig davon ab, wie man endliche Binärstrings als Aufzählung logischer Beweise interpretiert.

  • Als ich die Erklärung las: „BB(6) ist die sechste Busy-Beaver-Zahl, also die maximale Anzahl von Schritten, die eine 6-Zustands-Turingmaschine mit dem Alphabet {0,1} auf einem anfangs komplett mit 0 gefüllten Band ausführen kann, bevor sie hält“, hatte ich als Nichtfachmann eher das Gefühl, dass ich sie zu gut verstanden habe.
    Das ist offensichtlich ein Hardcore-Blog für Leute, die seit Jahrzehnten an so etwas arbeiten. Es ist ziemlich cool, zufällig auf einen Text zu stoßen, der für ein bestimmtes Publikum so kompromisslos dicht und voller Fachbegriffe geschrieben ist.

    • Wer eine Informatik-Grundausbildung im Studium hatte, sollte mit dieser Erklärung ungefähr verstehen können, worum es geht, selbst wenn er dem Busy-Beaver-Problem zum ersten Mal begegnet.
      Es ist zwar ein Nischenfachbegriff, aber zu glauben, nur Leute mit jahrzehntelangem Investment könnten Zugang dazu finden, unterschätzt einen selbst.
    • Diese Definition gehört zum Standardstoff der theoretischen Informatik im Grundstudium. In der Softwareentwicklung ist sie allerdings möglicherweise kein Standard.

  • So große Zahlen kann ein Mensch nicht visualisieren. Zahlen lassen sich nicht nur durch einfaches Zählen darstellen.
    Zum Beispiel kann man schon einem einzelnen Sandkorn unendlich viele mögliche Zustände zuschreiben. Da es unendlich viele reelle Zahlen gibt, könnte man sagen, ein einzelnes Sandkorn könne BB(6) darstellen. Kombinationen können exponentiell wachsen, vielleicht ist so ein Ansatz für die Darstellung nützlich.

    • Ab einem gewissen Punkt sind große Zahlen viel eher Konsistenzstärke eines formalen Systems als „große Mengen“.
      Es geht also darum, wie lange ein System so tun kann, als sei es widerspruchsfrei, bevor es auffliegt. Ein widersprüchliches System, das über BB(3) Konsistenz vortäuscht, wird viel schneller „entlarvt“ als eines, das dies über BB(6) tut. Mit Konsistenz vortäuschen ist hier gemeint, dass es behauptet, alle Programme, die für ein bestimmtes n länger als BB(n) Schritte laufen, würden nicht halten.
    • Wenn das Universum auf die nächste Planck-Einheit gerundet wird, hat ein einzelnes Sandkorn plötzlich gar nicht mehr so viele mögliche Zustände.
      Unendliche Präzision heranzuziehen, um es handhabbar erscheinen zu lassen, wirkt auf mich wie Taschenspielerei. Wenn man Größenordnungen erklären will, sollte man besser ganze Zahlen verwenden.
    • Dieses Beispiel verwirrt mich. Wenn die Anzahl der Sandkörner und die Anzahl der beobachtbaren Universen gleich sind, hieße das dann nicht: ein Sandkorn pro Universum?

  • Ich frage mich, ob das beobachtbare Universum groß genug ist, um den exakten Wert von BB(6) aufzuschreiben

    • Wenn man das beobachtbare Universum als geschlossenes System betrachtet, kann man die Bekenstein-Grenze anwenden
      R ≈ 46.5 billion light-years, also den Radius des beobachtbaren Universums, und E ≈ den gesamten Masse-Energie-Inhalt des beobachtbaren Universums
      Zur Masse-Energie zählen gewöhnliche Materie, Dunkle Materie und Dunkle Energie. Nach heutigen Schätzungen hat das beobachtbare Universum ungefähr ein Masse-Energie-Äquivalent von 10^53 kg
      Setzt man das in S ≤ 2πER/ℏc ein, ergibt sich eine maximale Informationsmenge in der Größenordnung von etwa 10^120 bits
      S ≤ 2πER/ℏc
      S ≤ (2 × 3.141593 × 3.036e+71 × 4.399e+26)/(1.055e-34 × 299792458)
      S ≤ 2.654135e+124
      S ≤ 10^120
      Daher ist es unmöglich
    • Es reicht definitiv nicht aus. Die im Universum speicherbare Informationsmenge liegt ungefähr bei 10^120 Bit. Selbst wenn ich um eine Billion Stellen danebenläge, würde das Ergebnis sich nicht ändern
    • Allein die Startzahl im Artikel ist ¹⁵10. Das bedeutet 10^(¹⁴10), hat also ¹⁴10 Stellen. Man kann sie also nicht aufschreiben
    • Vermutlich ist gemeint, dass alle Teile der vollständigen Darstellung gleichzeitig existieren. Wenn sie nicht gleichzeitig existieren müssen, könnte man sie vielleicht „aufschreiben“, falls die Lebensdauer des Universums unendlich ist. Ich weiß nicht, wie der Wärmetod hier hineinspielt, daher nur „vielleicht“
      In der relativistischen Raumzeit ist „gleichzeitig“ allerdings nicht gut definiert. Die Geschwisterkommentare haben im Bezugssystem, das die kosmische Mikrowellen-Hintergrundstrahlung nahelegt, sicher recht. Ich frage mich nur, ob es in irgendeinem Bezugssystem eine Art geben könnte, die Raumzeit so zu schneiden, dass eine „gleichzeitige“ Darstellung möglich wird