Satz reverse ist nicht sequentiell
Einfache Sprache
Def. Satz reverse ist nicht sequentiell
Die Funktion reverse ist keine Sequenzielle Funktion.
Beweisidee: Beweis durch Widerspruch Beweis: Wir nehmen an das $\mathrm{reverse}$ sequentiell ist. Nach dem Lemma des linear beschränkten Abstandswachstum existiert ein Konstante $c\in\mathbb N$ so, dass
$$d(\mathrm{raise}(x),f(y))\leq cd(x,y)$$Wir setzen $x = 0^{c+1}1$ und $y = 0^{c+1}0$. Dann gilt $d(x,y) = 2$ und $d(\mathrm{raise}(x), \mathrm{raise}(y))= d(10^{c+1},00^{c+1}) = 2(c+2)$. In die obere Ungleichung eingesetzt ergibt sich $2(c+2)\leq c2$, was offensichtlich falsch ist.