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}