Ironischerweise hören sich einige der hartnäckigsten mathematischen Probleme unserer Zeit erstaunlich einfach an. Ein Beispiel dafür ist die goldbachsche Vermutung, die der Mathematiker Christian Goldbach 1742 in einem Brief an Leonhard Euler erwähnte. Sie lautet: Jede gerade Zahl, die größer ist als zwei, lässt sich als Summe zweier Primzahlen darstellen. Überprüfen Sie es ruhig: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, 10 = 5 + 5 und so weiter. Tatsächlich wurde die Vermutung für mehr als 10¹⁷ gerade Zahlen getestet – und kein Gegenbeispiel entdeckt. Auch die berühmte Collatz-Vermutung, die aus zwei einfachen Berechnungen besteht, ist seit fast 100 Jahren unbewiesen: Man nehme eine Zahl, teile sie durch zwei, falls sie gerade ist; sonst multipliziert man sie mit drei und addiert eins hinzu. Das Ganze wiederholt man für das Ergebnis immer und immer wieder und erhält eine Zahlenfolge, bis man schließlich bei dem Wert 1 landet. Zum Beispiel: 10, 5, 16, 8, 4, 2, 1. Die Collatz-Vermutung besagt, dass man bei jedem Startwert irgendwann die 1 erreicht.

Für beide Vermutungen gab es schon etliche Beweisversuche. Doch alle führten bisher in eine Sackgasse. Einen spannenden Ansatz bietet ein Konzept, das auf die Grundlagen der Informatik zurückgeht.

Für die goldbachsche Vermutung wäre der Ansatz folgender: Man schreibt ein Computerprogramm, das für gerade Zahlen prüft, ob sie sich als Summe zweier Primzahlen schreiben lassen. Falls es möglich ist, nimmt sich der Algorithmus die nächstgrößere gerade Zahl vor; falls nicht, hält es an. Das Programm hält also an, sobald es auf ein Gegenbeispiel zur goldbachschen Vermutung stößt, sonst läuft es bis in alle Ewigkeit weiter. Um herauszufinden, ob die Vermutung wahr ist, muss man also bloß überprüfen, ob das entsprechende Computerprogramm irgendwann anhält.

Das klingt zwar einfach, aber die Aufgabe stößt an die Grenzen der Wissenschaft. Denn tatsächlich gibt es nachweislich keine Möglichkeit, für alle Algorithmen zu prüfen, ob ein sie ausführender Computer irgendwann zum Halten kommt. Das heißt, es wird immer Programme geben, die bis in alle Ewigkeit laufen und von denen man niemals erfahren wird, ob sie nicht irgendwann doch ein Ergebnis ausspucken. Wie sich das Programm zur goldbachschen Vermutung verhalten wird, weiß man bisher nicht. Klar ist: Da bisher 10¹⁷ Beispiele überprüft wurden, läuft der Algorithmus zumindest sehr, sehr lange. Um allerdings nicht bis in die Unendlichkeit auf eine Lösung warten zu müssen, könnten »fleißige Biber« behilflich sein: Hat man eine bestimmte Schwelle an Wartezeit überschritten, kann man sicher sein, dass der Algorithmus nicht mehr halten wird – so zumindest die Theorie. In der Praxis gestaltet sich das jedoch schwierig.

Unbeweisbare Aussagen erschweren die Suche nach einem Beweis

Der Grund, warum man nicht einfach vorhersagen kann, ob gewisse Computerprogramme zu einem Ende kommen, ist das so genannte Halteproblem. Dieses untersuchte erstmals der Mathematiker Alan Turing Ende der 1930er Jahre. Anlass dazu gaben die Arbeiten von Kurt Gödel, dessen »Unvollständigkeitssätze« die Mathematik erschütterten: Diese besagen, dass es innerhalb eines mathematischen Systems immer Aussagen geben wird, die sich weder beweisen noch widerlegen lassen. Anfangs hofften Fachleute noch, dass das ein abstraktes Ergebnis ohne bedeutsame Anwendungsfälle sei. Doch sie lagen falsch.

Inzwischen sind etliche Probleme bekannt, die sich nachweislich weder beweisen noch widerlegen lassen. Eines der frühesten Beispiele dafür war besagtes Halteproblem, das sich mit der Ausführung von Algorithmen beschäftigt. Natürlich 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 dividiert. Die Nullen und Einsen auf dem Band entsprechen dann den beiden Werten, die man dividieren möchte. 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 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 Sie sich wahrscheinlich vorstellen können, erfordert das Programmieren einer Turingmaschine etwas mehr Aufwand als ein Python-Programmcode. Und wie Turing herausfand, gibt es keine Turingmaschine, die für alle möglichen Konfigurationen von Turingmaschinen (also alle Algorithmen) bestimmen kann, ob sie irgendwann anhalten werden. Damit scheint dieser Ansatz bei der Lösung der goldbachschen Vermutung nicht allzu hilfreich.

