Busy-Beaver-Funktion

Die Busy-Beaver-Funktion kennt zwei unterschiedliche Definitionen:

• S(k, n) ist die Höchstanzahl der Schritte, die eine Turingmaschine mit k Zuständen und n Zeichen durchführen kann, wenn sie nicht anhält und von einem leeren Band aus startet.
• Σ(k, n) ist die Höchstanzahl der nicht leeren Zeichen, die eine Turingmaschine mit k Zuständen und n Zeichen auf einem Band hinterlassen kann, wenn sie nicht anhält und von einem leeren Band aus startet.

Solche Turingmaschinen werden auch Busy Beaver (englisch fleißige Biber) genannt.

Anstatt S(k, 2) bzw. Σ(k, 2) wird auch S(k) und Σ(k) geschrieben. Diese Busy-Beaver-Folgen wachsen schneller als jede berechenbare Folge, einige Zahlen sind jedoch bekannt:

• Σ(1)=1, 
• Σ(2)=4,
• Σ(3)=6,
• Σ(4)=13,
• Σ(5)≥4098,
• Σ(6)>3.514x10¹⁸²⁶⁷,
• Σ(7)>10^{10101018705352}