Fleißige Biber

Biber-Turingmaschinen

Eine Biber-Turingmaschine ist eine (einfache) Turingmaschine, die in jedem Arbeitsschritt genau eine "Baumaktion" durchführt (Baumstamm hinlegen oder wegnehmen) und einen Schritt nach rechts oder links geht. Ein Baum wird hier im Turing-Kara-Simulator mit einem Pfeil nach oben dargestellt.

Eine Biber-Turingmaschine startet in einer "leeren Welt" (leeres Band), "sammelt Baumstämme“ und hält nach endlich vielen Arbeitsschritten.

Die folgende Biber-Turingmaschine mit 2 Zuständen (außer dem Stop-Zustand zS) sammelt genau 2 Baumstämme, bevor sie hält. Beachte, dass ein Baum hier mit "I" beschrieben wird. Dieses Symbol entspricht also dem Pfeil im Simulationsprogramm.

z0 B z1 I R; 
z0 I zS I R;
z1 B z0 I L;
z1 I z0 I L;

Aufgabe 1: Biber-Turingmaschinen-Wettbewerb

Gesucht ist eine Biber-Turingmaschine mit genau 2 Zuständen (außer dem Stop-Zustand), die möglichst viele Baumstämme sammelt, bevor sie hält. Eine solche Turingmschine heißt „fleißiger Biber“ (mit 2 Zuständen) bzw. „busy beaver turing machine“.

Aufgabe 2: Biber-Turingmaschinen-Wettbewerb

Wer schafft die meisten Baumstämme? Gesucht ist eine Biber-Turingmaschine mit genau 3 bzw. 4 Zuständen (außer dem Stop-Zustand), die möglichst viele Baumstämme sammelt, bevor sie hält.

Rado´sche Funktion

Im Jahr 1962 hat der ungarische Mathematiker Tibor Rado ein bemerkenswerte Funktion definiert. Die Funktion Σ: N -> N ordnet jeder natürlichen Zahl n ∈ N nach der folgenden Berechnungsvorschrift eine natürliche Zahl zu:

Σ(n) beschreibt die maximale Anzahl von Baumstämmen, die eine Biber-Turingmaschine mit genau n Zuständen (außer dem Stop-Zustand) ausgehend von einem leeren Band sammeln kann.

Die folgende Tabelle zeigt einige Funktionswerte der Rado-Funktion.

n	Σ(n)
0	0
1	1
2	4
3	6
4	13
5	?
6	?
...	...

Aufgabe 3: Biber-Turingmaschinen-Wettberwerb

(a) Hast du mit einer Biber-Turingmaschine mit 3 Zuständen 6 Baustämme geschafft? Wenn nicht, dann teste die folgende Biber-Turingmschine: biber_z3.kara.

(b) Hast du mit einer Biber-Turingmaschine mit 4 Zuständen 13 Baustämme geschafft? Wenn nicht, dann teste die folgende Biber-Turingmschine: biber_z4.kara.

Aufgabe 4: Funktionswerte der Rado-Funktion

(a) Schätze erst einmal, wie groß die Funktionswerte Σ(5) und Σ(6) sind.

(b) Recherchiere anschließend, wie groß die Funktionswerte Σ(5) und Σ(6) sind. Wie gut waren deine Schätzungen?

Berechenbarkeit der Rado´sche Funktion

Die Rado-Funktion ist eine sehr schnell wachsende Funktion. Man kann zeigen, dass sie schneller wächst als jede (mit einer Turingmaschine) berechenbare Funktion. Wir verzichten hier auf diesen Nachweis und formulieren nur das Ergebnis.

Obwohl es sehr viele nicht-berechenbare Funktionen gibt - sogar mehr als berechenbare -, muss man sich doch Außergewöhnliches einfallen lassen, um eine nicht-berechenbare Funktionen möglichst konkret zu beschreiben. Rado hat das mit der nach ihm benannten Σ-Funktion geschafft.

Dass man die Funktionswerte der Σ-Funktion nicht so einfach berechnen kann, liegt nach dem oben angegebenen Satz an der Nicht-Berechenbarkeit der Funktion. Es gibt (nach der Church-Turing-These) kein algorithmisches Verfahren, mit dem man alle Funktionswerte der Σ-Funktion berechnen kann. Diese Tatsache schließt aber nicht aus, dass man einzelne Funktionswerte der Σ-Funktion bestimmen kann. Im Fall n = 2 kann man beispielsweise alle Turingmaschinen mit 2 Zuständen (außer dem Stop-Zustand) erzeugen und jede dieser endlichen vielen Turingmaschinen unsersuchen, ob sie hält und wie viele Baumstämme sie in diesem Fall erzeugt.

Aufgabe 5: Berechenbarkeit der Rado-Funktion

Philipp schlägt das folgende Verfahren zur Berechnung von Σ(n) vor:

In einem ersten Schritt werden alle Turingmschinen mit n Zuständen erzeugt. In einem zweiten Schritt werden alle Turingmschinen bestimmt, die ausgehend von einem leeren Band halten. In einem dritten Schritt werden diese haltenden Turingmaschinen der Reihe nach gestartet. Es wird dabei mitprotokolliert, wie viele Baustämme sie erzeugen. In einem vierten Schritt wird dann aus dem Ergebnisprotokoll der fleißige Biber bestimmt.

Bewerte dieses Verfahren.