Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 1 / 12J / a / Solution

The upper register index is the largest register number occurring in an instruction of $P$, with value zero if only register $0$ is used. A configuration records the current state and the contents of every register up to that index.

For input $\vec{w}$, let $C(0,M,\vec{w})$ be the initial configuration: the designated initial state, the words of $\vec{w}$ in the input registers, and the empty word in every remaining register. Recursively, if $C(t,M,\vec{w})$ is halting, keep it fixed; otherwise let $C(t+1,M,\vec{w})$ be the unique configuration into which $M$ transforms it. The resulting sequenceis the computation sequence.