= Solution
Choose an input word $w$ of length at least $n+1$. The final value $f_{M,1}(w)=\chi_L(w)$ has length at most one. Every symbol initially in register $0$ must either be deleted or transferred elsewhere, and either action begins with a remove instruction
$$
-(0,q,q').
$$
No other instruction can lower the length of register $0$. Consequently at least
$$
|w|-1\geq n
$$
such remove instructions occur in this computation. Since words of arbitrary length exist, the assertion follows.
Back to article page
