rado
Aus ProgrammingWiki
Archivierte Version vom 2015-06-13T13:06:49+00:00. Aktuelle Version
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.