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
Beachte: Die Turingmaschine muss irgendwann stoppen! |
|||||||||||||||||||||||||||||
|
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:
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 |
