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).
- 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?