Zur MathePrisma-Startseite
Zur Modul-Startseite  


Turingmaschine (Abspann 1)
 

 
 

 
Im Jahre 1962 stellte der ungarische Mathematiker Tibor Rado das Fleißige-Biber-Problem vor.
 
Die Busy- Beaver- Funktion
 
Die Fleißige-Biber-Funktion

    ordnet einer Anzahl von Zuständen die maximale Anzahl von Einsen zu, die eine Turingmaschine mit dieser Anzahl von Zuständen auf das leere Band schreiben kann.

Beachte: Die Turingmaschine muss irgendwann stoppen!
 











Ein fleißiger Biber












Die Jagd auf Biber hält an








Viel Glück bei der Suche
 
Rado konnte beweisen, dass diese Funktion nicht berechenbar ist. Außerdem wächst diese Funktion schneller als jede Exponentialfunktion! Man konnte nachweisen, dass bereits eine Turingmaschine mit 8 Zuständen mindestens Einsen auf das Band schreiben kann!

Bisher weiß man:

Anzahl Zustände Max. Anzahl Einsen auf dem Band
1 1
2 4
3 6
4 13
5 mindestens 4098
6 mindestens 95.524.079



Bis heute ist unbekannt, wieviele Einsen eine Turingmaschine mit fünf oder mehr Zuständen auf das Band schreiben kann.

Das Problem bei der Berechnung der maximalen Anzahl von Einsen ist, dass man alle Turingmaschinen mit einer bestimmten Anzahl von Zuständen testen muss. Darunter sind aber immer auch Maschinen, die nie halten! Aufgrund der Unentscheidbarkeit des Halteproblems lässt sich aber nicht entscheiden, ob eine Turingmaschine hält oder nicht.

Im Jahr 1984 wurde ein Biber mit 5 Zuständen und 501 Einsen gesichtet. Später fand man einen Biber mit 1915 Einsen und im Jahr 1989 wurde in Deutschland einer mit 4098 Einsen gesichtet. Dieses bisher letzte Exemplar wurde nach einer 3-tägigen Jagd mit Hilfe eines Hochgeschwindigkeitscomputers gefunden.

In dem Simulationsprogramm zu diesem Modul ist ein Biber mit fünf Zuständen und 501 Einsen enthalten.


Wenn du dich an der Bibersuche beteiligen möchtest, solltest du beachten, dass es etwa 1015 Turingmaschinen mit fünf Zuständen gibt, die Einsen und Leerzeichen auf das Band schreiben bzw. vom Band lesen können. Entweder du testest alle diese Maschinen oder du hast Glück und findest eine, die mehr als 4098 Einsen auf das Band schreibt.
 
Seite 15/17