Änderungen: Busy-Beaver-Funktion

Version vom 24. März 2015, 18:54 Uhr

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.514x10¹⁸²⁶⁷,
Σ(7)>10^{10^{10^{10^18705353}}}

Einzelnachweise

↑ Michel, Pascal: Busy Beaver Competitions.
↑ Weisstein, Eric W.: Busy Beaver.

Dieser Artikel ist ein Stub. Du kannst Googologie Wiki helfen, indem du ihn erweiterst.

[1] Michel, Pascal: Busy Beaver Competitions.

[2] Weisstein, Eric W.: Busy Beaver.

[1]

[2]

@@ Zeile 6: / Zeile 6: @@
 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.<ref><span style="font-variant:small-caps;">Weisstein</span>, Eric W.: [http://mathworld.wolfram.com/BusyBeaver.html ''Busy Beaver''.]</ref> Diese Busy-Beaver-Folgen wachsen schneller als jede berechenbare Folge, einige Zahlen sind jedoch bekannt.
+Anstatt S(''k'', 2) bzw. Σ(''k'', 2) wird auch S(''k'') und Σ(''k'') geschrieben.<ref><span style="font-variant:small-caps;">Weisstein</span>, Eric W.: [http://mathworld.wolfram.com/BusyBeaver.html ''Busy Beaver''.]</ref> Diese Busy-Beaver-Folgen wachsen schneller als jede berechenbare Folge, einige Zahlen sind jedoch bekannt:
 *Σ(1)=1,
 *Σ(2)=4,