BuK/IIm11/BuK-KA-RADO-Funktion

Wiki-Quelltext dieser Seite.

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