Googologie Wiki
Advertisement

Die Busy-Beaver-Funktion[1] 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.[2] 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.514x1018267,
  • Σ(7)>1010101018705352    

Einzelnachweise[]

  1. Michel, Pascal: Busy Beaver Competitions.
  2. Weisstein, Eric W.: Busy Beaver.
Advertisement