Bei »fleißigen Bibern« denken die meisten Menschen wahrscheinlich nicht sofort an Mathematik. Doch tatsächlich stehen die eifrigen Tierchen sinnbildlich für eines der erstaunlichsten Konzepte des Fachs: Nicht alles ist berechenbar – völlig egal, wie sehr man sich anstrengt. Die »Fleißige-Biber-Funktion« BB(n) stellt das erste Beispiel für eine nicht berechenbare Größe dar. Die Funktion an sich lässt sich einfach erklären, ihre Werte BB(n) werden aber niemals für alle n bekannt sein. Bisher ist jedoch unklar, ab welchem n unsere mathematischen Werkzeuge versagen: Wo genau liegt die Grenze des Berechenbaren?

Lange gingen viele Fachleute davon aus, dass BB(5) hinter dieser Grenze der Berechenbarkeit liegen könnte und somit unerreichbar wäre. Doch nun ist es der internationalen Kollaboration »bbchallenge« gelungen, den Wert von BB(5) zu bestimmen und formal durch einen computergestützten Beweisassistenten überprüfen zu lassen. Demnach ist BB(5) = 47 176 870. »Das ist die größte Busy-Beaver-Entwicklung seit 1983«, schreibt der Informatiker Scott Aaronson in einem Blogbeitrag. »Ich erinnere mich genau daran, dass ich mich fragte, ob BB(5) jemals mit Sicherheit bekannt sein würde.« Das neue Ergebnis markiert damit das Ende einer jahrzehntelangen Suche.

Die fleißigen Biber sind tief in den Grundfesten der Mathematik verankert. Im 20. Jahrhundert träumten viele Fachleute davon, ein Fundament zu finden, auf dem sich alle mathematischen Wahrheiten beweisen lassen. Doch der gerade einmal 25-jährige Logiker Kurt Gödel machte die Hoffnungen im Jahr 1931 zunichte. Wie er bewies, gibt es in der Mathematik zwangsläufig unbeweisbare Aussagen – also Aussagen, die sich weder beweisen noch widerlegen lassen. Anfangs hofften Fachleute noch, das sei ein abstraktes Ergebnis ohne bedeutsame Anwendungsfälle. Doch sie lagen falsch.

Beweisbar unbeweisbar

Inzwischen sind etliche Probleme bekannt, die sich nachweislich weder beweisen noch widerlegen lassen. Eines der ersten Beispiele dafür ist das Halteproblem, das sich mit der Ausführung von Algorithmen beschäftigt. Zwar gab es in den 1930er Jahren, als Turing sich dem Problem widmete, noch keine Computer. Der Mathematiker befasste sich damals mit dem theoretischen Modell eines solchen, der nach ihm benannten Turingmaschine. Diese besteht aus einem unendlich langen Band, das mit Nullen und Einsen beschriftet ist, und einem Kopf, der das Band ausliest, beschreibt und nach rechts und links verschiebt. Eine solche Maschine kann theoretisch jede Art von Berechnung durchführen – ebenso wie ein Computer.

Angenommen, man möchte eine Turingmaschine programmieren, damit sie zwei Zahlen multipliziert. Die Nullen und Einsen auf dem Band entsprechen dann den beiden Faktoren. Vor der Berechnung muss man eine bestimmte Anzahl an Zuständen definieren, in denen sich die Maschine befinden kann, etwa A, B, C und D sowie HALT. Diese entscheiden darüber, wie die Turingmaschine agiert. Zum Beispiel: Falls die Fünf-Zustands-Maschine im Zustand A eine 1 auf dem Band einliest, überschreibt sie diese durch eine 0, schiebt das Band nach links und wechselt in Zustand C. Für jeden der Zustände A bis D braucht man also je zwei Anweisungen – je nachdem, ob die Maschine eine 1 oder eine 0 auf dem Band vorfindet. Unter bestimmten Umständen (etwa Zustand B beim Einlesen einer 1) kann die Maschine in den Zustand HALT wechseln. In diesem Fall hält die Turingmaschine an, die Berechnung ist zu Ende. Das Ergebnis sind dann die Zahlen auf dem Band.

