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

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

Eigenschaft 2

• Für alle n gilt f(n) \le \sum(n+k)

Wenn f eine Turing-berechenbare Funktion ist, dann existiert eine TM M_f. M_f erzeugt mit k Zuständen eine maximale Anzahl von Einsen. Bei einer TM M_k werden n Einsen für n vorgeschaltete Zustände hinzugefügt, da f(n) auf n Einsen angesetzt wird. Somit kommen höchstens n Zustände zu M_k hinzu. Diese gesamte Maschine hat dann n + k Zustände und erzuegt mindestens soviele Einsen wie M_f, aber höchstens \sum(n + k).