Fleißiger Biber

Grundidee und Definition

Ein fleißiger Biber (englisch busy beaver) ist eine besondere Turingmaschine, die auf einem vollständig mit Nullen gefüllten Band arbeitet, möglichst viele Einsen schreibt und nach endlich vielen Rechenschritten anhält. Das Konzept und die zugehörige Funktion wurden 1962 von Tibor Radó betrachtet. In der theoretischen Informatik sind sie wichtige Beispiele dafür, dass eine Funktion eindeutig definiert sein kann, ohne allgemein berechenbar zu sein.

Ein fleißiger Biber besitzt n Arbeitszustände und zusätzlich einen Halt-Zustand. Sein Bandalphabet ist {0,1}. Bei jedem Schritt liest die Maschine ein Symbol, schreibt 0 oder 1, bewegt ihren Lese- und Schreibkopf genau ein Feld nach links oder rechts und wechselt in einen neuen Zustand. Das Verharren auf einem Feld ist nicht erlaubt. Die Maschine muss schließlich den Halt-Zustand erreichen; Maschinen mit Endlosschleifen zählen nicht.

Unter allen nach diesen Regeln arbeitenden und haltenden Maschinen mit n Zuständen ist ein fleißiger Biber eine Maschine, die die maximale Anzahl k_n von Einsen hinterlässt. Nicht haltende Maschinen könnten zwar noch mehr Einsen schreiben, erfüllen aber die Definition nicht.

Funktionen und Zusammenhänge

Die Fleißiger-Biber-Funktion oder Radó-Funktion gibt die größtmögliche Zahl geschriebener Einsen an:

Σ(n) = k_n.

Radó definierte außerdem S(n) als die maximale Schrittzahl einer haltenden Turingmaschine mit zweielementigem Alphabet und n Zuständen. Da in jedem Schritt höchstens eine Eins geschrieben werden kann, gilt S(n) ≥ Σ(n). Außerdem besteht die Beziehung S(n) < Σ(3n+6). Auch S ist nicht berechenbar: Könnte man S(n) bestimmen, ließe sich nach spätestens S(n) Schritten entscheiden, ob eine Maschine mit n Zuständen noch anhalten kann. Damit wäre das Halteproblem für ein leeres Eingabeband entscheidbar.

Die ebenfalls nicht berechenbare Funktion σ(n) entsteht durch die zusätzliche Forderung, dass alle geschriebenen Einsen eine zusammenhängende Kette bilden müssen.

C. Dunham definierte 1965 die Variante D(n): Sie bezeichnet die maximale Anzahl Einsen, die eine haltende Maschine mit zweielementigem Alphabet und n Zuständen erzeugt, wenn sie auf einem Band mit einem Anfangsblock aus n Einsen startet. D ist nicht berechenbar. Andernfalls könnte eine Maschine M mit m Zuständen die Funktion n ↦ D(n)+1 berechnen. Für n=m ergäbe sich der Widerspruch D(m)+1 = M(m) ≤ D(m).

Warum das Problem nicht allgemein lösbar ist

Es gibt keinen Algorithmus, der für jede Zustandszahl n die fleißigen Biber beziehungsweise Σ(n) bestimmt. Insbesondere lässt sich nicht allgemein entscheiden, ob eine gegebene Maschine anhält und dabei tatsächlich die größtmögliche Anzahl von Einsen schreibt. Für einzelne, hinreichend einfache Maschinen kann ein solcher Nachweis dennoch gelingen.

Die Wertemenge von Σ(n) ist weder entscheidbar noch rekursiv aufzählbar. Auch ihr Komplement ist nicht rekursiv aufzählbar. Deshalb dient sie als Beispiel für eine Sprache, die nicht in der ersten Stufe der arithmetischen Hierarchie liegt. Die Funktion Σ selbst ist nicht berechenbar; ihr asymptotisches Wachstum ist stärker als das jeder berechenbaren Funktion.

Praktische Suche und bekannte Werte

Die praktische Schwierigkeit wächst außerordentlich schnell. Bei n Zuständen und einem zusätzlichen Halt-Zustand gibt es für ein Alphabet aus zwei Zeichen

(2·2·(n+1))^(2n)