Wie Turing bewies, gibt es keine Turingmaschine, die für alle möglichen Konfigurationen von Turingmaschinen (also alle Algorithmen) bestimmen kann, ob sie irgendwann anhalten werden. Sprich: Es ist unmöglich, für jedes beliebige Computerprogramm anzugeben, ob es irgendwann seine Arbeit beenden wird. Und hier kommen die fleißigen Biber ins Spiel.

Welcher Computer ist der fleißigste?

Der ungarische Mathematiker Tibor Radó suchte in einem 1962 entwickelten »Fleißiger-Biber-Spiel« nach der fleißigsten Turingmaschine einer bestimmten Größe: Wie viele Rechenschritte BB(n) kann eine Turingmaschine mit n Zuständen, die irgendwann zum Halten kommt, maximal durchführen?

Um die Frage allgemein zu beantworten, müsste man das Halteproblem lösen. Denn um den fleißigsten Biber zu finden, muss man wissen, welche Turingmaschinen halten und welche nicht. Damit ist die Fleißiger-Biber-Funktion BB(n) im Allgemeinen nicht berechenbar.

Dennoch konnte Radó die ersten drei Werte der BB-Funktion bestimmen – wenn auch unter teilweise großem Aufwand. Denn eine Schwierigkeit besteht darin, dass die Anzahl der möglichen Turingmaschinen (Computerprogramme) mit wachsenden Zuständen n schnell zunimmt. Für jeden der zwei Eingabewerte 0 oder 1 führt die Turingmaschine in einem bestimmten Zustand drei verschiedene Operationen aus:

1. Sie ersetzt die Eingabe durch eine Ausgabe (0 oder 1).
2. Sie schiebt das Band nach rechts oder links.
3. Sie wechselt in einen der n Zustände oder in den Haltezustand.

Damit gibt es für jeden Eingabewert und jeden der n Zustände 2·2·(n+1) mögliche Operationen. Das heißt, es gibt für n Zustände insgesamt (4n+4)²ⁿ unterschiedliche Turingmaschinen. Lässt man nur einen Zustand zu, gibt es also bereits 64 verschiedene Turingmaschinen. Davon werden nur jene anhalten, die nach dem ersten Rechenschritt in den Zustand HALT wechseln. Über einen Rechenschritt kommt also keine dieser Turingmaschinen hinaus, daher ist BB(1) = 1.

Etwas komplizierter wird es, wenn man zwei Zustände zulässt. In diesem Fall gibt es bereits 20 736 Turingmaschinen, die man untersuchen muss. Da es keine allgemein gültige Methode gibt, um zu untersuchen, welche Turingmaschinen halten, muss man sie von Einzelfall zu Einzelfall identifizieren. Wie Radó herausfand, kann das längste Programm aus zwei Zuständen – der fleißigste Biber – sechs Rechenschritte durchführen, also ist BB(2) = 6.

Auch den Fall von drei Zuständen konnten Radó und sein damaliger Doktorand Shen Lin 1965 klären: Unter den 16 777 216 Turingmaschinen können jene, die irgendwann halten, höchstens BB(3) = 21 Rechenschritte durchführen. 1963 beschrieb Radó den Versuch, BB(4) zu berechnen, als hoffnungslos. Doch damit irrte er sich. Denn 20 Jahre später gelang es Alan Brady, BB(4) zu bestimmen: Die höchste Anzahl an Rechenschritten beträgt BB(4) = 107. Das blieb vier Jahrzehnte lang der letzte Wert der Fleißige-Biber-Funktion, der sich exakt bestimmen ließ.

Ist BB(5) berechenbar?

Kurz nach Bradys Ergebnis war die Mathematik-Community daran interessiert, BB(5) exakt zu berechnen. Daher veranstalteten Fachleute 1984 in Dortmund einen Wettbewerb, bei dem sie versuchten, dem fünften Wert der Funktion auf die Spur zu kommen. Die Teilnehmer suchten nach Fünf-Zustands-Turingmaschinen, die möglichst viele Rechenschritte ausführen, bevor sie zum Halten kommen. Gewinner des Wettbewerbs war Uwe Schult, der ein Programm mit 134 467 Rechenschritten fand. Fünf Jahre später fanden die Informatiker Heiner Marxen und Jürgen Buntrock unter den Fünf-Zustands-Maschinen eine, die erst nach 47 176 870 Schritten hält und präsentierten damit einen neuen Mindestwert für BB(5). Doch es ließ sich nicht beweisen, dass nicht ein noch fleißigeres Programm unter den Fünf-Zustands-Turingmaschinen lauert.

