[theory meets practice]
Auf der Suche nach fleißigen Bibern

Michael Bertol, Holger Petersen und Horst Prote

Das ist eine Initiative von Prof. Diekert für alle, die Spaß an theoretischer Informatik haben oder sich ein bißchen mit Knobeleien unterhalten wollen.

Einführung

Hallo liebe(r) Leser(in). Seit einigen Dekaden ist die Turingmaschine ein sehr robustes Modell in der theoretischen Informatik.

Was ist eigentlich eine Turingmaschine genau? Es handelt sich dabei um einen Apparat, den Alan Turing ersann. Er wollte die Arbeitsweise eines rechnenden Menschen mathematisch beschreiben. Die Berechnung wird wie üblich auf einem Blatt Papier durchgeführt. Zur Vereinfachung kann nur eine Textzeile beschrieben werden, das Papier ist also ein Band. Und da die damaligen Zeiten sehr schlecht waren, und die Leute sparen mußten, konnte nur eine einfache Maschine finanziert werden. Sie war in der Lage, genau ein Zeichen der Bandinschrift mit einem beweglichen Lese-/Schreibkopf zu verändern. Mathematischer präzise wird sie in diesem Postscript File beschrieben.

[Mr Bussy Beaver] Der fleißige Biber

Wir schränken uns hier auf das folgende Modell ein:

T. Rado entwickelte 1961 folgendes Spiel, um Anfängern den Begriff der Turingmaschine näherzubringen: Wer an dem Busy Beaver (fleißigen Biber) Spiel teilnehmen will, schickt an ein Komitee eine Maschinenbeschreibung, eine Schrittzahl und eine Speichergrenze. Die vorgelegte Maschine wird bis zur angegebenen Anzahl der Schritte auf dem mit Nullen initialisierten Band simuliert. Wenn die Maschine in der angegebenen Schrittzahl hält, dann nimmt sie am Wettbewerb teil. Hält sie vorher, wird die Maschine zur Korrektur zurückgegeben. Hält sie nicht, dann wird sie disqualifiziert.

Gewinnerin ist diejenige Maschine, die nach dem Halten die meisten Einsen auf ihrem Band hat.

Das Ziel ist also, zu einer natürlichen Zahl n eine binäre Turingmaschine zu finden, die möglichst viele (maximal viele!) Einsen auf ein mit Nullen initialisiertes Band schreibt und danach hält.

Beschreibung des Simulators

Da es recht stupide ist, Berechnungen von Hand (oder zu Fuß) nachzuvollziehen, haben wir weder Mühen noch Kosten gescheut, diesem Rechner auch das Turingmaschinenmodell nahezubringen. Lediglich die Turingtafel muß ihm noch mitgeteilt werden, was durch ein paar Mouseclicks geschieht.

Dazu wählt man ein Tripel bestehend aus einem Zustand, einem Bandsymbol (0,1) und einer Aktion (left, right, halt) mit den drei oberen Menüs in der rechten Hälfte der Simulatorseite aus. In der linken Tabelle kann danach dieses Tripel in die Tafel durch Anklicken der entsprechenden Position eingefügt werden. (Einige vielversprechende Bibermaschinen sind bereits vordefiniert.)

Ist die Tafel definiert, so kann eine Simulation gestartet werden. Um unendliche Rechnungen zu vermeiden, muß zuvor eine obere Grenze für die Schrittzahl festgelegt werden. (Vorsicht, bei zu großzügiger Wahl wird viel RAM requiriert.)

Das Band kann auch mit einer Anzahl Einsen initialisiert werden. Der Kopf der Maschine befindet sich dann beim Start der Simulation auf der ersten Eins. Aber das sind ja dann sowieso keine echten Biber ...

Der Start selbst erfolgt durch den Kontrollbutton neben dem Label ``Simulation Mode''. Je nach Leistung des benutzten Rechners reagiert der Simulator schnell oder etwas träger. Leider hilft da mehrmaliges Klicken auch nicht, sondern löst nur neue, Rechenzeit beanspruchende Events aus. Also Geduld. Man kann die Zeit nutzen, um zum Beispiel eine Tasse Java zu trinken.

Das Ergebnis kann dann in vier Textfeldern abgelesen werden. Beispielsweise terminiert die BB-Maschine(3) nach 11 Schritten, hat während der Berechnung 6 Felder des Bandes beschriftet, hält mit 6 Einsen, die alle in einem Block stehen (d.h. es befindet sich keine Null zwischen zwei Einsen). Im Gegensatz dazu hält die BB-Maschine(4) nach 96 Schritten mit 13 Einsen, hat aber 14 Felder beschrieben und die Ausgabe besteht aus zwei Einserblöcken, die durch eine Null getrennt sind.

Der Simulator

Forschen, ............. und andere Interessierte (Interessante)

Wenn jemand an dem Problem Freude fand und eventuell sogar eine vielversprechende Bibermaschine gefunden hat, kann sie oder er sie uns gerne zuschicken, anrufen oder vorbeikommen. Wir freuen uns über jeden Kommentar.

Email: diekert@informatik.uni-stuttgart.de
Email: bertol@informatik.uni-stuttgart.de
Email: petersen@informatik.uni-stuttgart.de

Weitere Referenzen ...

Ein einfacher Simulator von Dirk Farin und ein Simulator von Keneth's Team (Buena Vista University), der Java Cup Gwinner in der Sparte Education.

Literatur

Noch ein paar Weisheiten zum Schluß: