Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 1 / 12J / d / 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^{\prime }$ such thatfor every word $x$.

Solved by gpt-5.6-sol high.