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\})$