 |
Turing-Maschinen, die entlang ihres Bandes hin- und
herlaufen, hier ein Symbol unverändert lesen und dort ein Symbol schreiben,
könnten uns an fleißige Biber erinnern, die den Fluss zwischen Damm und Wald
fleißig durchqueren und bei jeder Tour ein Stöckchen (eine 1) für die
Konstruktion ihres Dammes heranschaffen. Wie fleißig kann nun eine
Turing-Maschine sein? Wie viele Stöckchen können sie legen? Dabei ist aber
zu bedenken, dass eine Turing-Maschine anhalten
muss. Eine Maschine zu entwerfen, die unendlich viele 1en auf ein Band
schreibt, ist nicht schwer. Wie ist es aber, wenn die Maschine nur möglichst
viele Einsen schreiben soll und irgendwann anhalten soll?
TIBOR RADO, ein ungarischer Mathematiker, dachte sich das aus, was heute als
Busy-beaver-Problem bezeichnet wird: Gegeben sei eine Turing-Maschine mit n
Zuständen und einem zweielementigen Alphabet bestehend aus 0 und 1. Was ist
nun die maximale Anzahl an Einsen, die eine solche Turing-Maschine auf das
Band schreiben kann? |
 |
www.oberstufeninformatik.de/theorie/ Der augenblickliche
Wissensstand (2002) sieht so aus:
Anzahl der Zustände maximale Anzahl der 1en
1 1
2 4
3 6
4 13
5 4098
1984 erschien in Scientific American ein Artikel über den damals fleißigsten
bekannten 5-Zustands-Biber von UWE SCHULT, einem deutschen Informatiker.
Sein Biber konnte 501 Einsen vor dem Anhalten erzeugen. Als Antwort auf den
Artikel führte GEORGE UHING, ein amerikanischer Programmierer, eine
Computersuche nach fleißigen Bibern mit 5 Zuständen durch und fand einen,
der 1915 Einsen produzieren konnte. 1989 führten JÜRGEN BUNTROCK und HEINER
MARXEN in Deutschland auf einem Hochgeschwindigkeitsrechner in Deutschland
ein Programm zur Suche ein, dass nach drei Tagen einen Biber mit 4096 Einsen
fand. Hier ist seine Turing-Tabelle:
Gelesenes Zeichen 0 1
Zustand Schreibe Neuer Nach Schreibe Neuer Nach
Zustand Zustand
Z1 1 Z2 L 1 Z1 L
Z2 1 Z3 R 1 Z2 R
Z3 1 Z1 L 1 Z4 R
Z4 1 Z1 L 1 Z5 R
Z5 1 S R 0 Z3 R
S (Stopp)
Es ist natürlich berechtigt, zu fragen, was „dieser Quatsch“ soll, mit dem
sich Informatiker mit „viel Freizeit“ beschäftigen. Ich kann mich selbst
daran erinnern, dass zu der Zeit, als ich in die Informatik Anfang der 80er
Jahre einstieg, in diversen Computerzeitschriften Busy-Beaver-Kolumnen
existierten, was ich damals überhaupt nicht verstehen konnte und wollte.
Warum ist dieses Problem nun so berühmt geworden? Die Antwort ist kurz und
ernüchternd: Das Busy-beaver-Problemist mit einer Turing-Maschine nicht
berechenbar und damit überhaupt nicht berechenbar.
Kein Computer kann jemals herausfinden, wieviel Stöckchen ein fleißiger
Biber mit einer bestimmten Anzahl von Zuständen maximal legen kann. Die
Informatik hat also ihre Grenzen und damit muss man sich leider abfinden.
Der Beweis des Satzes sei auf das Informatik-Studium verschoben. |
