rado

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$.