kurse:ef05a-2021:turingmaschinen:busybeaver [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Busy Beaver ======
Siehe auch https://de.wikipedia.org/wiki/Flei%C3%9Figer_Biber

Ein «Busy Beaver» (fleissiger Biber) ist jene TM mit $n$ Zuständen (plus den Halte-Zustand) und einem Alphabet der Grösse zwei (z.B. 0/1), die auf einem mit Nullen gefüllten Band **am meisten Einsen schreibt und auch anhält**. Diese Anzahl Einsen wird mit $\Sigma(n)$ bezeichnet.

===== Nicht-Berechenbarkeit von $\Sigma(n)$ =====
Könnte man $\Sigma(n)$ berechnen, könnte man damit das Halteproblem lösen. 
  * Man berechnet $\Sigma(3n+6)$, wobei $n$ die Anzahl Zustände von der zu prüfenden Maschine $T$ ist. 
  * Hält die Maschine $T$ nicht nach $\Sigma(3n+6)$ Schritten, hält sie nie.

Das heisst aber auch, dass man im Prinzip durch sequentielles Ausprobieren mathematische Sachverhalte beweisen könnte, man muss nur $\Sigma(3n+6)$ Zahlen durchprobieren, wobei $n$ die Anzahl Zustände jener TM ist, die das Durchprobieren erledigt.

Das Problem ist dass schon für $n=6$ die Anzahl Schritte $\Sigma(6) > 10^{18'000}$, wobei auch das nur eine Abschätzung ist. Für $n=7$ sind nicht einmal Schätzungen realistisch (ausser dass wohl schon die Anzahl Stellen der Zahl zu gross ist, um aufgeschrieben werden können).

===== Aufgaben =====
  * Wie viele mögliche Maschinendefinitionen gibt es für $n$ Zustände? (Das Alphabet besteht aus genau 2 Zeichen).
<hidden Lösungsvorschlag>
Folgende Abschätzung liefert eine zu grosse Zahl, da z.B. Maschinen mehrfach gezählt werden.
  * Jeder Zustand hat zwei Einträge (für . oder 1 lesen).
  * Für jeden dieser Einträge gibt es
    * 2 Möglichkeiten für das zu schreibende Zeichen
    * 2 Möglichkeiten für die Bewegung
    * $n+1$ Möglichkeiten für den Folgezustand (inklusive stop).
  * Also $4(n+1)$ Möglichkeiten pro Eintrag, d.h. $16(n+1)^2$ Möglichkeiten pro Zustand.
Die Anzahl Maschinen ist also
$$
\left(16(n+1)^2\right)^n
$$

| 0 | 1 | $10^{0}$ |
| 1 | 64 | $10^{1}$ |
| 2 | 20736 | $10^{4}$ |
| 3 | 16777216 | $10^{7}$ |
| 4 | 25600000000 | $10^{10}$ |
| 5 | 63403380965376 | $10^{13}$ |
| 6 | 232218265089212416 | $10^{17}$ |
| 7 | 1180591620717411303424 | $10^{21}$ |
| 8 | 7958661109946400884391936 | $10^{24}$ |
| 9 | 68719476736000000000000000000 | $10^{28}$ |
</hidden>
  * Ohne zu «googeln», programmieren Sie je eine Maschine mit $n=4,5,6,7$ Zuständen auf dem Alphabet «.1», die irgendwann anhält (Beweis durch Ausprobieren oder durch Überlegung). Wer programmiert den fleissigsten Biber?