Eine 10-Zustands-Turingmaschine namens n1 wurde identifiziert, die den aktuellen BB(10)-Champion übertrifft. Die veröffentlichte Schranke des Champions ist f_ω(f_ω(25)), auf der Stufe ω der schnell wachsenden Hierarchie. n1 hebt den BB(10)-Rekord auf die Stufe ω+1. Die Maschine wird aus einer 8-Zustands-Basismaschine gebildet, die in den Zuständen A bis E mit dem BB(8)-Rekord übereinstimmt und dieselbe Ziffernlisten-Berechnung wie der Rekord ausführt, nämlich das Programm des BB(7)-Champions mit 36 Ziffern.
Die Forscher erweiterten die Basismaschine, indem sie deren Haltübergang an einen neuen Zustand I sendeten und die Zustände I und J hinzufügten. Die Maschine hält von einem leeren Band aus. Ihr genauer Wert ist in Coq bewiesen, einem maschinell überprüften Beweisassistenten, ohne Axiome. Der Wert liegt zwischen zwei Werten von f_(ω+1) und platziert die Maschine damit auf einer höheren Stufe der Hierarchie als den vorherigen Champion.
Die Beweise zeigen, dass die Anzahl der auf dem Band verbleibenden Einsen die Graham-Zahl übersteigt und größer ist als F, angewandt N = (6T − 19)/7 ≈ 0,86·T-mal auf 33, wobei T = 2↑^37 3 der Wert ist, den der BB(8)-Rekord berechnet. Die Standardbewertung ist die Anzahl der Einsen plus eins, da der Haltübergang eine 1 schreibt.
Die Analyse folgt der Notation von Ligocki für den BB(7)-Champion, bei der der Bandinhalt als Blöcke aus abwechselnden Ziffern und Nullen kodiert wird. Jeder Löschschritt auf einem Token verändert den Akkumulatorwert um einen Turm von Exponentialen, dessen Höhe von der Tiefe des Tokens abhängt. Das Ergebnis ist eine maschinell verifizierte untere Schranke, die frühere Rekorde weit übertrifft.
Die Maschine wurde am 8. Oktober 2026 dokumentiert und ist in einem öffentlichen Repository von jeff87654 festgehalten. Das Ergebnis ist für das Busy-Beaver-Problem bedeutsam, das nach der maximalen Anzahl von Schritten oder Einsen fragt, die eine haltende Maschine gegebener Größe erzeugen kann.
Quelle: Hacker News · Zusammengefasst von HeadlinesBriefing