Fleißige Biber sind Turingmaschinen, die möglichst viele Einsen auf das Band schreiben ohne in eine Endlosschleife zu geraten (d.h. die nach einer endlichen Anzahl Rechenschritte halten). Die Radó-Funktion (auch Fleißiger-Biber-Funktion) gibt die Anzahl der Einsen an, welche ein fleißiger Biber mit einer gegebenen Anzahl Zustände schreibt. Beides wurde erstmals 1962 vom ungarischen Mathematiker Tibor Radó betrachtet.

Formelle Betrachtung

---

Definition

Ein Fleißiger Biber ist eine Turingmaschine mit dem zweielementigen Alphabet $\backslash \{0,\; 1\backslash \}$ und $n$ Zuständen, die auf ein leeres (aus Nullen bestehendes) Band eine maximale Anzahl $k\_n$ von Einsen schreibt und dann hält. Keine Turingmaschine mit gleicher Anzahl Zuständen und gleichem Alphabet kann also bei dieser Startkonfiguration mit mehr Einsen als ein fleißiger Biber auf dem Band halten.

Fleißiger-Biber-Funktion

Über die Anzahl $k\_n$ von Einsen, die ein fleißiger Biber mit n Zuständen schreibt, definiert man den Wert der Fleißiger-Biber-Funktion (auch Radó-Funktion) an der Stelle n: $\backslash Sigma(n)\; =\; k\_n$.

Unlösbares Problem

Der fleißige Biber führt zu einem Problem, das nicht lösbar ist: So ist nicht allgemein entscheidbar, ob eine gegebene Turingmaschine mit $n$ Zuständen tatsächlich eine Kette von Einsen maximaler Länge schreibt (siehe Entscheidbarkeit, für einzelne Turingmaschinen geringer Komplexität ist das allerdings möglich.) Also ist die Menge der Werte von $\backslash Sigma(n)$ weder entscheidbar, noch rekursiv aufzählbar, obwohl $\backslash Sigma(n)$ wohldefiniert ist. Da auch das Komplement dieser Menge nicht rekursiv aufzählbar ist, wird diese Menge gerne als Beispiel für eine Sprache gewählt, die nicht in der ersten Stufe der arithmetischen Hierarchie liegt.

Wegen dieser Eigenschaften der Wertemenge ist die Funktion $\backslash Sigma$ nicht berechenbar. Man kann außerdem zeigen, dass ihr asymptotisches Wachstum stärker ist als das jeder berechenbaren Funktion.

Praktische Betrachtung

---

In der Praxis hat sich gezeigt, dass schon für $n\; >\; 5$ eine Erkenntnis über den Wert $\backslash Sigma(n)$ realistisch gesehen nicht mehr möglich zu sein scheint. Dazu müsste man für jede einzelne Turingmaschine mit n Zuständen jeweils herausfinden, nach wievielen Schritten sie hält, oder anderenfalls beweisen, dass sie das nicht tut. Aus Gödels Unvollständigkeitssatz folgt direkt, dass nicht für alle solche Turingmaschinen ein entsprechender Beweis existiert. Ob bereits für $n\; =\; 5$ eine solche zwingende Erkenntnislücke naheliegt ist bislang nicht bekannt. Durch die Untersuchung bestimmter Eigenschaften konnten inzwischen zumindest bereits bis auf 40 Maschinen, die kein reguläres Verhalten zeigen, eine Unterteilung in haltende Maschinen, die höchstens 4098 Einsen schreiben und nicht haltenden Maschinen unternommen werden.

>= 1915 (1984, George Uhing)
>= 4098 (1989, Jürgen Buntrock und Heiner Marxen)

Zustände n	$\backslash Sigma(n)$
1	1
2	4
3	6
4	13
5	>= 501 (1984, Uwe Schult)
6	> 1,29×10865
7	Abschätzung unrealistisch

Ebenfalls nicht berechenbare Funktion

---

Eine ebenfalls nicht berechenbare Funktion ergibt sich, wenn man die zusätzliche Beschränkung einführt, dass alle Einsen eine zusammenhängende Kette bilden müssen.

Tmb.gif

Als Bezeichnung dafür hat sich $\backslash sigma(n)$ eingebürgert.

Weblinks

---

• Weitere Informationen
• Seite von Heiner Marxen
• Prinzipielle Grenzen der Berechenbarkeit
• Eine Einführung der Uni Stuttgart

Literatur

---

• A. K. Dewdney: The new Turing Omnibus—66 Excursions in Computer Science (1993, überarbeitet 1996). Computer Science Press, New York.
• Heiner Marxen und Jürgen Buntrock: Attacking the Busy Beaver 5. Bulletin of the EATCS 40 (Februar 1990), S. 247–251. .

Theoretische Informatik | Rekursionstheorie

Busy beaver | Busy Beaver