Aber Vorsicht! Das Halteproblem besagt zwar, dass es keine allgemeine Möglichkeit gibt, das Halten eines Programms vorherzusagen. Über einzelne Algorithmen lassen sich jedoch durchaus solche Aussagen treffen. Zum Beispiel kann man bei einem einfachen Programmcode (etwa der Addition zweier Zahlen) sofort beurteilen, dass er halten wird. Zugegeben, bei der goldbachschen Vermutung wird das vermutlich nicht ganz so einfach. Aber es gibt einen Hoffnungsschimmer am Horizont: die bereits erwähnten fleißigen Biber.

Welcher Biber ist am fleißigsten?

Mit diesem Konzept kam der Mathematiker Tibor Radó 1962 um die Ecke. Damals suchte er nach der »fleißigsten« Turingmaschine einer bestimmten Größe: Wie viele Rechenschritte kann eine Turingmaschine mit n Zuständen, die irgendwann zum Halten kommt, maximal durchführen? Im Gegensatz zum eigentlichen Bemühen von Informatikern, die nach möglichst effizienten Algorithmen mit möglichst wenigen Rechenschritten suchen, richtete Radó seine Aufmerksamkeit gewissermaßen auf das ineffizienteste Modell.

Um die Frage allgemein zu beantworten, müsste man das Halteproblem lösen. Um den fleißigsten Biber zu finden, muss man schließlich wissen, welche Turingmaschinen halten und welche nicht. Damit ist die Fleißiger-Biber-Funktion BB(n), die die maximale Anzahl an Rechenschritten angibt, im Allgemeinen nicht berechenbar. Doch Radó gelang es, die ersten drei Werte der Funktion zu bestimmen. Und tatsächlich bringt die Kenntnis von BB(n) enorme Vorteile mit sich: Schafft man es, ein mathematisches Problem durch eine Turingmaschine mit n Zuständen zu codieren, kann man sie einfach laufen lassen. Wenn die Maschine nach BB(n) Berechnungen noch nicht gehalten hat, dann weiß man: Sie wird niemals halten.

Und tatsächlich ist es schon gelungen, die goldbachsche Vermutung durch eine Turingmaschine auszudrücken: 2016 wurde eine solche mit lediglich 27 Zuständen beschrieben. Das sind gute Nachrichten! Theoretisch kann man den Programmcode also einfach laufen lassen; falls er nach BB(27) Rechenschritten noch weiterläuft, dann wissen wir: Der Algorithmus wird für immer weiterlaufen, ohne dass jemals ein Gegenbeispiel zur goldbachschen Vermutung gefunden wird. Die Vermutung wäre demnach wahr.

Also, nichts wie los: Man muss nur noch versuchen, BB(27) zu berechnen. Dafür ist es hilfreich, zunächst einmal herauszufinden, wie viele unterschiedliche Turingmaschinen es für eine bestimmte Anzahl von n Zuständen gibt. 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.

Die ersten Werte der Fleißiger-Biber-Funktion

Betrachtet man zum Beispiel Maschinen mit nur einem Zustand, findet man bereits 64 verschiedene Turingmaschinen. Davon werden nur jene halten, 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. Nur so kommt man voran: Da es keine allgemein gültige Methode gibt, um zu untersuchen, welche Turingmaschinen irgendwann 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. Alle Zwei-Zustand-Turingmaschinen, die länger laufen, werden also niemals anhalten.

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 21 Rechenschritte durchführen. Damit wirken die ersten drei Glieder der Fleißiger-Biber-Folge nicht besonders beeindruckend: 1, 6, 21. Aber wie geht die Folge weiter?

1963 beschrieb Radó den Versuch, BB(4) zu berechnen, als hoffnungslos. 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 107. Falls eine Vier-Zustand-Turingmaschine länger läuft, dann wird sie mit Sicherheit endlos weiterlaufen. Bisher ist das der letzte Wert der Fleißiger-Biber-Funktion, der sich exakt bestimmen ließ.

Die Grenzen des Berechenbaren

Für eine Turingmaschine mit fünf Zuständen ist der fleißigste Biber noch nicht bekannt. Die Mathematiker Heiner Marxen und Jürgen Buntrock haben 1989 einen vorläufigen Champion gekürt, der 47 176 870 Berechnungen ausführt, bevor er hält. Offenbar gibt es nur noch 43 Fünf-Zustand-Turingmaschinen, von denen man nicht weiß, ob sie ewig weiterlaufen oder doch irgendwann halten. Daher ist BB(5) ≥ 47 176 870. 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. Damit sind wir noch sehr weit von einer Lösung von BB(27) entfernt – falls sie überhaupt existiert.

