Lexikon der Mathematik: busy-beaver-Funktion
Biberfunktion, Beispiel für eine nicht berechenbare Funktion, die von Rado 1962 angegeben wurde.
Diese Funktion \(b:{{\mathbb{N}}}_{0}\to {{\mathbb{N}}}_{0}\) ist definiert als die größtmögliche Anzahl b(n) von Strichen, die von einer Turing-Maschine mit n Zuständen produziert werden kann, angesetzt auf ein leeres Band. Es wird hierbei verlangt, daß die Turing-Maschine schließlich stoppt, und daß sie nur den Strich und das Leerzeichen als einzig mögliche Bandbeschriftungen verwendet.
Die Nicht-Berechenbarkeit der Funktion b ergibt sich aus dem folgenden Satz:
Für jede total berechenbare Funktion \(f:{{\mathbb{N}}}_{0}\to {{\mathbb{N}}}_{0}\)gibt es eine Konstante k, so daß
\begin{eqnarray}f(n)\lt b(n)\end{eqnarray}
für alle \(n\ge k\)gilt.Copyright Springer Verlag GmbH Deutschland 2017
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.