»Die Schwierigkeit, BB(5) festzulegen, bestand nicht nur darin, dass es viele Fünf-Zustands-Turingmaschinen gibt (genau genommen 16 679 880 978 201). Die eigentliche Schwierigkeit besteht darin, zu beweisen, dass eine bestimmte Maschine unendlich lange läuft.« Um BB(n) zu bestimmen, muss man eindeutig zeigen, dass einige der Turingmaschinen niemals anhalten. Zum Beispiel muss man belegen, dass ein Programm in eine Schleife mündet, die sich immer wieder wiederholt. Noch kniffliger ist es, zu beweisen, dass eine Turingmaschine ohne ein sich wiederholendes Muster unendlich lange weiterläuft – etwa so, wie die Nachkommastellen einer irrationalen Zahl.

Die Suche nach einer haltenden Fünf-Zustands-Turingmaschine, die mehr als 47 176 870 Rechenschritte durchführt, blieb mehrere Jahrzehnte erfolglos. Daher vermuteten viele Expertinnen und Experten, darunter Aaronson, dass BB(5) = 47 176 870 ist. Aber ohne einen stichhaltigen Beweis ist das in der Mathematik nichts wert.

Deshalb startete der Informatik-Doktorand Tristan Stérin im Jahr 2022 die »bbchallenge«: Dort sollten alle Ergebnisse zu fleißigen Bibern gesammelt und überprüft werden. Wenn jemand beispielsweise bewiesen hatte, dass ein Fünf-Zustands-Programm unendlich lange weiterläuft, konnte er den Beweis dort veröffentlichen und durch einen computergestützten Beweisassistenten überprüfen lassen. So konnte eine große Zahl Interessierter zusammenarbeiten und stichhaltige Ergebnisse vorlegen. Im Juli 2024 wurde das Projekt abgeschlossen, mit dem finalen Beweis, dass BB(5) tatsächlich 47 176 870 ist.

Da die fleißigen Biber einem Algorithmus entsprechen, kann man sich fragen, was BB(5) überhaupt berechnet. Das Programm entspricht einer rekursiven Funktion, die der aus der Collatz-Vermutung ähnelt – einem der größten ungelösten Probleme der Zahlentheorie. BB(5) berechnet für eine Eingabe x den Wert ^5x+18⁄₃, falls x durch drei teilbar ist; ^5x+22⁄₃, falls x durch drei geteilt einen Rest von 1 ergibt; und falls x durch drei geteilt einen Rest von 2 hat, hält das Programm an.

Die Suche nach BB(6)

Und nun geht die Suche nach fleißigen Bibern weiter. Der Rekordhalter für Turingmaschinen mit sechs Zuständen führt bereits so viele Rechenschritte durch, dass man eine neue Rechenoperation braucht, um die Zahl in kompakter Weise aufschreiben zu können (10↑↑↑15; also 10 hoch 10 hoch 10 hoch… 10; insgesamt 15-mal). Inzwischen mehren sich aber die Hinweise, dass BB(6) wahrscheinlich nicht berechenbar ist. Denn 2024 wurde eine Sechs-Zustands-Turingmaschine gefunden, die fast dem Collatz-Problem entspricht. Möchte man zeigen, dass diese Maschine anhält (oder für immer weiterläuft), käme das quasi einer Lösung des Collatz-Problems gleich – und an diesem beißen sich etliche Fachleute seit Jahrzehnten erfolglos die Zähne aus. Eine Befürchtung ist daher, dass das Collatz-Problem zu den unbeweisbaren Aussagen der Mathematik gehört.

In diesem Fall wären die Versuche, BB(6) zu berechnen, zwangsläufig zum Scheitern verurteilt. Auch Scott Aaronson zeigt sich in seinem Blog wenig hoffnungsvoll: »Falls und wenn künstliche Superintelligenzen die Welt übernehmen, können sie sich um den Wert von BB(6) kümmern. Und dann kann Gott sich um den Wert von BB(7) sorgen.« Damit scheint es, als hätten Mathematiker mit BB(5) nun wirklich die Grenze des Berechenbaren erreicht. Aber wer weiß: Vielleicht schafft es jemand erneut, die Fachwelt zu überraschen.