Fleißige Biber

Hinweis: Die hier angegebenen Turingmaschinen sind in der Folge Zustand, gelesenes Zeichen -> zu schreibendes Zeichen, Kopfbewegung, Folgezustand angegeben. Die Programme können im Programm P_automat getestet werden; daher ist der Anfangszustand mit A und die Bewegung Halt über den Endzustand E realisiert.

Definition

Definition: Fleißige Biber
Als fleißige Biber mit n Zuständen werden Turingmaschinen mit n Zuständen genannt, die angesetzt auf das leere Band halten eine maximale Anzahl von Strichen schreiben.

Die Idee zu diesem Fleißige-Biber-Spiel stammt von Tibor Rado (1962). Nach ihm wurde dann auch die bb(n)-Funktion (bb – busy beaver) als Rado-Funktion benannt.

„Kleine“ fleißige Biber

Ein fleißiger Biber mit nur einem Zustand kann höchstens einen Strich auf das leere Band drucken. z B. erledigt dies das folgende Programm:

A * -> I L E
A I -> I L E

Im Fall n = 2 (zwei Zustände) schreibt die Maschine

A * -> I R 2
A I -> I L E
2 * -> I L 2
2 I -> I L A

drei konsekutive (aufeinander folgende) Striche auf das leere Band; es werden 6 Schritte benötigt.

Die Maschine

A * -> I R 2
A I -> I L 3
2 * -> I R 3
2 I -> I R E
3 * -> I L A
3 I -> * L 2

mit drei Zuständen schreibt 6 konsekutive Striche auf das Band.

Für n = 4 ist die Maschine

A * -> I L 2
A I -> * L 3
2 * -> I R A
2 I -> I L A
3 * -> * L E
3 I -> I L 4
4 * -> I R 4
4 I -> * R 2

konstruierbar, die 12 konsekutive Striche (in 96 Schritten) produziert. Wird die Anweisung 3 * -> * L H in 3 * -> I L H abgeändert, so erhält man die Bandinschrift

...***I*IIIIIIIIIIII***...

, also 13 Striche.

Fleißige Biber mit fünf Zuständen

1983 fand an der Universität Dortmund ein Wettbewerb zur Jagd auf fleißige Biber statt. Für den Fall n = 5 gewann Uwe Schult mit seinem Castor diligentissimus,

A * -> I R 2
A I -> * L 3
2 * -> I R 3
2 I -> I R 4
3 * -> I L A
3 I -> * R 2
4 * -> * R 5
4 I -> I L E
5 * -> I L 3
5 I -> I R A

der 501 Striche produziert und dafür 134.467 Schritte benötigt. Ist dies der fleißigste Biber mit fünf Zuständen? Wohl nicht, denn mittlerweile gibt es die Maschine

A * -> I R 2
A I -> I L 2
2 * -> * L 1
2 I -> * L 4
3 * -> I L 1
3 I -> I L E
4 * -> I L 2
4 I -> I R 5
5 * -> * R 4
5 I -> * R 2

von Georg Uhing, die 1.915 Striche erzeugt und dafür 2.133.492 Schritte benötigt. Aber auch dies ist (definitiv) noch nicht das Maximum; 1989 fanden Heiner Marxen und Jürgen Buntrock einen noch fleißigeren Biber

A * -> I R 2
A I -> I R A
2 * -> I L 3
2 I -> I L 2
3 * -> I R A
3 I -> I L 4
4 * -> I R A
4 I -> I L 5
5 * -> I L E
5 I -> * L 3

der 4.098 Striche schreibt und 11.798.826 Schritte dafür benötigt. Ist damit das Maximum erreicht?

Weshalb werden fleißige Biber gesucht?

Die oben schon angesprochene Rado-Funktion bb(n) besitzt als Funktionswert die Maximalzahl der geschriebenen Striche eines fleißigen Bibers mit n Zuständen, d. h. wir wissen bb(1)=1, bb(2)=4, bb(3)=6 und bb(4)=13. Für bb(5) ist derzeit nur die Aussage >=4096 möglich.

Weshalb ist dieser Wert (noch nicht) genau bestimmbar?

Die Rado-Funktion bb(n) hat eine fatale Eigenschaft: sie ist nicht berechenbar. Nach den ersten 4 Werten 1, 4, 6, 13 ist dies kaum zu vermuten. Und selbst, wenn bb(5)= 4098 sein sollte, schein das Wachstum nicht stärker zu sein, als das einer Exponentialfunktion. Allerdings: Für den Fall n=8 wurde für den Funktionswert bereits eine untere Schranke von 10⁴³ ermittelt.