Selbst wenn man BB(27) theoretisch berechnen könnte, ist die Zahl höchstwahrscheinlich so groß, dass kein Computer jemals in absehbarer Zeit so viele Rechenschritte ausführen kann. Der Grund für die unvorstellbare Größe von BB(27) besteht darin, dass die Fleißiger-Biber-Folge BB(n) nachweislich schneller wächst als jede berechenbare Folge. Wenn man also eine Rechenvorschrift für eine möglichst schnell wachsende Folge angibt – möge sie noch so verrückt sein –, gibt es immer ein n, ab dem der fleißige Biber diese überholt. Damit wird die goldbachsche Vermutung auf diese Weise wohl nicht gelöst.

Erstaunlicherweise ergibt sich allerdings ein Ansatzpunkt, um die Collatz-Vermutung anzugehen. Dazu muss man sich ansehen, was die fleißigsten Biber überhaupt berechnen. Wie sich herausstellt, entsprechen die dazugehörigen Algorithmen rekursiven Funktionen, die der Collatz-Vermutung ähneln. Zum Beispiel berechnet der aktuelle Rekordhalter von BB(5) für eine Eingabe x den Wert (5x+18)/3, falls x durch drei teilbar ist; (5x+22)/3, 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. Überraschenderweise hat auch der aktuelle BB(6)-Champion eine ähnliche Form. Da beide Programme halten, bedeutet es, dass alle natürlichen Zahlen die angegebenen Funktionen nur endlich viele Male durchlaufen und stets beim selben Punkt enden. Deswegen erhoffen sich Fachleute, durch Untersuchung weiterer fleißiger Biber eine Lösung des Collatz-Problems zu finden.

Wenn wir uns aber an das Halteproblem zurückerinnern, dann wird klar: Es gibt zwangsweise Werte n, für die BB(n) nicht berechenbar ist. Damit stellt sich die Frage, was die größte Anzahl an Zuständen ist, für die man noch beurteilen kann, ob die dazugehörigen Turingmaschinen anhalten werden. Sprich: Was ist das größte n, für das man BB(n) berechnen kann? Um das herauszufinden, haben Wissenschaftler versucht, eine unentscheidbare Aussage durch eine möglichst kleine Turingmaschine zu codieren.

Sie haben eine Turingmaschine definiert, die genau dann hält, wenn das Grundgerüst der Mathematik widersprüchlich ist

Dafür kehrten sie zu den Anfängen der Logik und Gödels Arbeiten zurück. Mit seinen Unvollständigkeitssätzen hat Gödel nämlich nicht nur gezeigt, dass es zwangsweise unentscheidbare Aussagen gibt. Er hat auch bewiesen, dass ein mathematisches System niemals in der Lage ist, mit den eigens zur Verfügung gestellten Werkzeugen zu belegen, dass es niemals zu Widersprüchen führen wird. Das heißt: Die Axiome, die unsere Mathematik aufbauen, reichen nicht aus, um zu zeigen, dass sie widerspruchsfrei sind.

2016 ist es dem Informatiker Scott Aaronson gemeinsam mit seinem Doktoranden Adam Yedidia gelungen, diese Erkenntnis zu nutzen, um die Grenze der berechenbaren Fleißiger-Biber-Funktionen zu finden. Sie haben dazu eine Turingmaschine mit 7910 Zuständen definiert, die genau dann hält, wenn das Grundgerüst der Mathematik widersprüchlich ist. Da sich diese Tatsache weder beweisen noch widerlegen lässt, wird man niemals herausfinden können, ob die entsprechende Turingmaschine jemals halten wird oder nicht. Damit ist BB(7910) nicht berechenbar.

Nun stellt sich die Frage, ob es auch kleine Turingmaschinen gibt, auf die das zutrifft. Und tatsächlich wurde inzwischen eine etwa zehnmal kleinere Maschine mit bloß 748 Zuständen gefunden, die die gödelsche Unvollständigkeit enthält. Viele Fachleute gehen aber davon aus, dass BB(n) bereits für deutlich kleinere Werte von n nicht berechenbar ist. Aaronson vermutet zum Beispiel, dass schon BB(20) nicht berechenbar ist.

Wenn er damit richtigliegt, könnte auch die goldbachsche Vermutung zu den unentscheidbaren Problemen zählen. In diesem Fall würden unsere mathematischen Werkzeuge nicht ausreichen, um sie zu beweisen oder zu widerlegen. So oder so: Der Ansatz mit den fleißigen Bibern ist nicht der vielversprechendste, um die goldbachsche Vermutung zu lösen. In jüngster Zeit haben sich immer mehr Verbindungen zwischen der Zahlentheorie und anderen Bereichen der Mathematik offenbart. Vielleicht helfen diese Brücken, die so einfach erscheinenden Probleme anzugehen. Denn die fleißigen Biber sind einfach viel zu fleißig.