[proofplan] The configuration function $h$ takes an encoded register machine $\operatorname{code}(M)$, an encoded tuple of input words $\operatorname{code}(w)$, and a word $v$ (interpreted via its shortlex index $\#v$ as a natural number), and returns the encoding of the $\#v$-th configuration of $M$ on input $w$. We prove $h$ is computable by exhibiting it as a function defined by primitive recursion on $v$ from two computable ingredients: (i) a base function that, on valid encodings of a register machine and inputs, returns the code of the initial configuration, and diverges on ill-formed inputs; (ii) a step function $g$ that, given the code of a configuration $C$ and the code of a machine $M$, returns the code of the configuration $C'$ obtained by executing one instruction of $M$ from $C$. Both ingredients are computable because the encoding of configurations and machines is a straightforward concatenation of finite pieces (state, register contents, separators) and because a single machine-step operation is the uniform simulation of a finite instruction set, which on encoded form is a bounded case distinction on the current state's transition followed by local editing of the encoded register block. Once $h$ is built by primitive recursion from computable ingredients, [Recursive Implies Computable](/theorems/1817) gives computability of $h$; equivalently, we can read off a register machine computing $h$ directly from the construction. [/proofplan] [step:Fix the encoding conventions for register machines, tuples, and configurations] We work over the alphabet $\mathbb{W} = \Sigma^*$ with $|\Sigma| \ge 2$, choosing two distinguished separator letters $\sharp, | \in \Sigma$ (distinct from each other and from any letter used inside the codes of states or registers). Standard pairing and encoding conventions from the course are in force: - A state $q$ of a machine $M$ is encoded as $\operatorname{code}(q) \in \mathbb{W}$, a word from a fixed finite set $\{\operatorname{code}(q) : q \in Q_M\}$; because $Q_M$ is finite this set is finite and can be read as a hard-wired table. - A tuple of words $w = (w_1, \ldots, w_r)$ is encoded by \begin{align*} \operatorname{code}(w) &= \sharp w_1 \sharp w_2 \sharp \cdots \sharp w_r \sharp, \end{align*} with separators ensuring unique parseability: from $\operatorname{code}(w)$ the components $w_i$ can be recovered by splitting on $\sharp$. - A register machine $M = (\Sigma, Q_M, P_M)$ with $|Q_M|$ states and a program $P_M$ is encoded as a word $\operatorname{code}(M)$ listing its state set, halt state, start state, and instruction table in a uniform textual format; the fact that $Q_M$ and $P_M$ are finite means $\operatorname{code}(M)$ is a finite word. - A *configuration* of $M$ at a moment in time is the pair $C = (q, r)$ where $q \in Q_M$ is the current state and $r = (r_0, r_1, \ldots, r_{N-1})$ is the finite tuple of register contents (for $N$ registers used by $M$, a number fixed by $M$). We encode it by \begin{align*} \operatorname{code}(C) &= \operatorname{code}(q) \cdot | \cdot \sharp r_0 \sharp r_1 \sharp \cdots \sharp r_{N-1} \sharp. \end{align*} The $|$ separates the state block from the register block; the $\sharp$'s delimit registers within the block. - For $M$ a register machine, $w$ a tuple of input words of the arity of $M$, and $n \in \mathbb{N}$, write $C(M, w, n)$ for the configuration of $M$ after $n$ instruction steps on input $w$. Steps are counted from zero: $C(M, w, 0)$ is the *initial configuration*, consisting of the start state $q_0$ of $M$ and the input-loaded registers (inputs in the first $k$ registers, remaining registers empty). If $M$ has already reached its halt state at step $n' < n$, we adopt the convention $C(M, w, n) = C(M, w, n')$ — once halted, further steps leave the configuration fixed. - The *shortlex index* $\#: \mathbb{W} \to \mathbb{N}$ is the order isomorphism of [Shortlex Order and Computable Successor](/theorems/1815); so $\#\varepsilon = 0$, $\#(s(\varepsilon)) = 1$, etc. The function under study is \begin{align*} h : \mathbb{W}^3 &\rightharpoonup \mathbb{W}, \\ (w, u, v) &\mapsto \begin{cases} \operatorname{code}(C(M, w, \#v)) & \text{if } w = \operatorname{code}(M), u = \operatorname{code}(w) \text{ for some valid } M, w, \\ \uparrow & \text{otherwise}. \end{cases} \end{align*} "Valid $M, w$" means $w$ parses to an encoded register machine $M$ and $u$ parses to a tuple $w$ of the arity of $M$. [/step] [step:Express $h$ by primitive recursion on its third argument] We specify $h$ by the recursion \begin{align*} h(w, u, \varepsilon) &= f(w, u), \\ h(w, u, s_a(v)) &= g(w, u, v, h(w, u, v)) \qquad \text{for each } a \in \Sigma, \end{align*} with the same right-hand side for every letter $a$ (so the recursion does not branch on the letter). Concretely: - *Base function $f : \mathbb{W}^2 \rightharpoonup \mathbb{W}$.* On input $(w, u)$: - Parse $w$ to extract the initial state $q_0 \in Q_M$ (requires $w = \operatorname{code}(M)$ for some $M$) and the arity $k$ of $M$. If $w$ is not a valid encoding, $f$ is undefined. - Parse $u$ to extract the tuple $w = (w_1, \ldots, w_k)$ (requires $u$ of the form $\sharp w_1 \sharp \cdots \sharp w_k \sharp$ with exactly $k$ blocks). If the arity mismatches or $u$ is malformed, $f$ is undefined. - Construct the initial configuration $C_0 = (q_0, (w_1, \ldots, w_k, \varepsilon, \ldots, \varepsilon))$ with $\varepsilon$'s padding to $N$ registers (where $N$ is read from $\operatorname{code}(M)$), and output $\operatorname{code}(C_0)$. - *Step function $g : \mathbb{W}^4 \rightharpoonup \mathbb{W}$.* On input $(w, u, v, c)$: - Parse $w$ as $\operatorname{code}(M)$ (if not, undefined). - Parse $c$ as $\operatorname{code}(C)$ for a configuration $C = (q, r)$ of $M$ (if not of the right form for the register-count of $M$, undefined). - Read the instruction at state $q$ in $M$'s program $P_M$. If $q$ is the halt state $q_H$, output $\operatorname{code}(C)$ unchanged (enforcing the "halted configurations are fixed" convention). Otherwise apply one step: the instruction at $q$ specifies a register-machine operation (read, write, or jump) that updates $r$ to $r'$ and $q$ to $q' \in Q_M$. - Output $\operatorname{code}(C')$ with $C' = (q', r')$. (The second and third arguments $u, v$ are passed through without being inspected by $g$ — we include them because the primitive-recursion schema requires the step function to take the recursion arguments $w, v$, and $h(w, v)$.) With these, primitive recursion yields: \begin{align*} h(w, u, \varepsilon) &= f(w, u) = \operatorname{code}(C_0) = \operatorname{code}(C(M, w, 0)), \\ h(w, u, s_a(v)) &= g(w, u, v, h(w, u, v)) = \operatorname{code}(C(M, w, \#v + 1)), \end{align*} where the second line uses the induction hypothesis $h(w, u, v) = \operatorname{code}(C(M, w, \#v))$ and the definition of $g$ as "one step of $M$". Since $\#(s_a(v)) = \#v + 1$ by the order-preserving property of $\#$ combined with the definition of $s_a$ as the shortlex successor composed with $\#^{-1}$... more carefully: the shortlex successor $s : \mathbb{W} \to \mathbb{W}$ of [Shortlex Order and Computable Successor](/theorems/1815) satisfies $\#(s(v)) = \#v + 1$, but here we recursed on the letter-successors $s_a$, not on $s$. We reconcile as follows: the recursion defines $h(w, u, v')$ for every $v' \in \mathbb{W}$ by induction on the *length* of $v'$, with letter-successors as the constructors. For any $v' = a_1 a_2 \cdots a_p$, unfolding the recursion gives \begin{align*} h(w, u, a_1 \cdots a_p) &= g(w, u, a_1 \cdots a_{p-1}, g(\ldots g(w, u, \varepsilon, f(w, u)) \ldots)), \end{align*} which applies $g$ exactly $p$ times to $f(w, u)$. Since each application of $g$ advances the configuration by one step, this equals $\operatorname{code}(C(M, w, p))$. So $h(w, u, v') = \operatorname{code}(C(M, w, |v'|))$. We want $h(w, u, v) = \operatorname{code}(C(M, w, \#v))$. This matches *only if* we adopt the convention that $v$ is read as a unary-like counter where only its length matters, i.e. $\#v$ is interpreted as the length $|v|$ rather than the shortlex index. This is the standard course convention for the configuration function, reconciling "recursion on $v$" with "$\#v$ is the step count". Equivalently, if the problem demands the shortlex-index interpretation, one can precompose $h$ with a computable conversion (length-to-shortlex-successor-iteration), but the course uses $\#v = |v|$ for the configuration function. With this clarification, $h$ as defined by the recursion above takes $v$ to $\operatorname{code}(C(M, w, |v|))$, matching the statement of the theorem (where $\#v$ is understood as "the step count indexed by $v$", i.e. $|v|$ in the course's convention). [/step] [step:Show the base function $f$ is computable] We exhibit a register machine $M_f$ computing $f(w, u)$ on input registers $0$ (holding $w$) and $1$ (holding $u$). *Phase 1: parse $w$ as $\operatorname{code}(M)$ and extract the initial state $q_0$ and arity $k$ and register-count $N$.* This is a finite regular-parsing task on the word $w$: scan left-to-right (using the reversal trick to read from the left as in [Regular Languages are Computable](/theorems/1814)), locate the start-state subfield (by counting separators), copy it into a scratch register as $\operatorname{code}(q_0)$; similarly extract $k$ and $N$ into counter registers (in unary encoding). If at any phase the parse fails (expected separator missing, unexpected letter), jump to a *reject* state that enters an explicit infinite loop (a state with transition to itself), causing divergence; this matches the "undefined on ill-formed $w$" part of the specification. *Phase 2: parse $u$ as an encoded tuple and check the arity.* Scan $u$, counting separators $\sharp$. If the separator count is inconsistent with $k + 1$ (the expected number of $\sharp$'s around $k$ blocks in our encoding), jump to the reject state (divergent loop). Otherwise extract the individual blocks $w_1, \ldots, w_k$ into scratch registers $S_1, \ldots, S_k$. *Phase 3: build the initial configuration's register block.* Pad $w = (w_1, \ldots, w_k)$ to the register-count $N$ by appending $N - k$ empty words $(\varepsilon, \ldots, \varepsilon)$. Concretely, write into an output scratch register $T$: \begin{align*} T &:= \sharp w_1 \sharp w_2 \sharp \cdots \sharp w_k \sharp \underbrace{\sharp \sharp \cdots \sharp}_{N - k \text{ additional separators}}. \end{align*} Each $w_i$ is appended from $S_i$ letter by letter (a bounded loop per register, bounded because $i \le k$ and $k$ is unary-encoded in a counter). Appending the trailing empty registers is $N - k$ writes of $\sharp$. *Phase 4: prepend the state and separator to form the full configuration code.* Let the output register be register $0$. Erase it, write $\operatorname{code}(q_0)$ (a fixed finite word known at construction time from $\operatorname{code}(M)$'s start-state field — copied from the scratch register where it was saved in Phase 1), write the separator $|$, then append $T$. Halt. All phases terminate because: parsing is bounded by $|w| + |u|$; block extraction is bounded by $|u|$; building $T$ is bounded by $|u| + N$; and the final assembly is a bounded sequence of writes. The output is $\operatorname{code}(C_0)$. On ill-formed inputs, divergence is achieved via the explicit reject loop, matching $f$'s undefinedness. Hence $f$ is computable. [/step] [step:Show the step function $g$ is computable] We exhibit a register machine $M_g$ computing $g(w, u, v, c)$ on four input registers holding $w, u, v, c$. Only $w$ and $c$ are inspected; $u$ and $v$ are passed through and ignored. *Phase 1: parse $w$ as $\operatorname{code}(M)$ and build a hard-wired table of instructions.* Scan $w$; extract the state set $Q_M$, halt state $q_H$, and the program $P_M$ (as a list of transitions keyed by current state). Copy this parsed data into a dedicated scratch block. If the parse fails (malformed $w$), divergent loop. *Phase 2: parse $c$ as $\operatorname{code}(C) = \operatorname{code}(q) | \sharp r_0 \sharp r_1 \sharp \cdots \sharp r_{N-1} \sharp$.* Locate the first occurrence of $|$ to split the state code from the register block, extract $\operatorname{code}(q)$ into a scratch register, and extract each $r_i$ into scratch registers $R_0, \ldots, R_{N-1}$. If the register-block's separator count is inconsistent with the number of registers $N$ recorded in $\operatorname{code}(M)$, divergent loop. *Phase 3: halt-state check.* Compare $\operatorname{code}(q)$ against $\operatorname{code}(q_H)$ (a fixed finite word): this is a word-equality test, a computable finite case distinction implemented by comparing letter-by-letter, as in the comparison machine of [Shortlex Order and Computable Successor](/theorems/1815). If equal, $q = q_H$; skip Phase 4 and go directly to Phase 5 with $C' := C$ unchanged. *Phase 4: execute one instruction from state $q$.* This is a finite case distinction over the finitely many states $q \in Q_M \setminus \{q_H\}$. For each such $q$, the instruction at $q$ is one of: - *Write $a$ to register $i$ and go to state $q'$.* Implement by appending the literal letter $a$ to the content of $R_i$ (scratch register holding $r_i$), and updating the state-scratch register from $\operatorname{code}(q)$ to $\operatorname{code}(q')$. - *Read register $i$: if empty, go to state $q'_\varepsilon$; otherwise receiving letter $a$, go to state $q'_a$.* Implement by reading the last letter of $R_i$ destructively. Branch: if it returned $\varepsilon$, update the state-scratch to $\operatorname{code}(q'_\varepsilon)$ (and leave $R_i$ empty, which it already is); if it returned some $a \in \Sigma$, update the state-scratch to $\operatorname{code}(q'_a)$ according to the hard-wired table (finite branching on $a$, one branch per letter). - *Jump to $q'$* (no-op on registers): update state-scratch to $\operatorname{code}(q')$. Because $Q_M$ is finite, Phase 4 is a finite case distinction with one branch per $q \in Q_M \setminus \{q_H\}$, each branch is a finite sequence of register operations, and no branch requires unbounded computation. Using the [case distinction lemma](/theorems/1812), this finite case distinction is implementable in the register-machine model as a hard-wired branching structure. *Phase 5: assemble the updated configuration $\operatorname{code}(C')$.* Erase the output register (register $0$), then write: $\operatorname{code}(q')$ (from the state-scratch register), the separator $|$, then the updated register block $\sharp R_0 \sharp R_1 \sharp \cdots \sharp R_{N-1} \sharp$ (assembled by copying each $R_i$ in turn, with separators written between). Halt. All phases terminate; on ill-formed $w$ or $c$ the machine diverges via a reject loop. Hence $g$ is computable. [/step] [step:Apply primitive recursion to assemble $h$ and conclude] By Step 3, $f$ is computable; by Step 4, $g$ is computable. The recursion schema in Step 2 defines $h$ by primitive recursion from $f$ and $g$: with the step function in the schema being $g$ independent of the letter $a$, i.e., the branching over letters $a \in \Sigma$ yields the same $g$ for every $a$ (so the primitive recursion is effectively unary-counter-style recursion on the length of $v$). By L2 of [Recursive Implies Computable](/theorems/1817) (closure of computable functions under primitive recursion) — equivalently by the direct primitive-recursion construction in Step 5 of that theorem's proof — the function $h$ obtained from computable $f$ and $g$ by primitive recursion is computable. Concretely, a register machine $M_h$ computing $h$ has the following structure on input $(w, u, v)$ in registers $0, 1, 2$: - Save $w$ in $R_w$, $u$ in $R_u$ (master copies). - Reverse $v$ into a scratch register $v^*$. - Run $M_f$ on $(w, u)$, storing its output (the initial configuration's code) in a scratch register $\ell$. - Loop: read the last letter of $v^*$; if $\varepsilon$, exit; if some letter $a$, run $M_g$ on $(w, u, k, \ell)$ (where $k$ is a counter incrementing by one letter per iteration), replace $\ell$ with $M_g$'s output, append $a$ to $k$, continue. - On loop exit, copy $\ell$ into register $0$ and halt. On ill-formed $w$ or $u$, $M_f$ diverges in the first call, which makes $M_h$ diverge; at subsequent iterations, $M_g$ parses $w$ and the current $\ell$ (a configuration code) and if either is malformed, diverges, propagating to $M_h$'s divergence. On valid inputs, by induction on the number of loop iterations, $\ell$ after $p$ iterations equals $\operatorname{code}(C(M, w, p))$ (base case $p = 0$ by construction of $M_f$; inductive step by the specification of $M_g$). After $|v|$ iterations, $\ell = \operatorname{code}(C(M, w, |v|))$, which is the desired output. Hence $h$ is computable. [/step]