kurse:ef05a-2021:turingmaschinen:busybeaver

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision		 Previous revision
kurse:ef05a-2021:turingmaschinen:busybeaver [2021/08/31 19:58] – [Nicht-Berechenbarkeit von $\Sigma(n)$] Ivo Blöchligerkurse:ef05a-2021:turingmaschinen:busybeaver [2021/09/16 07:00] (current) – [Aufgaben] Ivo Blöchliger
Line 1: Line 1:
 +====== 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?
 +
 +