Direkt zum Inhalt

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.

Lesermeinung

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos