KA RADO-Funktion
Aus ProgrammingWiki
Inhaltsverzeichnis |
RADO-Funktion
Die Rado-Funktion ("Busy Beaver") $\Sigma : \N \rightarrow \N$ ermittelt die größtmögliche Anzahl an Einsen, die von einer stoppenden Turing-Maschine mit $n$ Zuständen auf ein anfangs leeres Band geschrieben werden. Dabei spielt es keine Rolle, an welcher Position die Einsen stehen, das heißt sie können auch durch Leerstellen unterbrochen sein. Ebenso spielt es keine Rolle, an welcher Stelle der Kopf der Turing-Maschine zum stehen kommt.
Funktionswerte:
$\Sigma(1) = 1$
$\Sigma(2) = 4$
$\Sigma(3) = 6$
$\Sigma(4) = 13$
$\Sigma(5) \geq 4098$
Die Rado-Funktion ist nicht berechenbar.
Nachweis der Nichtberechenbarkeit
Zu zeigen: $\Sigma$ ist nicht berechenbar.
Vorraussetzungen
- Wenn $f$ und $g$ Turing-berechenbar sind, dann ist auch $f \circ g$ Turing-berechenbar.
- $\Sigma (n) \lt \Sigma (n+1)$
- Für alle $n$ gilt: $f(n) \leq \Sigma (n+k)$. $f$ ist eine Turing-berechenbare Funktion.
Annahme
$\Sigma$ ist berechenbar.
