Fleißiger Biber

Fleißige Biber (auch engl.: 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.