IvanP (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
(Kategorien hinzufügen) Markierung: categoryselect |
||
| (4 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 6: | Zeile 6: | ||
Solche Turingmaschinen werden auch '''Busy Beaver''' (englisch ''fleißige Biber'') genannt. |
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, |
||
| + | *Σ(3)=6, |
||
| + | *Σ(4)=13, |
||
| + | *Σ(5)≥4098, |
||
| + | *Σ(6)>3.514x10<sup>18267</sup>, |
||
| + | *Σ(7)>10<sup>10<sup>10<sup>10<sup>18705352</sup></sup></sup></sup> |
||
== Einzelnachweise == |
== Einzelnachweise == |
||
<references /> |
<references /> |
||
| + | [[Kategorie:Funktion]] |
||
| − | |||
| − | {{stub}} |
||
Aktuelle Version vom 6. September 2016, 19:30 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.514x1018267,
- Σ(7)>1010101018705352
Einzelnachweise[]
- ↑ Michel, Pascal: Busy Beaver Competitions.
- ↑ Weisstein, Eric W.: Busy Beaver.