BuK/IIm11/BuK-KA-RADO-Funktion

Wiki-Quelltext dieser Seite.

== 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 !!!'''