Fleißiges Biberspiel

Das Busy Beaver Game ist ein theoretisches Informatikproblem, das 1962 vom Mathematiker Tibor Radó vorgeschlagen wurde. Bei dem Spiel handelt es sich um eine spezielle Art von Turingmaschine, die als „Busy Beaver“ bezeichnet wird. Dabei handelt es sich um ein Programm, das darauf ausgelegt ist, möglichst viele „1en“ auf ein unendlich langes Stück Papierband zu schreiben. Betrachten Sie im Busy Beaver-Spiel bei einer gegebenen positiven Ganzzahl alle Turingmaschinen mit Zuständen (einschließlich Eingabealphabet und Zustandsübergangsfunktion usw.). Das Ziel des Spiels besteht darin, eine Turingmaschine zu finden, die bei einer leeren Eingabe die längste Zeit (oder die meisten Schritte) benötigt, bevor sie stoppt, und dabei die größte Anzahl von Einsen ausgibt. Die Anzahl der Einsen in dieser Ausgabe ist der Wert der Busy-Beaver-Funktion, der der positiven Ganzzahl entspricht, bezeichnet mit BB(n), wobei n die Anzahl der Zustände der Turingmaschine ist.

Im September 2024 gab ein Team aus mehr als 20 Mitwirkenden bekannt, dass sie die fünfte fleißige Biberzahl, BB(5), mit einem Wert von 47.176.870 gefunden hätten. Dieses Ergebnis ist Teil des von Tristan Stérin initiierten Projekts Busy Beaver Challenge, einer Online-Zusammenarbeit mit dem Ziel, den Wert von BB(5) endgültig zu bestimmen. Das Team überprüfte seine Ergebnisse mithilfe der Software „Coq Proof Assistant“, einem formalen Verifizierungstool, das zur Sicherstellung der Genauigkeit mathematischer Beweise verwendet wird.