BuK-KA-RADO-Funktion

Aus ProgrammingWiki

RADO-Funktion

$\Sigma(n)$ bezeichnet die maximale Anzahl von Einsen (nicht unbedingt aufeinander folgend), die eine haltende TM über $\{1\}^*$ und n Zuständen zzgl. eines Haltezustands auf ein anfangs leeres Band schreiben kann. Die Kopfposition am Ende der Berechnung spielt (im Gegensatz zur sonstigen Vereinbarung) keine Rolle.

Einige Funktionswerte: $\Sigma$(1) = 1; $\Sigma$(2) = 4; $\Sigma$(3) = 6; $\Sigma$(4) = 13; $\Sigma$(5) $\geq$ 4098.

Eigenschaften der RADO-Funktion

1. $\Sigma(n) < \Sigma(n+1)$

2. Für alle n gilt $f(n) \leq \Sigma(n+k)$

Lemma 2

Wenn $f$ eine Turing-berechenbare Funktion ist, dann existiert eine TM $M_f$ mit $k$ Zuständen. Es gilt $f(n) \leq \Sigma(n+k)$ für alle $n$.

$\Sigma(k)$ schreibt maximal viele Einsen und $n$ Einsen kommen durch Vorschalten von $n$ Zuständen hinzu, da $f$ auf $n$ Einsen angesetzt wird.

$\Sigma(n+k)$ hinterlässt mindestens so viele Einsen auf dem Band, wie $M_f(n)$.

Lemma 3

Wenn $f,g$ berechenbar, dann auch "g nach f" (Beweis: Kopplung von Turing-Maschinen)

Beweis

z.z.: $\Sigma$ ist nicht berechenbar

Annahme: $\Sigma$ ist berechenbar.

Dann gibt es für $b$, mit $b(n) = \Sigma(2n)$ eine Turing-Maschine $M_b$ mit $k$ Zuständen.

Laut Lemma 2 gilt:

$b(n) \leq \Sigma(n+k)$, wobei $b(n) = \Sigma(2n)$. Das heißt $\Sigma(2n) \leq \Sigma(n+k)$.

Für ein spezielles $n$, mit $n = k+1$ ergibt sich $\Sigma(2k+2) \leq \Sigma(2k+1)$.

Laut Lemma 1 gilt:

$\Sigma(2k+2) > \Sigma(2k+1)$ Widerspruch !!!