Lemma des linear beschränkten Längenwachstum
Einfache Sprache
Wächst die Länge der Ausgabe für eine zuberechnende Funktion überproportional zur Länge der Eingabe, kann diese nicht durch eine Sequenzielle Maschine implementiert werden, da eine sequentielle Maschine einen Buchstabe des Eingabewortes nur auf eine endlich Menge an Ausgabesymbole abbilden kann. Die Länge der Ausgabe kann also maximal linear in Abhängigkeit der Länge der Eingabe wachsen.
Def. Lemma des Linear beschränkten Längenwachstum
Ist $f:A^*\rightarrow B^*$ eine Sequenzielle Funktion, dann existiert eine Konstante $c\in\mathbb{N}$ so, dass
$$|f(x)|\leq c(|x|+1)$$für alle $x\in\text{dom}(f)$, also für alle $x$ für die $f$ definiert ist.
Beweisidee: durch Induktion über $|x|$.
Beweis: Sei $M=(Q,A,B,\delta,\alpha,q_I,\iota,\omega)$ eine Sequenzielle Maschine, die $f$ berechnet. Sei $d$ die maximale Länge einer Ausgabe von $M$ in einem Schritt, d.h.
$$d = \max\left(\{|\iota|\}\cup\{|\alpha(q,a)|:q\in Q, a\in A\}\cup\{|\omega(q)|:q\in \mathrm{dom}(\omega)\}\right)$$1. Hilfslemma
Behauptung: $|\hat\alpha(q_I,x)|\leq d|x|$. Beweis: induktiv über $x$: IA: Sei $x = \varepsilon$. Dann gibt
$$\begin{align}|\hat\alpha(q_I,x)| &= |\hat\alpha(q_I,\varepsilon)| &\Huge|\normalsize\text{Def. $x$}\\ &= |\varepsilon| &\Huge|\normalsize\text{Def. $\hat\alpha$}\\&= 0 &\Huge|\normalsize\text{Def. $\varepsilon$}\\&= d|\varepsilon|&\Huge|\normalsize\text{Def. $d, \varepsilon$}\\&= d|x|&\Huge|\normalsize\text{Def. $x$}\\&\leq d|x|&\Huge|\normalsize\text{Def. $\leq$}\end{align}$$IS: Sei $w\in A^*$ und gelte die Induktionshypothese $|\hat\alpha(q_I,w)|\leq d|w|$. Sei $a\in A$, dann gilt
$$\begin{align}|\hat\alpha(q_I,wa)| &= |\hat\alpha(q_I,w)\alpha(\hat\delta(q_I,w), a)| &\Huge|\normalsize\text{Def. $\hat\alpha$}\\&= |\hat\alpha(q_I,w)|+|\alpha(\hat\delta(q_I,w), a)| &\Huge|\normalsize\text{Def. Konkatenation}\\&\leq|\hat\alpha(q_I,w)|+d &\Huge|\normalsize\text{Def. $d$}\\&\leq d|w|+d &\Huge|\normalsize\text{\textit{Induktionshypothese}}\\&= d(|w|+1) &\Huge|\normalsize\text{Distributivgesetz}\\&= d|wa| &\Huge|\normalsize\text{Def. Konkatenation, $a$}\end{align}$$
Setze nun $c = 2d$. Dann sehen wir, dass für alle $x\in\mathrm{dom}(f_M)$ gilt
$$\begin{align}|f_M(x)| &= |\iota\hat\alpha(q_I,w)\omega(\hat\delta(q_I,w))| &\Huge|\normalsize\text{Def. $f_M$}\\&= |\iota|+|\hat\alpha(q_I,w)|+|\omega(\hat\delta(q_I,w))| &\Huge|\normalsize\text{Def. Konkatenation}\\&\leq d+|\hat\alpha(q_I,w)|+d &\Huge|\normalsize\text{Def. $d,c$}\\&\leq d+d|x|+d &\Huge|\normalsize\text{\textit{1. Hilfslemma}}\\&= d(|x|+1)+d &\Huge|\normalsize\text{Distributivgesetz}\\&\leq d(|x|+1)+d(|x|+1)&\Huge|\normalsize\text{$0\leq|x|$}\\&= 2d(|x|+1)&\Huge|\normalsize\text{Summe}\\&= c(|x|+1)&\Huge|\normalsize\text{Def. $c$}\\\end{align}$$