Die Jagd nach den emsigen Bibern Home -> Themen -> Emsige Biber
Die Jagd nach den emsigen Bibern
Der Wettbewerb Die Ergebnisse Probleme bei der Suche Die emsigen Biber im Informatikunterricht
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.
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.
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.
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.
