Satz raise ist nicht sequentiell
Einfache Sprache
Def. Satz raise ist nicht sequentiell
Die Funktion raise ist keine Sequenzielle Funktion.
Beweisidee: Beweis durch Widerspruch Beweis: Wir nehmen an das $\mathrm{raise}$ sequentiell ist. Dann existiert nach dem Lemma des linear beschränkten Längenwachstum eine Konstante $c\in\mathbb N$ so, dass $|\mathrm{raise}(x)|\leq c(|x| + 1)$ für alle alle $x\in\mathrm{dom(raise)}$. Wir setzen nun $x=0^m1$ so, dass $\mathrm{raise}(x)=0^{2^m}1$ gilt. Dann gilt $|x| = m+1$ und $|\mathrm{raise}(x)| = 2^m+1$. Eingesetzt in die erste Gleichung ergibt sich ( #TODO warum wird hier $c$ durch $m$ ersetzt?), dass
$$2^m+1 \leq m(m+2)$$. Man sieht das es für $m \geq 6$ immer Widerspruch gibt. Wir setzen also $m = \max(6, c)$.