29 Was sind die Fleißigen Biber?

Fleißiger Biber – Wikipedia

Fleißige Biber (auch englisch busy beaver) sind spezielle Turingmaschinen, die möglichst viele Einsen auf das Band schreiben und die nach einer endlichen Anzahl Rechenschritte den Halt-Zustand einnehmen (also anhalten).

Die Radó-Funktion (auch Fleißiger-Biber-Funktion) gibt die maximale Anzahl der Einsen an, die ein fleißiger Biber mit einer gegebenen Anzahl von Zuständen schreiben kann. Beides wurde erstmals 1962 vom ungarischen Mathematiker Tibor Radó betrachtet.

Aktuell sind die folgenden Zahlen bekannt:

ZuständeSchritte
11
26
321
4107
547176870