BuK-KA-RADO-Funktion

RADO-Funktion

\Sigma(n) bezeichnet die maximale Anzahl von Einsen (nicht unbedingt aufeinander folgend), die eine haltende TM über \{1\}^* und n Zustanden 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 heisst \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 !!!