= 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 <sequence>
$$
\boxed{\{C(t,M,\vec w):t\in\mathbb N\}}
$$
is the computation <sequence>.
Back to article page
