Lemma des linear beschränkten Abstandswachstum

Einfache Sprache

Das Lemma des linear beschränkten Abstandswachstum besagt stark vereinfacht, dass sich wenn sich zwei Eingaben für eine Sequenzielle Maschine nur an einer Stelle (z.B. am Ende) unterscheiden, dann unterscheidet sich die Ausgabe auch nur an der zugehörigen Stelle (z.B. am Ende).

Def. Lemma des linear beschränkten Abstandswachstum

Sei $f: A^*\rightharpoonup B^*$ eine Sequenzielle Funktion. Dann existiert eine Konstante $c\in\mathbb{N}$ so, dass

$$d(f(x),f(y))\leq cd(x,y)$$

für alle $x,y\in\text{dom}(f)$. Wobei $d(x,y)$ den Abstand zwischen $x$ und $y$ berechnet.

Wir nutzen wieder das 1. Hilfslemma.

Beweis: Sei $u$ das maximale gemeinsame Präfix von $x$ und $y$ so, dass $x = ux_0$ und $y = uy_0$ für $x_0,y_0\in A^*$ gilt. Wir machen nun eine Fallunterscheidung nach dem Unterschied zwischen $x_0$ und $y_0$.

Falls $x_0 = y_0 = \varepsilon$, also $x=y$, gilt $d(f(x), f(y)) = 0 = d(x,y)$

Falls $|x_0|+|y_0| \geq 1$ definieren zu nächst die Sequenzielle Maschine $M$ die $f$ berechnet. Also $f_M = f$. Sei $d$ die maximale Länge der Ausgabe die $M$ in einem Berechnungsschritt produzieren kann, formal im Lemma des linear beschränkten Längenwachstum definiert. Durch dass setzen von $c := 4d$ erhalten wir folgende Gleichung:

Anwendung

• Satz reverse ist nicht sequentiell