Fleißige Biber (engl.: busy beaver)

von Christian Seise (2006)

Gliederung

1. Fleißige Biber
1. "Was sind fleißige Biber?"
2. Auf "Biberjagd", oder: wie findet man fleißige Biber?
3. Beispiele für fleißige Biber
2. Radós Σ-Funktion
1. Allgemeines über die Fkt
2. Beweis der nicht-Berechenbarkeit

Was sind "fleißige Biber"?

Was sind "fleißige Biber"? (I)

Ein fleißiger Biber (engl. busy beaver)...

• ist eine TM (Turingmaschine)
• besitzt das Alphabet A = {0,1} und n Zustände
• führt bei jedem Arbeitsschritt genau eine Links- oder Rechtsbewegung aus
• soll so viele Einsen wie möglich auf ein leeres Band (gefüllt mit Nullen) schreiben
• soll nach "getaner Arbeit" anhalten

Was sind "fleißige Biber"? (II)

• Keine andere TM (Anz. Zustände gleich) soll mehr Einsen auf das Band schreiben.
• Sind all diese Bedingungen erfüllt, dann nennt man diese Turingmaschine
  --> "Fleißiger Biber mit n Zuständen"

• Ermals betrachtet von Tibor Radó seit 1962.
  

Auf "Biberjagd"

Auf "Biberjagd" (I)

Wie findet man einen fleißigen Biber?

• Es gibt keine schnelle Methode einen fleißigen Biber zu finden.
• Einzige Möglichkeit:
  • Systematisches Erstellen und Prüfen aller TM mit n Zuständen
• Schwierigkeiten:
• Schon bei 5 Zuständen gibt es 63.403.380.965.376 mögliche Turingmaschinen
• Man weiß nicht, wie lange man warten soll (hält die TM an?)
• Zeitaufwand groß

Beispiele für fleißige Biber

Beispiele für fleißige Biber (I)

Radós Σ-Funktion

Radós Σ-Funktion (I)

Funktionswerte:

Radós Σ-Funktion (II)

• Eigenschaften:
• Es sind nur die ersten 4 Werte der Funktion sicher bekannt
• Die Σ-Funktion wächst immens schnell
• Die Σ-Funktion ist monoton, d.h. wenn n<k, dann ist auch Σ(n)<Σ(k)

• Das heißt es gibt keine TM, die für alle n∈ N (nach endlich vielen Schritten) Σ(n) berechnen kann.

Radós Σ-Funktion (III)

Beweisführung (nach Dr. Becker):

Vorraussetzung:

• Monotonie von Σ (Σ(n)<Σ(n+1) ∀ n ∈ N)
• Σ(n) ≥ n ∀ n ∈ N.

Annahme:

• Es existiere eine (fiktive) Turingmaschine T_Σ, die Σ(n) berechnen kann.
  
• Weiterhin sei die Anzahl der Zustände von T_Σ k.

Radós Σ-Funktion (IV)

Zu zeigen:
Es gibt eine TM T_n mit n Zuständen, die eine Baumstammreihe der Länge n erzeugt:

Lösung:

Radós Σ-Funktion (V)

Zu zeigen:
Es gibt eine TM T₇ mit 7 Zuständen, die eine gegebene Baumstammreihe verdoppelt.
Lösung:

Radós Σ-Funktion (VI)

Nun wird die (fiktive) Verknüpfung der Maschinen T_n,7,Σ erzeugt:
Lösung (nur T_n,7):

Radós Σ-Funktion (VII)

Das heißt also die verknüpfte TM:

• erzeugt zunächst eine Baumstammreihe der Länge 2n
• und berechnet anschließend Σ(2n)

Merke: Anzahl der Zustände: n+7+k.

Vergleich unserer TM T_n,7,Σ mit einem fleißigen Biber T_FB(n+7+k) mit n+7+k Zuständen:

• T_n,7,Σ hat n+7+k Zustände und erzeugt Σ(2n) Baumst.
• T_FB(n+7+k) hat n+7+k Zustände und erzeugt Σ(n+7+k) Baumst.

Radós Σ-Funktion (VIII)

Ein Biber mit n Zuständen erzeugt die max. mögliche Anz. an Einsen: -->
Σ(n+7+k) ≥ Σ(2n)

Wählen von n = 2(7+k):

• n+7+k = 3(7+k) und
• 2n = 4(7+k)

--> 3(7+k) &lt 4(7+k) und damit folgt aus der Monotonie von Σ:

Σ(3(7+k)) < Σ(4(7+k)) und damit Σ(n+7+k) < Σ(2n).
Widerspruch! --> Die Annahme ist falsch.