Schauen wir uns die Rado-Funktion etwas genauer an. Zunächst einmal wird diese Funktion mathematisch wohl definiert sein, d. h. es existiert zu jedem n ein Funktionswert bb(n). Zunächst einmal gibt es zu jeder natürlichen Zahl n nur endlich viele Turingmaschinen mit n Zuständen. Von diesen halten damit auch nur endlich viele, wenn sie auf einem leeren Band starten. Die von diesen Maschinen erzeugten Strichzahlen bilden eine endlichen Menge natürlicher Zahlen … und eine solche Mengen besitzt ein Maximum. Damit ist zu jedem n die Existenz von bb(n) begründet.

Ein Algorithmus zur Berechnung von bb(n) ist ganz leicht anzugeben:

Einlesen von n
Notiere alle (endlich viele) Turingmaschinen mit n Zuständen
Sortiere alle nicht haltenden Maschinen aus
Starte alle Maschinen und notiere die erzeugten Strichzahlen
Ermittle das Maximum aller Strichzahlen

Dies hört sich einfach durchführbar an, ist es aber nicht. Das Problem liegt in dem dritten Schritt. Für einige der Turingmaschinen lässt sich sehr leicht feststellen, dass sie nicht anhalten; für andere Turingmaschinen lässt sich jedoch nicht entscheiden, ob sie jemals anhalten. Bei einer solchen Turingmaschine bleibt letztlich nichts anderes übrig, als abzuwarten, ob sie irgendwann anhält und welchen Wert sie liefert. Da sie jedoch möglicherweise nie stehenbleibt, lässt sich nicht garantieren, dass die Berechnung von bb(n) auf diesem Wege zu einem Ende kommt (Halteproblem).

Definition: Satz von Rado
Die bb(n)-Funktion ist algorithmisch nicht berechenbar.

Das heißt: Es gibt kein allgemeines Verfahren (keinen Algorithmus, kein Computerprogramm, …), mit dem an den Wert von bb(n) für natürliche Zahlen ausrechnen kann. Gemäß der Turingthese heißt dies, dass es keine Turingmaschine gibt, der wir die Zahl n etwa in unärer Darstellung auf das Band schreiben, und die dann den Funktionswert bb(n) ermittelt und ihn ebenfalls in unärer Darstellung auf das Band schreibt.

Weitere fleißige und weniger fleißige Biber

Die Suche nach besseren fleißigen Bibern geht natürlich trotzdem weiter. Bekannt ist z. B. der folgende fleißige Biber mit 6 Zuständen, der 95.524.079 Striche erzeugt und dabei 8.690.333.381.690.951 Schritte benötigt:

A * -> I R 2
A I -> I R A
2 1 -> I L 2
2 * -> I L 3
3 I -> I L 4
3 * -> * R 6
4 I -> * L 5
4 * -> I R A
5 I -> I L 6
5 * -> I L E
6 I -> * L 3
6 * -> * L A

Bei der Suche nach fleißigen Bibern gehen auch andere „weniger fleißige“ – dafür genauso schöne – Biber in die Falle. Bei dem oben angesprochenen Wettbewerb an der Universität Dortmund fand Jochen Ludewig einige Biber, die sich alle dadurch auszeichnen, dass sie beim Halten ein absolut leeres Band hinterlassen. Castor ministerialis, der Ministerialbeamtenbiber, versucht, ohne etwas zu leisten, so weit wie möglich voranzukommen. Castor scientificus, der Wissenschaftlerbiber, unterscheidet sich von dem ersten nur dadurch, dass er einen noch großeren Aufwand treibt, um nichts zu erreichen. Castor exflippus, der Aussteigerbiber, schafft es, reumütig auf sein Ausgangsfeld zurückzukehren.

Castor ministerialis   Castor scientificus    Castor exflippus
A * -> I R 2           A * -> * R 2           A * -> * R 2
A I -> I R A           A I -> * L A           A I -> * L A
2 * -> I R 3           2 * -> * R 3           2 * -> I R 3
2 I -> * R 5           2 I -> * N E           2 I -> * N E
3 * -> I L 4           3 * -> I R 4           3 * -> * L 3
3 I -> * R 1           3 I -> I L 5           3 I -> I R 4
4 * -> I L 2           4 * -> I L 1           4 * -> * L 4
4 I -> I L 4           4 I -> * L 4           4 I -> I R 5
5 * -> * N E           5 * -> I R 3           5 * -> I L 1
5 I -> * R 2           5 I -> I R 5           5 I -> * L 5