imported>RokerHRO: Die letzte Textänderung von ~2025-40830-01 wurde verworfen und die Version 258953857 von Sir Stephens stille Stunde wiederhergestellt.

2025-12-16T16:31:13Z

Die letzte Textänderung von ~2025-40830-01 wurde verworfen und die Version 258953857 von Sir Stephens stille Stunde wiederhergestellt.

Neue Seite

'''Fleißige Biber''' (auch {{enS|busy beaver}}) sind spezielle [[Turingmaschine]]n, die möglichst viele Einsen auf das Band schreiben und die nach einer endlichen Anzahl Rechenschritte den Halt-Zustand einnehmen (also [[Terminiertheit|anhalten]]). Die '''Radó-Funktion''' (auch '''Fleißiger-Biber-Funktion''') gibt die maximale Anzahl der Einsen an, die ein fleißiger Biber mit einer gegebenen Anzahl von Zuständen schreiben kann. Beides wurde erstmals 1962<ref name="Rado">T. Radó: {{Webarchiv |url=http://www.alcatel-lucent.com/bstj/vol41-1962/articles/bstj41-3-877.pdf |text=On non-computable functions |wayback=20140327045029}} (PDF; 3,6 MB; Web-Archive vom 27. März 2014), In ''The Bell System Technical Journal'', Band 41, Nr. 3, S. 877–884, Mai 1962</ref> vom ungarischen Mathematiker [[Tibor Radó]] betrachtet.

Die Fleißiger-Biber-Funktion ist in der [[Theoretische Informatik|theoretischen Informatik]] ein Standardbeispiel für eine [[Wohldefiniertheit|wohldefinierte]], aber im Allgemeinen nicht [[Berechenbarkeit|berechenbare]] Funktion.<ref>{{Literatur |Autor=Eckart Zitzler |Titel=Dem Computer ins Hirn geschaut: Informatik entdecken, verstehen und querdenken |Verlag=Springer-Verlag |Datum=2017 |ISBN=978-3-662-53666-7 |Seiten=384 f. |Online=https://books.google.com/books?id=XLsyDwAAQBAJ&newbks=0&printsec=frontcover&pg=PA384 |Abruf=2021-10-25}}</ref>

== Formelle Betrachtung ==
=== Definition ===
Nach Radó ist ein fleißiger Biber eine [[Turingmaschine]], die <math>n</math> Zustände und einen Halt-Zustand einnehmen kann. Im Gegensatz zur allgemeinen Definition einer Turingmaschine unterliegt er jedoch speziellen Regeln.<ref name="Rado" /> So muss ein fleißiger Biber als Bewegungsschritt immer entweder nach links oder rechts auf dem Band gehen. Es gibt hier also keine Anweisung zum Verharren auf einem Feld. Ein fleißiger Biber erwartet auch keine leeren Felder, sondern nur welche, die bereits einen Wert aus dem ihm bekannten zweielementigen [[Alphabet (Informatik)|Alphabet]] <math>\{0, 1\}</math> enthalten. Das Band, auf das der fleißige Biber aufgesetzt wird, ist zuvor vollständig mit Nullen gefüllt. Ein fleißiger Biber muss nach einer endlichen Anzahl Schritte den Halt-Zustand einnehmen, darf also nicht in eine [[Endlosschleife (Programmierung)|Endlosschleife]] geraten. Er muss nach dem Anhalten die maximale Anzahl <math>k_n</math> von Einsen geschrieben haben, verglichen mit allen anderen Turingmaschinen mit ebenfalls <math>n</math> Zuständen, die nach den gleichen Regeln arbeiten. Nur Turingmaschinen, die nicht halten, könnten mehr Einsen schreiben, wären dann aber keine fleißigen Biber.

=== Fleißiger-Biber-Funktion ===
Über die maximale Anzahl <math>k_n</math> von Einsen, die ein fleißiger Biber mit <math>n</math> Zuständen schreibt, ist der Wert der Fleißiger-Biber-Funktion (auch Radó-Funktion) an der Stelle <math>n</math> definiert:
:<math>\Sigma(n) = k_n</math>.

=== Verwandte Funktionen ===
==== S(n): maximale Anzahl an Schritten ====
Radó definierte zusätzlich eine [[Funktion (Mathematik)|Funktion]] <math>S(n)</math>, deren Wert die maximale Anzahl an Schritten einer haltenden [[Turingmaschine]] mit zweielementigem Alphabet und <math>n</math> Zuständen ist. Auch diese Funktion <math>S</math> ist nicht [[Berechenbare Funktion|berechenbar]]. Wäre sie es, so wäre das [[Halteproblem#Eine äquivalente Formulierung|Halteproblem mit leerem Eingabeband]] entscheidbar, denn eine Turingmaschine mit <math>n</math> Zuständen, die mehr als <math>S(n)</math> Schritte macht, hält nie.

Da in jedem Schritt maximal eine Eins geschrieben werden kann, gilt

:<math>S(n) \ge \Sigma(n)</math>.

Zwischen den Funktionen <math>\Sigma</math> und <math>S</math> besteht weiterhin die folgende Beziehung.
:<math>S(n) < \Sigma(3n+6)</math>.<ref>A. M. Ben-Amram, B. A. Julstrom, U. Zwick:
''A Note on Busy Beavers and Other Creatures'',
In ''Mathematical Systems Theory'', 29(4), S. 375–386, Juli / August 1996, [[doi:10.1007/BF01192693]]</ref>

==== σ(n): Zusammenhängende Kette von Einsen ====
Eine ebenfalls nicht [[berechenbare Funktion]] ergibt sich, wenn die zusätzliche Beschränkung eingeführt wird, dass alle Einsen eine zusammenhängende Kette bilden müssen.
[[Datei:Bildliche Busy-Beaver-Beschreibung.png|links|mini|hochkant=2.1|Bildliche Beschreibung eines fleißigen Kleinbibers]]
{{Absatz}}
Als Bezeichnung dafür hat sich <math>\sigma(n)</math> eingebürgert.

==== D(n) ====
1965 hat C. Dunham eine weitere Variante der Funktion des fleißigen Bibers angegeben.<ref>C. Dunham: ''A Candidate for the simplest uncomputable function'' In: ''Communications of the Association for Computing Machinery'' (Letter to the Editor) 8, 4, 1965, {{ISSN|0001-0782}}, S. 201</ref> <math>D(n)</math> ist definiert als die maximale Anzahl Einsen, die eine [[Turingmaschine]] mit zweielementigem [[Alphabet (Informatik)|Alphabet]] und <math>n</math> Zuständen schreiben kann, wenn sie auf ein Band mit einem Block von <math>n</math> Einsen angesetzt wird und dabei hält. Wäre diese [[Berechenbare Funktion|Funktion berechenbar]], so gäbe es auch eine Turingmaschine M mit zweielementigem Alphabet, die <math>n\mapsto D(n)+1</math> berechnet. Diese Turingmaschine habe <math>m</math> Zustände. Dann wäre <math>D(m)+1 = M(m) \le D(m)</math>, wobei das Gleichheitszeichen gerade die Definition von M ist, und das <math>\le</math>-Zeichen daher rührt, dass M ja eine Maschine mit <math>m</math> Zuständen ist und angesetzt auf <math>m</math> (d. h. auf einen Block aus <math>m</math> Einsen) hält und daher nach Definition von <math>D</math> die Ungleichung <math>M(m)\le D(m)</math> erfüllen muss. Dieser Widerspruch zeigt die Nicht-Berechenbarkeit von <math>D</math>.

=== Nicht lösbares Problem ===
Die Bestimmung der fleißigen Biber ist ein Problem, das nicht allgemein (für alle <math>n</math>) [[algorithmisch]] lösbar ist. So ist nicht generell [[entscheidbar]], ob eine gegebene [[Turingmaschine]] mit <math>n</math> Zuständen tatsächlich eine maximale Anzahl von Einsen auf das Band schreibt. Für einzelne Turingmaschinen geringer Komplexität ist das allerdings möglich. Also ist die Menge der Werte von <math>\Sigma(n)</math> weder entscheidbar noch [[Rekursive Aufzählbarkeit|rekursiv aufzählbar]], obwohl <math>\Sigma(n)</math> [[Wohldefiniertheit|wohldefiniert]] ist. Da auch das [[Komplement (Mengenlehre)|Komplement]] dieser Menge nicht rekursiv aufzählbar ist, wird diese Menge gerne als Beispiel für eine Sprache gewählt, die nicht in der ersten Stufe der [[Arithmetische Hierarchie|arithmetischen Hierarchie]] liegt.

Wegen dieser Eigenschaften der [[Zielmenge|Wertemenge]] ist die [[Funktion (Mathematik)|Funktion]] <math>\Sigma</math> nicht [[Berechenbare Funktion|berechenbar]]. Man kann außerdem zeigen, dass ihr [[Asymptotische Analyse|asymptotisches Wachstum]] stärker ist als das jeder berechenbaren Funktion.

== Praktische Betrachtung ==
In der Praxis hat sich gezeigt, dass schon für <math>n > 5</math> eine Erkenntnis über den Wert <math>\Sigma(n)</math> realistisch gesehen nicht mehr möglich zu sein scheint. Dazu müsste man für jede einzelne [[Turingmaschine]] mit <math>n</math> Zuständen jeweils herausfinden, nach wie vielen Schritten sie hält, oder anderenfalls beweisen, dass sie das nicht tut. Für eine gegebene Anzahl <math>n</math> von Zuständen (plus einem Haltezustand) gibt es bei einem [[Alphabet (Informatik)|Alphabet]] mit zwei Zeichen <math>(2 \cdot 2 \cdot (n+1))^{2n}</math> verschiedene Turingmaschinen, denn für jeden der <math>n</math> Eingangszustände muss jeweils für jedes der beiden möglichen gelesenen Symbole festgelegt werden, welches der beiden Symbole auf das Band geschrieben werden soll und in welche Richtung der Lesekopf bewegt werden soll und welchen der <math>n + 1</math> möglichen Zustände die Turingmaschine danach annehmen soll. Schon bei <math>n = 5</math> möglichen Eingangszuständen müssen somit <math>24^{10}</math> verschiedene Turingmaschinen betrachtet werden. Für <math>n = 6</math> ist die aktuell bekannte Untergrenze von Schritten bereits weit größer als die Anzahl der Atome im beobachtbaren Universum, außerdem müssen für den Nachweis [[Collatz-Problem|Collatz]]-ähnliche Probleme gelöst werden.<ref>[https://wiki.bbchallenge.org/wiki/Antihydra ''Antihydra: Maschine mit 6 Zuständen und Collatz-ähnlichem Verhalten''] bbchallenge.org, Juni 2024, abgerufen am 3. Juli 2024</ref>

Anfang 1983 fand in der Universität Dortmund – heute TU Dortmund – eine Tagung der Gesellschaft für Informatik statt. Sie widmete sich der theoretischen Informatik und lobte einen Wettbewerb für fleißige Biber mit fünf Zuständen aus. Es trafen 133 Programme ein, die ein [[Liste der Siemens-Computer#Mittlere Datentechnik|Siemens-7.748]]-Computer überprüfte. Die siegreiche Befehlsliste schickte Uwe Schult aus Hamburg; sie zeichnete 501 Einsen auf das Turing-Band.<ref>{{Internetquelle |autor=J. Ludewig, U. Schult, F. Wankmüller |url=https://docs.bbchallenge.org/other/lud20.pdf |titel=CHASING THE BUSy-BEAVER - NOTES AND OBSERVATIONS ON A COMPETITION TO FIND THE 5-STATE BUSY BEAVER |werk=bbchallenge.org |datum=1983 |sprache=englisch |abruf=2025-07-11}}</ref>

Der Bulgare Georgi Georgiev veröffentlichte 2003 eine Untersuchung, in der er fleißige Biber daraufhin analysierte, ob sie anhalten würden oder nicht.<ref>[http://skelet.ludost.net/bb/nreg.html Busy Beaver nonregular machines for class TM(5)]</ref> Für <math>n = 5</math> entzogen sich lediglich knapp über 40 fleißige Biber einem gesicherten Ergebnis, da sie aufgrund besonderer Verhaltensweisen nicht mit den von Georgiev angewandten Methoden abschließend zu analysieren waren. Von denen, die als terminierend (anhaltend) bestimmt wurden, schreibt keiner mehr als 4098 Einsen auf das Band.

In internationaler Zusammenarbeit via ''The Busy Beaver Challenge'' wurden ab 2022 verbleibende Maschinen für <math>n = 5</math> mit irregulärem Verhalten untersucht und schließlich durch mxdys (Pseudonym) ein algorithmischer Beweis in [[Rocq]] zusammengestellt, der den bereits 1989 von Jürgen Buntrock und Heiner Marxen gefundenen Rekordhalter für BB(5) final bestätigt hat.<ref>[https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237 ''Ankündigung Nachweis von BB(5)''] bbchallenge.org, Juli 2024, abgerufen am 3. Juli 2024</ref>

{| class="wikitable zebra" style="text-align:right; line-height:144%"
|-
! Zustände <math>n</math> || Turing- maschinen<ref>[[On-Line Encyclopedia of Integer Sequences|OEIS]], [https://oeis.org/A052200 A052200].</ref> || <math>\Sigma(n)</math> || <math>S(n)</math> || Jahr || Autor(en) Quelle
|-
| style="text-align:center" | 1 || 64 || 1 || 1 || style="text-align:left" | 1962 || style="text-align:left" | Radó
|-
| style="text-align:center" | 2 || 20 736 || 4 || 6 || style="text-align:left" | 1962 || style="text-align:left" | Radó
|-
| style="text-align:center" | 3 || 16 777 216 || 6 || 21 || style="text-align:left" | 1965 || style="text-align:left" | Lin, Radó
|-
| style="text-align:center" | 4 || 25 600 000 000
|| 13 || 107 || style="text-align:left" | 1972 || style="text-align:left" | Weimann, Casper, Fenzel
|-
| rowspan="2" style="text-align: center;" |5
| rowspan="2" |63 403 380 965 376
|501
|134 467
| style="text-align: left;" |1983
| style="text-align: left;" |Ludewig, Schult, Wankmüller
|-
| 4 098 || 47 176 870 || style="text-align:left" | 2024 || style="text-align:left" | Kooperation
|-
| style="text-align:center" | 6 || ≈ 2,322 ⋅ 1017 || colspan="2" style="text-align:left" | <math> > 2 \uparrow \uparrow \uparrow 5 </math> (siehe [[Pfeilschreibweise]]) || style="text-align:left" | 2025 || style="text-align:left" | mxdys<ref>[https://wiki.bbchallenge.org/wiki/1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE ''BB(6) Rekordhalter Juni 2025''] bbchallenge.org, abgerufen am 3. Juli 2025</ref>
|-
| style="text-align:center" | 7 || ≈ 1,181 ⋅ 1021 || colspan="2" style="text-align:left" | <math> > 2 \uparrow^{11} 2 \uparrow^{11} 3 </math> || 2025 || style="text-align:left" | Pavel Kropitz<ref>[https://wiki.bbchallenge.org/wiki/1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF ''BB(7) Rekordhalter Mai 2025''] bbchallenge.org, abgerufen am 3. Juli 2025</ref>
|}

== Beispiele ==

=== Fleißiger Biber mit 1 Zustand ===
[[Datei:Busy beaver 1-state.svg|mini|hochkant=1.0|Fleißiger Biber mit 1 Zustand]]
Der Automat ist definiert durch <math>M</math>:
:<math>M = (\{q_0, q_f\}, \{\}, \{0,1\}, \delta, q_0, 0, \{q_f\})</math>,
wobei
:{| style="line-height:90%"
|<math>\{q_0, q_f\}</math> || die möglichen Zustände beschreibt,
|-
|<math>\{\}</math> || die Menge der Eingabesymbole auf dem Band ist (hier leer),
|-
|<math>\{0,1\}</math> ||die möglichen Symbole auf dem Band beschreibt (hier binär),
|-
|<math>\delta</math> || die partielle Überführungsfunktion darstellt,
|-
|<math>q_0, 0</math> || die Startbedingungen sind,
|-
|<math>\{q_f\}</math> || den Zustand der Haltebedingung darstellt.
|}

Die partielle Überführungsfunktion <math>\delta</math> ist wie folgt definiert (Der Zustand <math>q_0</math> mit gelesenem Symbol <math>1</math> braucht hier nicht definiert werden, da er nie eingenommen wird):
{| class="wikitable" style="text-align:center"
|- style="line-height:120%"
! rowspan="2" | aktueller Zustand
! colspan="4" | Symbol
! rowspan="2" | neuer Zustand
! rowspan="2" | Kopf- richtung
|-
! colspan="2" style="width:10px" | geles.
! colspan="2" style="width:50px" | schr.
|- style="background:#FFFDFB; font-family:monospace, Courier; line-height:100%"
| <math>q_0</math> || style="border-right:0" | 0 || colspan="2" style="border-left:0; border-right:0" | <big><big>→</big></big> || style="border-left:0" | 1 || style="background:#FF8080" | <math>q_f</math> || style="background:white" | '''Halt'''
|}

<math>M</math> durchläuft folgende Zustände, wobei die aktuelle Kopfposition fett gedruckt ist:
{| class="wikitable" style="text-align:center; margin-top:.5em; style="line-height:120%"
|-
! Schritt || Zust. || Band
|- style="text-align:center; font-family:monospace, Courier; line-height:120%"
| 1 || <math>q_0</math> || '''0'''0
|- style="text-align:center; font-family:monospace, Courier; line-height:120%"
| '''Halt''' || style="background:#FF8080" | <math>q_f</math> || 1'''0'''
|}

=== Fleißiger Biber mit 2 Zuständen ===
[[Datei:Busy beaver 2-state.svg|mini|hochkant=1.45|Fleißiger Biber mit 2 Zuständen]]

:<math> M = (\{q_0, q_1, q_f\}, \{\}, \{0,1\}, \delta, q_0, 0, \{q_f\})</math>

Die Überführungsfunktion <math>\delta</math> ist wie folgt definiert:
{| class="wikitable" style="text-align:center"
|- style="line-height:120%"
! rowspan="2" | aktueller Zustand
! colspan="4" | Symbol
! rowspan="2" | neuer Zustand
! rowspan="2" | Kopf- richtung
|-
! colspan="2" style="width:10px" | geles.
! colspan="2" style="width:50px" | schr.
|- style="background:#FFFDFB; font-family:monospace, Courier; line-height:100%"
| rowspan="2" | <math>q_0</math> || style="border-right:0" | 0 || style="border-right:0; border-left:0" colspan="2"|<big><big>→</big></big> || style="border-left:0" | 1 || style="background:#F0F2F4;" | <math>q_1</math> || R<big><big>→</big></big>
|- style="background:#FFFDFB; font-family:monospace, Courier; line-height:100%"
| style="border-right:0" | 1 || style="border-right:0; border-left:0" colspan="2"|<big><big>→</big></big> || style="border-left:0" | 1 || style="background:#F0F2F4;" | <math>q_1</math> || <big><big>←</big></big>L
|- style="background:#F0F2F4; font-family:monospace, Courier; line-height:100%"
| rowspan="2" | <math>q_1</math> || style="border-right:0" | 0 || style="border-right:0; border-left:0" colspan="2"|<big><big>→</big></big> || style="border-left:0" | 1 || style="background:#FFFDFB;"|<math>q_0</math> || <big><big>←</big></big>L
|- style="background:#F0F2F4; font-family:monospace, Courier; line-height:100%"
| style="border-right:0" | 1 || style="border-right:0; border-left:0" colspan="2"|<big><big>→</big></big> || style="border-left:0" | 1 || style="background:#FF8080;" | <math>q_f</math> || style="background:white;" | '''Halt'''
|}

<math>M</math> durchläuft folgende Zustände, wobei die aktuelle Kopfposition fett gedruckt ist:

{| class="wikitable" style="border:0; line-height:120%"
|-
! Schritt || Zust. || Band || rowspan="5" style="border:0; background:white" | || Schritt || Zust. || Band
|- style="text-align:center; font-family:monospace, Courier; margin-top:.5em"
| 1 || <math>q_0</math> || …000'''0'''000… || 5 || <math>q_0</math> || …0'''0'''11100…
|- style="text-align:center; font-family:monospace, Courier; margin-top:.5em"
| 2 || <math>q_1</math> || …0001'''0'''00… || 6 || <math>q_1</math> || …01'''1'''1100…
|- style="text-align:center; font-family:monospace, Courier; margin-top:.5em"
| 3 || <math>q_0</math> || …000'''1'''100… || '''Halt''' || style="background:#FF8080" | <math>q_f</math> || …011'''1'''100…
|- style="text-align:center; font-family:monospace, Courier; margin-top:.5em"
| 4 || <math>q_1</math> || …00'''0'''1100… || colspan="3" style="background:white; border:0" |
|}

=== Fleißiger Biber mit 3 Zuständen ===

[[Datei:Busy beaver 3-state.svg|mini|hochkant=1.45|Fleißiger Biber mit 3 Zuständen]]

:<math> M = (\{q_0, q_1, q_2, q_f\}, \{\}, \{0,1\}, \delta, q_0, 0, \{q_f\})</math>

Die Überführungsfunktion <math>\delta</math> ist wie folgt definiert:
{| class="wikitable" style="text-align:center"
|- style="line-height:120%"
! rowspan="2" | aktueller Zustand
! colspan="4" | Symbol
! rowspan="2" | neuer Zustand
! rowspan="2" | Kopf- richtung
|-
! colspan="2" style="width:10px" | geles.
! colspan="2" style="width:50px" | schr.
|- style="background:#FFFDFB; font-family:monospace, Courier; line-height:100%"
| rowspan="2" | <math>q_0</math> || style="border-right:0" | 0 || colspan="2" style="border-right:0; border-left:0"|<big><big>→</big></big> || style="border-left:0" | 1 || <math>q_1</math> || R<big><big>→</big></big>
|- style="background:#FFFDFB; font-family:monospace, Courier; line-height:100%"
| style="border-right:0" | 1 || colspan="2" style="border-right:0; border-left:0"|<big><big>→</big></big> || style="border-left:0" | 1 || style="background:#FF8080" | <math>q_f</math> || '''Halt'''
|- style="background:#F0F2F4; font-family:monospace, Courier; line-height:100%"
| rowspan="2" | <math>q_1</math> || style="border-right:0" | 0 || colspan="2" style="border-right:0; border-left:0"|<big><big>→</big></big> || style="border-left:0" | 0 || <math>q_2</math> || R<big><big>→</big></big>
|- style="background:#F0F2F4; font-family:monospace, Courier; line-height:100%"
| style="border-right:0" | 1 || colspan="2" style="border-right:0; border-left:0"|<big><big>→</big></big> || style="border-left:0" | 1 || <math>q_1</math> || R<big><big>→</big></big>
|- style="background:#F8FFF4; font-family:monospace, Courier; line-height:100%"
| rowspan="2" | <math>q_2</math> || style="border-right:0" | 0 || colspan="2" style="border-right:0; border-left:0"|<big><big>→</big></big> || style="border-left:0" | 1 || <math>q_2</math> || <big><big>←</big></big>L
|- style="background:#F8FFF4; font-family:monospace, Courier; line-height:100%"
| style="border-right:0" | 1 || colspan="2" style="border-right:0; border-left:0"|<big><big>→</big></big> || style="border-left:0" | 1 || <math>q_0</math> || <big><big>←</big></big>L
|}

<math>M</math> durchläuft folgende Zustände, wobei die aktuelle Kopfposition fett gedruckt ist:

{| class="wikitable float-left" style="text-align:center; margin-top:.5em; border:0"
|-
! Schritt || Zust. || Band || rowspan="6" style="border:0; background:white" |
! Schritt || Zust. || Band || rowspan="6" style="border:0; background:white" |
! Schritt || Zust. || Band
|- style="font-family:monospace, Courier; line-height:120%"
| 1 || <math>q_0</math> || 0'''0'''0000 || 6 || <math>q_0</math> || '''0'''11100 || 11 || <math>q_2</math> || 11110'''0'''
|- style="font-family:monospace, Courier; line-height:120%"
| 2 || <math>q_1</math> || 01'''0'''000 || 7 || <math>q_1</math> || 1'''1'''1100 || 12 || <math>q_2</math> || 1111'''0'''1
|- style="font-family:monospace, Courier; line-height:120%"
| 3 || <math>q_2</math> || 010'''0'''00 || 8 || <math>q_1</math> || 11'''1'''100 || 13 || <math>q_2</math> || 111'''1'''11
|- style="font-family:monospace, Courier; line-height:120%"
| 4 || <math>q_2</math> || 01'''0'''100 || 9 || <math>q_1</math> || 111'''1'''00 || 14 || <math>q_0</math> || 11'''1'''111
|- style="font-family:monospace, Courier; line-height:120%"
| 5 || <math>q_2</math> || 0'''1'''1100 || 10 || <math>q_1</math> || 1111'''0'''0 || '''Halt''' || style="background:#FF8080" | <math>q_f</math> || 111'''1'''11
|}
{{Absatz}}

=== Fleißiger Biber mit 4 Zuständen ===
[[Datei:Busy beaver 4-state.svg|mini|hochkant=1.45|Fleißiger Biber mit 4 Zuständen]]

:<math> M = (\{q_0, q_1, q_2, q_3, q_f\}, \{\}, \{0,1\}, \delta, q_0, 0, \{q_f\})</math>

Die [[Übergangsfunktion|Überführungsfunktion]] <math>\delta</math> ist wie folgt definiert:<ref name=":0">{{Internetquelle |autor=Mike Davey |url=https://www.youtube.com/watch?v=2PjU6DJyBpw |titel=A Turing Machine - Busy Beaver 4-state |datum=2010-03-07 |abruf=2025-04-04}}</ref>
{| class="wikitable" style="text-align:center"
|- style="line-height:120%"
! rowspan="2" | aktueller Zustand
! colspan="4" | Symbol
! rowspan="2" | neuer Zustand
! rowspan="2" | Kopf- richtung
|-
! colspan="2" style="width:10px" | geles.
! colspan="2" style="width:50px" | schr.
|- style="background:#FFFDFB; font-family:monospace, Courier; line-height:100%"
| rowspan="2" | <math>q_0</math> || style="border-right:0"|0 || colspan="2" style="border-right:0; border-left:0"|<big><big>→</big></big> || style="border-left:0"|1 || <math>q_1</math> || R<big><big>→</big></big>
|- style="background:#FFFDFB; font-family:monospace, Courier; line-height:100%"
| style="border-right:0"|1 || colspan="2" style="border-right:0; border-left:0"|<big><big>→</big></big> || style="border-left:0"|1 || <math>q_1</math> || <big><big>←</big></big>L
|- style="background:#F0F2F4; font-family:monospace, Courier; line-height:100%"
| rowspan="2" | <math>q_1</math> || style="border-right:0"|0 || colspan="2" style="border-right:0; border-left:0"|<big><big>→</big></big> || style="border-left:0"|1 || <math>q_0</math> || <big><big>←</big></big>L
|- style="background:#F0F2F4; font-family:monospace, Courier; line-height:100%"
| style="border-right:0"|1 || colspan="2" style="border-right:0; border-left:0"|<big><big>→</big></big> || style="border-left:0"|0 || <math>q_2</math> || <big><big>←</big></big>L
|- style="background:#F8FFF4; font-family:monospace, Courier; line-height:100%"
| rowspan="2" | <math>q_2</math> || style="border-right:0"|0 || colspan="2" style="border-right:0; border-left:0"|<big><big>→</big></big> || style="border-left:0"|1 || style="background:#FF8080" | <math>q_f</math> || style="background:white" | '''Halt'''
|- style="background:#F8FFF4; font-family:monospace, Courier; line-height:100%"
| style="border-right:0"|1 || colspan="2" style="border-right:0; border-left:0"|<big><big>→</big></big> || style="border-left:0"|1 || <math>q_3</math> || <big><big>←</big></big>L
|- style="background:#FFFCF0; font-family:monospace, Courier; line-height:100%"
| rowspan="2" | <math>q_3</math> || style="border-right:0"|0 || colspan="2" style="border-right:0; border-left:0"|<big><big>→</big></big> || style="border-left:0"|1 || <math>q_3</math> || R<big><big>→</big></big>
|- style="background:#FFFCF0; font-family:monospace, Courier; line-height:100%"
| style="border-right:0"|1 || colspan="2" style="border-right:0; border-left:0"|<big><big>→</big></big> || style="border-left:0"|0 || <math>q_0</math> || R<big><big>→</big></big>
|}

<math>M</math> erreicht den Halt-Zustand nach 107 Schritten und mit Bandinhalt „…1'''0'''111111111111…“.

=== Fleißiger Biber mit 5 Zuständen ===

[[Datei:Busy beaver 5-state.svg|mini|hochkant=1.45|Fleißiger Biber mit 5 Zuständen]]

:<math> M = (\{q_0, q_1, q_2, q_3, q_4, q_f\}, \{\}, \{0,1\}, \delta, q_0, 0, \{q_f\})</math>

Die Überführungsfunktion <math>\delta</math> ist wie folgt definiert:<ref name=":0" />
{| class="wikitable" style="text-align:center"
|- style="line-height:120%"
! rowspan="2" | aktueller Zustand
! colspan="4" | Symbol
! rowspan="2" | neuer Zustand
! rowspan="2" | Kopf- richtung
|-
! colspan="2" style="width:10px" | geles.
! colspan="2" style="width:50px" | schr.
|- style="background:#FFFDFB; font-family:monospace, Courier; line-height:100%"
| rowspan="2" | <math>q_0</math> || style="border-right:0"| 0 || colspan="2" style="border-right:0; border-left:0"|<big><big>→</big></big> || style="border-left:0"|1 || <math>q_1</math> || R<big><big>→</big></big>
|- style="background:#FFFDFB; font-family:monospace, Courier; line-height:100%"
| style="border-right:0"| 1 || colspan="2" style="border-right:0; border-left:0"|<big><big>→</big></big> || style="border-left:0"| 1 || <math>q_2</math> || <big><big>←</big></big>L
|- style="background:#F0F2F4; font-family:monospace, Courier; line-height:100%"
| rowspan="2" | <math>q_1</math> || style="border-right:0"| 0 || colspan="2" style="border-right:0; border-left:0"| <big><big>→</big></big> || style="border-left:0"| 0 || <math>q_0</math> || <big><big>←</big></big>L
|- style="background:#F0F2F4; font-family:monospace, Courier; line-height:100%"
| style="border-right:0"| 1 || colspan="2" style="border-right:0; border-left:0"|<big><big>→</big></big> || style="border-left:0"| 0 || <math>q_3</math> || <big><big>←</big></big>L
|- style="background:#F8FFF4; font-family:monospace, Courier; line-height:100%"
| rowspan="2" | <math>q_2</math> || style="border-right:0"| 0 || colspan="2" style="border-right:0; border-left:0"| <big><big>→</big></big> || style="border-left:0"| 1 || <math>q_0</math> || <big><big>←</big></big>L
|- style="background:#F8FFF4; font-family:monospace, Courier; line-height:100%"
| style="border-right:0"| 1 || colspan="2" style="border-right:0; border-left:0"|<big><big>→</big></big> || style="border-left:0"| 1 || style="background:#FF8080" | <math>q_f</math> || style="background:white" | '''Halt'''
|- style="background:#FFFCF0; font-family:monospace, Courier; line-height:100%"
| rowspan="2" | <math>q_3</math> || style="border-right:0"| 0 || colspan="2" style="border-right:0; border-left:0"| <big><big>→</big></big> || style="border-left:0"| 1 || <math>q_1</math> || <big><big>←</big></big>L
|- style="background:#FFFCF0; font-family:monospace, Courier; line-height:100%"
| style="border-right:0"| 1 || colspan="2" style="border-right:0; border-left:0"|<big><big>→</big></big> || style="border-left:0"| 1 || <math>q_4</math> || R<big><big>→</big></big>
|- style="background:#F2F0FF; font-family:monospace, Courier; line-height:100%"
| rowspan="2" | <math>q_4</math> || style="border-right:0"| 0 || colspan="2" style="border-right:0; border-left:0"| <big><big>→</big></big> || style="border-left:0"| 0 || <math>q_3</math> || R<big><big>→</big></big>
|- style="background:#F2F0FF; font-family:monospace, Courier; line-height:100%"
| style="border-right:0"| 1 || colspan="2" style="border-right:0; border-left:0"|<big><big>→</big></big> || style="border-left:0"| 0 || <math>q_1</math> || R<big><big>→</big></big>
|}

== Literatur ==

* [[Alexander K. Dewdney|A. K. Dewdney]]: ''The (new) Turing Omnibus. 66 Excursions in Computer Science.'' Computer Science Press, New York NY 1993, überarbeitet 1996, ISBN 0-7167-8271-5.
* Jochen Ludewig, Uwe Schult, Frank Wankmüller: ''Chasing the Busy Beaver. Notes and Observations on a competition to find the 5-state Busy Beaver.'' Universität Dortmund – Abt. Informatik, Dortmund 1983 (''Abteilung Informatik, Universität Dortmund.'' Bericht 159).
* Heiner Marxen, Jürgen Buntrock: ''[http://turbotm.de/~heiner/BB/mabu90.html Attacking the Busy Beaver 5].'' In: ''Bulletin of the EATCS.'' 40, Februar 1990, {{ISSN|0252-9742}}, S. 247–251.

== Weblinks ==
{{Commonscat|Busy beavers|Fleißiger Biber}}
* W. Zimmer: [http://www.wazimmer.de/infogk13_material-Dateien/fleissige_biber.pdf ''Fleißige Biber''] (PDF, 97 [[KiB]]), exakte Einführung mit Literaturbeispielen, auf 10 Seiten für Grundkurs Theoretische Informatik am [[Cusanus-Gymnasium Wittlich|Cusanus-Gymnasium]] [[Wittlich]] dargestellt
* Reinhard Völler: [http://users.informatik.haw-hamburg.de/~voeller/th/thinf/node16.html ''Turing-Berechenbarkeit''] aus [http://users.informatik.haw-hamburg.de/~voeller/th/thinf/thinf.html ''Theoretische Informatik''], kurze Darstellung von Rados ''Busy-Beaver''-Problem mit einigen Beispielen aus der Literatur, [[Hochschule für Angewandte Wissenschaften Hamburg]]
* Heiner Marxen: [http://turbotm.de/~heiner/BB/ ''Busy Beaver''] (englisch) – bekannte Resultate, sehr viele Links (zur Forschung) bis 2010, ''darunter:''
* [http://www2.informatik.uni-stuttgart.de/fmi/ti/projects/beaver/bbb.html ''Auf der Suche nach fleißigen Bibern''] – Turingmaschinensimulatoren, [[Universität Stuttgart]] 1996
* Scott Aaronson: [https://www.scottaaronson.com/papers/bb.pdf ''The Busy Beaver Frontier''] (PDF; 478 kB), Überblick und Diskussion offener Probleme, 2020

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4282517-9}}

{{SORTIERUNG:Fleissiger Biber}}
[[Kategorie:Berechenbarkeitstheorie]]

Fleißiger Biber - Versionsgeschichte

imported>RokerHRO: Die letzte Textänderung von ~2025-40830-01 wurde verworfen und die Version 258953857 von Sir Stephens stille Stunde wiederhergestellt.