= Solution
Consider computations while a terminal block of $b$'s is removed from register $0$. Until that block has disappeared, the available instruction and next state depend on the current state and on the visible $b$, not on the untouched prefix $x$.
Take a block longer than $|Q|$. Record the state after each successive $b$ has been removed. Two records have the same state $q$, by the pigeonhole principle. If the corresponding removed tail lengths are $k\ne\ell$, the same finite instruction <sequences> work in front of every prefix $x$. Thus there are fixed times $t,t'$ such that
$$
\boxed{
C(t,M,xb^k)=(q,x)=C(t',M,xb^\ell)
}
$$
for every word $x$.
Back to article page
