Fleißiger Biber

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.

Die Fleißiger-Biber-Funktion ist in der theoretischen Informatik ein Standardbeispiel für eine wohldefinierte, aber im Allgemeinen nicht berechenbare Funktion.

↑ T. Radó: On non-computable functions (Memento vom 27. März 2014 im Internet Archive) (PDF; 3,6 MB; Web-Archive vom 27. März 2014), In The Bell System Technical Journal, Band 41, Nr. 3, S. 877–884, Mai 1962
↑ Eckart Zitzler: Dem Computer ins Hirn geschaut: Informatik entdecken, verstehen und querdenken. Springer-Verlag, 2017, ISBN 978-3-662-53666-7, S. 384 f. (google.com [abgerufen am 25. Oktober 2021]).

[Rado-1] T. Radó: On non-computable functions (Memento vom 27. März 2014 im Internet Archive) (PDF; 3,6 MB; Web-Archive vom 27. März 2014), In The Bell System Technical Journal, Band 41, Nr. 3, S. 877–884, Mai 1962

[2] Eckart Zitzler: Dem Computer ins Hirn geschaut: Informatik entdecken, verstehen und querdenken. Springer-Verlag, 2017, ISBN 978-3-662-53666-7, S. 384 f. (google.com [abgerufen am 25. Oktober 2021]).