Busy Beaver

Für $n \in N$ ist der Fleißige Biber (Busy Beaver) bezogen auf die Schrittzahl definiert als die Funktion $S (n)$ :

S (n) := max {s (M) ∣ M ist eine haltende TM mit n Zuständen auf leerem Band}

wobei $s (M)$ die Anzahl der Schritte ist, die $M$ bis zum Halten macht.

Eigenschaft: $S (n)$ ist eine totale, aber nicht berechenbare Funktion.