FANDOM


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 Bearbeiten

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

Störung durch Adblocker erkannt!


Wikia ist eine gebührenfreie Seite, die sich durch Werbung finanziert. Benutzer, die Adblocker einsetzen, haben eine modifizierte Ansicht der Seite.

Wikia ist nicht verfügbar, wenn du weitere Modifikationen in dem Adblocker-Programm gemacht hast. Wenn du sie entfernst, dann wird die Seite ohne Probleme geladen.

Auch bei FANDOM

Zufälliges Wiki