BuK/IIm14/Studenten/s3ankrau1/rado

Wiki-Quelltext dieser Seite.

==RADO-Funktion==
Die Rado-Funktion (Busy-Beaver) $\sum : \N \rightarrow \N$, die nach dem Erfinder Tibor Rado benannt ist, berechnet die maximale Anzahl von Einsen, die eine mit n-Zuständen stoppende Turing-Maschine auf ein leeres Band schreiben kann. Die Einsen müssen nicht wie üblich hintereinander stehen und die Position des Schreibkopfs am Ende spielt keine Rolle. Beispielwerte für die Rado-Funktion: $\sum(1) = 1$, $\sum(2) = 4$, $\sum(3) = 6$, $\sum(4) = 13$, $\sum(5) \ge 4098$.


Für $n=2$ berechnet die TM $M=(\{q_0,q_1,H\},\{1\},\{\$,1\},\delta,q_0,\$,\{H\})$ den Wert $\sum(2) = 4$.

[[Bild:Rado 2 n.jpg]]


[[Bild:Output rado.JPG]]

Die Rado-Funktion ist nicht Turing-berechenbar. Im Folgenden wird dies durch einen indirekten Beweis gezeigt.

==Eigenschaft 1==
* $\sum(n) < \sum(n + 1)$

Es gibt eine Turing-Maschine $M_n$ (zzgl. eines Haltezustands), die die Funktion $\sum(n) berechnet. Wird nun ein weiterer Zustand genommen und direkt nach dem Startzustand eingefügt, erhält man eine weitere Turing-Maschine $M_{n+1}$ mit $n + 1$ Zuständen. Diese erzeugt gegenüber $M_n$ mindestens eine 1 mehr, im Höchstfall $\sum(n + 1)$.