BuK-KA-RADO-Funktion

z.z.: \Sigma ist nicht berechenbar

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)

Lösungsidee (Robert Rosenberger, Stefan Scheumann, Tobias Salzmann, Ronald Krause)

Annahme: \Sigma ist berechenbar

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).