verschiedene Maschinen. Für jede Kombination aus Zustand und gelesenem Symbol müssen das zu schreibende Symbol, die Bewegungsrichtung und der nächste der n+1 möglichen Zustände festgelegt werden. Bereits bei n=5 sind 24^10 Maschinen zu berücksichtigen. Für jede einzelne müsste man ihre Haltezeit ermitteln oder beweisen, dass sie niemals anhält. Für n>5 scheint eine vollständige Bestimmung von Σ(n) praktisch nicht mehr realistisch. Bei n=6 ist die bekannte Untergrenze der Schrittzahl bereits weit größer als die Zahl der Atome im beobachtbaren Universum; für Nachweise treten zudem Collatz-ähnliche Probleme auf.

Gesicherte Werte sind:

• n=1: Σ(1)=1 und S(1)=1, bestimmt 1962 von Radó.
• n=2: Σ(2)=4 und S(2)=6, bestimmt 1962 von Radó.
• n=3: Σ(3)=6 und S(3)=21, bestimmt 1965 von Lin und Radó.
• n=4: Σ(4)=13 und S(4)=107, angegeben 1972 von Weimann, Casper und Fenzel.
• n=5: Σ(5)=4098 und S(5)=47 176 870; der Wert wurde 2024 durch internationale Zusammenarbeit bestätigt.

Bei einem Wettbewerb der Gesellschaft für Informatik Anfang 1983 an der Universität Dortmund, heute TU Dortmund, wurden 133 eingesandte Programme auf einem Siemens-7.748-Computer geprüft. Die von Uwe Schult eingesandte Sieger-Maschine schrieb 501 Einsen und benötigte 134 467 Schritte. Georgi Georgiev berichtete 2003, dass sich für n=5 knapp über 40 Maschinen mit seinen Methoden nicht abschließend auf ihr Halteverhalten untersuchen ließen; unter den als haltend erkannten schrieb keine mehr als 4098 Einsen.

Ab 2022 untersuchte The Busy Beaver Challenge die verbleibenden irregulären Maschinen für n=5. Schließlich stellte mxdys einen algorithmischen Beweis in Rocq zusammen. Damit wurde der bereits 1989 von Jürgen Buntrock und Heiner Marxen gefundene Rekordhalter endgültig bestätigt.

Für größere Maschinen nennt der Artikel nur Untergrenzen: Für n=6 gilt 2025 eine Grenze von mehr als 2↑↑↑5, verbunden mit mxdys; für n=7 eine Grenze von mehr als 2↑^11 2↑^11 3, verbunden mit Pavel Kropitz. Die Pfeile bezeichnen die Pfeilschreibweise für extrem große Zahlen.

Beispiele kleiner Maschinen

Der fleißige Biber mit einem Zustand startet in q₀ auf einer Null. Er schreibt eine Eins und geht unmittelbar in den Halt-Zustand q_f. Damit erreicht er nach einem Schritt den Bandinhalt 10 und die Werte Σ(1)=1 sowie S(1)=1. Die Überführung für den gelesenen Wert 1 muss nicht definiert werden, weil dieser Fall während des Ablaufs nie eintritt.

Die angegebene Maschine mit zwei Zuständen q₀ und q₁ schreibt insgesamt vier Einsen und hält nach sechs Schritten. Ihr relevanter Bandabschnitt lautet am Ende …0111100…. Damit erreicht sie Σ(2)=4 und S(2)=6.

Die Beispielmaschine mit drei Zuständen q₀, q₁ und q₂ hält nach 14 Schritten mit sechs Einsen, dargestellt als Bandinhalt 111111. Der bekannte Maximalwert der Schrittzahl beträgt jedoch S(3)=21; eine Maschine, die die meisten Einsen schreibt, muss also nicht zugleich die größtmögliche Zahl von Schritten ausführen.

Die angegebene Maschine mit vier Zuständen erreicht nach 107 Schritten den Halt-Zustand. Ihr Band enthält dann „…10111111111111…“, also insgesamt 13 Einsen. Sie erreicht damit sowohl Σ(4)=13 als auch S(4)=107.

Für fünf Zustände gibt der Artikel außerdem die vollständige Überführungsfunktion des später bestätigten Rekordtyps mit den Arbeitszuständen q₀ bis q₄ und dem Halt-Zustand q_f an. Seine komplexe Folge von Schreib-, Bewegungs- und Zustandswechseln führt zum Rekord von 4098 Einsen nach 47 176 870 Schritten.