Home -> Themen -> Emsige Biber


Turing-Werkstatt

Theoretische Informatik am PC


O.Pletsch 1862 Die Jagd nach den emsigen Bibern

Der Wettbewerb
1982 startete der Fachbereich Informatik der Uni Dortmund einen vielbeachteten Wettbewerb. Gesucht wurden emsige Biber, genauer gesagt Turing-Maschinen mit einem Band, 5 Zuständen und mit dem Arbeitsalphabet {' ','I'} die nach dem Start auf dem leeren Band möglichst viele Striche produzieren bevor sie stoppen. Der Schreib/Lese-Kopf darf nur die Bewegungen R,L und S ausführen (Einladung der Uni Dortmund). Als Orientierung war die Tafel einer Turing-Maschine, biber4.tm, mit 4 Zuständen angegeben, die die Maximalzahl von 13 Strichen erzielt. Ebenso bekannt sind die besten Maschinen mit 2 und 3 Zuständen biber2.tm, biber3.tm.

Die Ergebnisse
In der Novemberausgabe der Zeitschrift Spektrum der Wissenschaft von 1984 wurde der Wettbewerb und die Ergebnisse ausführlich dargestellt. 133 Maschinen waren eingereicht worden von . Die Siegermaschine Schult.tm von Uwe Schult brachte es auf 501 Striche. Nach Ende des Wettbewerbs ist die Suche weitergegangen. Eine Maschine uhing.tm von G.Uhing bringt es auf 1915 Striche, die Maschine buntmarx.tm von Heiner Marxen und Jürgen Buntrock auf 4098 Striche.
Offizieller Bericht der Abteilung der Informatik der Universität Dortmund :
Ludewig,J., Schult,U., Wankmüller,F. : Chasing the BUSY-Beaver-Notes and Observations to find the 5-state Busy-Beaver.

Probleme bei der Suche
Die erste Schwierigkeit ist die große Anzahl von zu untersuchenden Maschinen. Die Berechnung der Anzahl ist eine einfache Übung der Kombinatorik.
Eine zweite noch größere Schwierigkeit besteht darin, dass man einer Maschine nicht so einfach ansehen kann, ob sie anhalten wird nach einem Start auf dem leeren Band. Einfach wäre die Suche, wenn man einen Algorithmus hätte, der für jede zu prüfende Turing-Maschine entscheidet, ob sie anhalten wird. Man spricht vom speziellen Halteproblem für Turing-Maschinen, d.h. in anderen Worten : Ist die Menge der Turing-Maschinen entscheidbar, die nach einem Start auf dem leeren Band anhalten? Wäre das Halteproblem entscheidbar, so könnte man alle nicht haltenden Maschinen aussondern und nur die restlichen Maschinen starten ohne Gefahr einer Endlosschleife. Nach dem Stopp kann für jede dieser Maschinen die Anzahl der Striche ermittelt werden.

Die emsigen Biber im Informatikunterricht
Der Biber-Wettbewerb eignet sich hervorragend als Einstieg in eine Unterrichtsreihe über die Grenzen des algorithmisch Machbaren. Aus der Perspektive eines Teilnehmers am Wettbewerb wird man zwangsläufig auf Halteprobleme bei Turing-Maschinen geführt und zur Betrachtung der Radoschen Sigma-Funktion. Mit dem Nachweis, dass die Sigma-Funktion nicht berechenbar ist, hat man zugleich das Halteproblem für Turingmaschinen als nicht entscheidbar nachgewiesen.