Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 1 / 12J / b / 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 instructionNo other instruction can lower the length of register $0$. Consequently at leastsuch remove instructions occur in this computation. Since words of arbitrary length exist, the assertion follows.