[proofplan] Using the [Recursive Functions via Trees](/theorems/1816) characterisation, it suffices to show that the class of computable partial functions contains the basic functions and is closed under composition, primitive recursion, and minimisation; an induction on the height of the recursion tree then gives computability of every partial recursive function. The basic functions (zero, successors, projections) are computed by short explicit register-machine programs. Closure under composition is the [concatenation lemma](/theorems/1810): feed the outputs of machines $M_{f_1}, \ldots, M_{f_m}$ into the input registers of $M_g$ after saving the original inputs, being careful that an unterminated $M_{f_i}$ correctly causes the composite machine to diverge. Closure under primitive recursion is implemented by a counter $k$ and an accumulator $\ell$: initialise $\ell := f(w)$, and while $k \ne v$, update $\ell := g_a(w, k, \ell)$ and append $a$ to $k$ (where $a$ is the next letter of $v$); after $|v|$ iterations $\ell = h(w, v)$. Closure under minimisation uses a single counter $k$ starting at $\varepsilon$: compute $f(w, k)$; if it diverges the machine diverges; if it returns $\varepsilon$ output $k$; otherwise apply a successor to $k$ and loop. At every step we verify that undefinedness of the input function propagates correctly to undefinedness of the constructed function. [/proofplan] [step:Reduce to closure of the computable class under the three operations] Let $\mathcal{C}$ denote the class of computable partial functions $\mathbb{W}^k \rightharpoonup \mathbb{W}$ and let $\mathcal{R}$ denote the class of partial recursive functions. We want to show $\mathcal{R} \subseteq \mathcal{C}$. By the [Recursive Functions via Trees](/theorems/1816) characterisation, every $f \in \mathcal{R}$ equals $f_{T, \ell}$ for some recursion tree $(T, \ell)$ over the labels $\{\text{basic}_\phi, \text{comp}, \text{rec}, \text{min}\}$. We prove $f_{T, \ell} \in \mathcal{C}$ by induction on the height of $(T, \ell)$, split into four lemmas: - (L0) Every basic function (zero, successor $s_a$ for each $a \in \Sigma$, projection $\pi_i^k$) is computable. - (L1) If $g, f_1, \ldots, f_m \in \mathcal{C}$, then $g \circ (f_1, \ldots, f_m) \in \mathcal{C}$. - (L2) If $f \in \mathcal{C}$ and each $g_a \in \mathcal{C}$ for $a \in \Sigma$, then the function $h$ defined from $f$ and $\{g_a\}$ by primitive recursion is in $\mathcal{C}$. - (L3) If $f \in \mathcal{C}$ then $\mu f \in \mathcal{C}$. *Induction on the height of the tree.* The base case (height $0$) is a single leaf labelled with a basic function, handled by L0. In the induction step, the root is labelled $\text{comp}$, $\text{rec}$, or $\text{min}$, with children yielding partial functions in $\mathcal{C}$ by the induction hypothesis; then L1, L2, L3 respectively give that the root function is in $\mathcal{C}$. It remains to prove L0, L1, L2, L3. [/step] [step:Prove L0 — basic functions are computable] Recall the basic functions over $\mathbb{W} = \Sigma^*$ with $|\Sigma| \ge 1$: \begin{align*} \text{zero: } \mathbb{W}^0 &\to \mathbb{W}, \quad () \mapsto \varepsilon, \\ \text{successor } s_a : \mathbb{W} &\to \mathbb{W}, \quad v \mapsto va, \qquad a \in \Sigma, \\ \text{projection } \pi_i^k : \mathbb{W}^k &\to \mathbb{W}, \quad (w_1, \ldots, w_k) \mapsto w_i, \qquad 1 \le i \le k. \end{align*} - *Zero.* The machine with state set $\{q_S, q_H\}$ and no instructions at $q_S$ other than a transition to $q_H$ halts immediately with register $0 = \varepsilon$ (the convention for no-input machines). Hence zero is computable. - *Successor $s_a$.* On input register $0 = v$, execute a single "write $a$ to register $0$" instruction and transition to the halt state $q_H$. The resulting register $0$ contents equal $va = s_a(v)$, so $s_a$ is computable. - *Projection $\pi_i^k$.* The machine has input registers $0, 1, \ldots, k - 1$, holding $w_1, \ldots, w_k$ respectively (by convention the $j$-th input of a $k$-ary machine is in register $j - 1$, or register $j$ under an alternative convention; we use the version where the first argument is in register $0$ and the $i$-th argument is in register $i - 1$). If $i = 1$, register $0$ already holds $w_1$, and a direct transition to $q_H$ suffices. If $i \ne 1$, use a standard copy routine: erase register $0$, then copy register $i - 1$ into register $0$ (reading letters destructively from a scratch copy to preserve the source). Concretely: (a) Copy register $i - 1$ into a scratch register $j$ (by destructively reading register $i - 1$ and writing to both register $j$ and register $0$ in reverse; then draining $j$ back into register $i - 1$). This is the standard "non-destructive read" pattern of the register-machine model. (b) Halt. The final register $0$ contents equal $w_i = \pi_i^k(w_1, \ldots, w_k)$, so $\pi_i^k$ is computable. [/step] [step:Prove L1 — closure under composition] Let $g : \mathbb{W}^m \rightharpoonup \mathbb{W}$ and $f_i : \mathbb{W}^n \rightharpoonup \mathbb{W}$ ($i = 1, \ldots, m$) be computable, witnessed by register machines $M_g, M_{f_1}, \ldots, M_{f_m}$. We construct a machine $M_h$ computing the partial function \begin{align*} h : \mathbb{W}^n &\rightharpoonup \mathbb{W}, \\ (w_1, \ldots, w_n) &\mapsto g(f_1(w_1, \ldots, w_n), \ldots, f_m(w_1, \ldots, w_n)), \end{align*} with the usual convention that $h(w)$ is undefined iff some $f_i(w)$ is undefined or $g(f_1(w), \ldots, f_m(w))$ is undefined. This is the [concatenation lemma](/theorems/1810). Concretely, $M_h$ proceeds as follows: - *Save inputs.* Copy registers $0, \ldots, n - 1$ (holding $w_1, \ldots, w_n$) into scratch registers $R_1, \ldots, R_n$ (disjoint from the working registers of each $M_{f_i}$ and $M_g$, which can be ensured by renaming registers of the component machines to disjoint ranges). - *For each $i = 1, \ldots, m$ sequentially:* Restore the saved inputs $w_1, \ldots, w_n$ from $R_1, \ldots, R_n$ into the input registers expected by $M_{f_i}$ (by copying out, which preserves the saved copies). Run $M_{f_i}$. If $M_{f_i}$ does not halt, $M_h$ does not halt, which is the correct behaviour because $h(w)$ is undefined in this case. If $M_{f_i}$ halts, copy its output register into a dedicated storage register $S_i$ (distinct from all previously used registers). - *Prepare input for $M_g$.* Copy $S_1, \ldots, S_m$ into the input registers of $M_g$. - *Run $M_g$.* If it diverges, $M_h$ diverges (correctly, as $g$ is undefined on these inputs). If it halts, the output register holds $g(f_1(w), \ldots, f_m(w)) = h(w)$; ensure this output is in register $0$ (by a final copy) and halt. By the [concatenation lemma](/theorems/1810), the state sets of the component machines can be taken disjoint and their programs combined into a single program on the union of state sets, with the transitions above wiring one phase into the next. The function computed is $h$ on its domain, and divergence of $M_h$ corresponds exactly to undefinedness of $h$. Hence $h \in \mathcal{C}$. [/step] [step:Prove L2 — closure under primitive recursion] Let $f : \mathbb{W}^n \rightharpoonup \mathbb{W}$ and $g_a : \mathbb{W}^{n + 2} \rightharpoonup \mathbb{W}$ (one per $a \in \Sigma$) be computable, witnessed by machines $M_f$ and $\{M_{g_a}\}$. The function $h : \mathbb{W}^{n + 1} \rightharpoonup \mathbb{W}$ defined by primitive recursion is specified by \begin{align*} h(w, \varepsilon) &= f(w), \\ h(w, v a) &= g_a(w, v, h(w, v)), \qquad a \in \Sigma, \; v \in \mathbb{W}, \end{align*} with $h(w, u)$ undefined if any intermediate value in this recursive unfolding is undefined. We construct a machine $M_h$ that computes $h$ using two scratch registers $k$ and $\ell$ and a scratch register $v^*$ holding a copy of the recursion argument $v$. *Register layout.* Input registers $0, \ldots, n - 1$ hold $w_1, \ldots, w_n$; register $n$ holds the recursion argument $v$. We use three fresh scratch registers $k, \ell, v^*$ disjoint from all working registers of $M_f$ and $M_{g_a}$. *Phase 0: save $w$ and set up the recursion.* Copy $w_1, \ldots, w_n$ into a saved block $R_1, \ldots, R_n$. Copy register $n$ (holding $v$) into $v^*$, then reverse $v^*$ using the letter-by-letter reversal technique established in [Regular Languages are Computable](/theorems/1814), so that after reversal $v^* = \text{rev}(v)$; this lets us read the letters of $v$ from left to right by popping the last letter of $v^*$. Initialise $k := \varepsilon$ (erase register $k$). *Phase 1: compute the base value $\ell := f(w)$.* Restore $w_1, \ldots, w_n$ from $R_1, \ldots, R_n$ into the input registers expected by $M_f$, then run $M_f$. If $M_f$ diverges, $M_h$ diverges (correct, because $h(w, v)$ is undefined when $f(w)$ is undefined). If $M_f$ halts, copy its output into $\ell$. *Phase 2: iterate over letters of $v$.* Run a loop whose body is: (2a) Read the last letter of $v^*$. If the read returns $\varepsilon$, exit the loop (we have processed all letters of $v$). Otherwise the read returns some $a \in \Sigma$; continue with (2b) specialised to that $a$. (2b) For the specific letter $a$ obtained in (2a), prepare the input for $M_{g_a}$: copy $w_1, \ldots, w_n$ from $R_1, \ldots, R_n$ into the first $n$ input registers of $M_{g_a}$, copy $k$ into the $(n+1)$-th input register, copy $\ell$ into the $(n+2)$-th input register. Run $M_{g_a}$. If it diverges, $M_h$ diverges (correct: the recursive unfolding requires $g_a(w, v_{\text{prefix}}, h(w, v_{\text{prefix}}))$ to be defined at every partial prefix of $v$). If it halts, overwrite $\ell$ with its output. (2c) Append $a$ to register $k$ (using the basic register-machine "write $a$" instruction). (2d) Return to (2a). The branching in (2a) between $\varepsilon$ and each $a \in \Sigma$ is a hard-wired finite case distinction: $|\Sigma| + 1$ branch targets, one per letter plus one for the $\varepsilon$ branch, as in the standard register-machine read instruction. *Phase 3: emit output.* When the loop exits (because $v^*$ became empty), copy $\ell$ into register $0$ and halt. [claim:On input $(w, v)$ with $v = a_1 a_2 \cdots a_p$, if the recursive unfolding of $h$ is defined up to argument $v$, then $M_h$ halts with output $h(w, v)$; otherwise $M_h$ diverges at exactly the point of undefinedness] We argue by induction on $p = |v|$. *Base $p = 0$ ($v = \varepsilon$).* Phase 0 sets $k := \varepsilon$, $v^* := \text{rev}(\varepsilon) = \varepsilon$. Phase 1 attempts to compute $f(w)$: if undefined, $M_h$ diverges here (matching $h(w, \varepsilon) = f(w)$ undefined); if defined, $\ell = f(w)$. Phase 2's first iteration reads $v^*$, which is $\varepsilon$, exits the loop immediately. Phase 3 emits $\ell = f(w) = h(w, \varepsilon)$. *Inductive step $p \ge 1$.* Write $v = v' a_p$ with $|v'| = p - 1$. By the Phase 0 reversal, $v^* = \text{rev}(v) = a_p a_{p-1} \cdots a_1$. The first iteration of Phase 2 reads the last letter of $v^*$, which is $a_1$; let us trace the loop. Define the *loop invariant* $I_t$ at the start of the $(t+1)$-th iteration of Phase 2: \begin{align*} k &= a_1 a_2 \cdots a_t, \qquad v^* = a_p a_{p-1} \cdots a_{t+1}, \qquad \ell = h(w, a_1 \cdots a_t), \end{align*} provided $h(w, a_1 \cdots a_t)$ is defined (if any intermediate $h$-value is undefined, the machine has already diverged in a prior iteration, matching the undefinedness of $h(w, v)$). $I_0$ holds at the start of iteration $1$ because Phase 1 sets $\ell = f(w) = h(w, \varepsilon)$, Phase 0 sets $k = \varepsilon$, and $v^* = a_p \cdots a_1$. If $I_t$ holds with $t < p$, step (2a) reads $a_{t+1}$ off $v^*$, leaving $v^* = a_p \cdots a_{t+2}$. Step (2b) runs $M_{g_{a_{t+1}}}$ on inputs $(w, k, \ell) = (w, a_1 \cdots a_t, h(w, a_1 \cdots a_t))$. By definition of $h$, this equals $g_{a_{t+1}}(w, a_1 \cdots a_t, h(w, a_1 \cdots a_t)) = h(w, a_1 \cdots a_{t+1})$. If this is undefined, $M_h$ diverges here, matching undefinedness of $h(w, v)$ at the recursive unfolding step $t + 1 \le p$. If defined, $\ell$ becomes $h(w, a_1 \cdots a_{t+1})$. Step (2c) appends $a_{t+1}$ to $k$, making $k = a_1 \cdots a_{t+1}$. These match $I_{t+1}$. At $t = p$, step (2a) reads $v^*$ which is empty, and the loop exits. Then $\ell = h(w, a_1 \cdots a_p) = h(w, v)$, and Phase 3 emits this value. [/claim] Hence $h \in \mathcal{C}$. [/step] [step:Prove L3 — closure under minimisation] Let $f : \mathbb{W}^{n + 1} \rightharpoonup \mathbb{W}$ be computable with witness machine $M_f$. The function $\mu f : \mathbb{W}^n \rightharpoonup \mathbb{W}$ is defined by \begin{align*} (\mu f)(w) &= \min\{v \in \mathbb{W} : f(w, v) = \varepsilon \text{ and } f(w, v') \downarrow \text{ for all } v' < v\}, \end{align*} where $<$ is the shortlex order on $\mathbb{W}$ and "min" refers to the shortlex-minimum, which exists whenever the set is non-empty because $(\mathbb{W}, <)$ is well-ordered (see [Shortlex Order and Computable Successor](/theorems/1815)). If the set is empty (either because $f(w, v)$ is undefined at some $v$ before any $\varepsilon$ is found, or because no $\varepsilon$ value is ever produced), then $(\mu f)(w)$ is undefined. We construct a machine $M_{\mu f}$ using a scratch register $k$ that enumerates $\mathbb{W}$ in shortlex order, starting at $\varepsilon$ and using the computable successor $s : \mathbb{W} \to \mathbb{W}$ whose computability is established in [Shortlex Order and Computable Successor](/theorems/1815). *Register layout.* Input registers $0, \ldots, n - 1$ hold $w_1, \ldots, w_n$; we use scratch registers $R_1, \ldots, R_n$ to save a master copy, scratch register $k$ for the candidate, and we call $M_f$ and $M_s$ as sub-routines with their working registers disjoint from these (achievable by renaming register indices in $M_f$ and $M_s$). *Phase 0: save inputs.* Copy $w_1, \ldots, w_n$ from registers $0, \ldots, n-1$ into $R_1, \ldots, R_n$. Initialise $k := \varepsilon$ (erase $k$). *Phase 1: main loop.* Each iteration: (1a) Restore $w_1, \ldots, w_n$ from $R_1, \ldots, R_n$ into the first $n$ input registers of $M_f$, and copy $k$ into the $(n+1)$-th input register. Run $M_f$. If $M_f$ diverges, $M_{\mu f}$ diverges (correct: for $(\mu f)(w)$ to be defined, $f(w, v')$ must be defined for every $v' \le $ the minimising $v$; divergence at the current $k$ means $f(w, k)$ is undefined, so either $k$ is not bounded above by the minimiser, or no minimiser exists). If $M_f$ halts, examine its output. (1b) If the output of $M_f$ is $\varepsilon$, copy $k$ into register $0$ and halt. By the loop invariant below, $k$ at this point is the shortlex-least $v$ with $f(w, v) = \varepsilon$, i.e. $(\mu f)(w) = k$. (1c) If the output is non-empty, replace $k$ by $s(k)$ using the computable successor $M_s$ (established in [Shortlex Order and Computable Successor](/theorems/1815)): copy $k$ into $M_s$'s input register, run $M_s$, copy its output back into $k$. Return to (1a). The test "output is $\varepsilon$" in (1b) vs. "non-empty" in (1c) is the standard read-result case distinction on $M_f$'s output register: read the last letter once; if the read returns $\varepsilon$ the register was empty (halt), otherwise it returned some $a \in \Sigma$ (proceed; first write $a$ back to restore the output register before moving on, though actually in our context the output register of $M_f$ is going to be overwritten next iteration anyway, so we may just discard). [claim:The loop in Phase 1 maintains the invariant "at the start of the iteration, $k$ is the shortlex-least word $v$ such that $f(w, v) \downarrow$ and $f(w, v)$ has not yet been observed to be $\varepsilon$, and for every $v' < k$ we have $f(w, v') \ne \varepsilon$ (and $f(w, v') \downarrow$)"] The initial iteration starts with $k = \varepsilon$, the shortlex-minimum, and no previous values of $f$ have been queried, so the invariant holds vacuously (the set $\{v' : v' < \varepsilon\}$ is empty). If the invariant holds at the start of an iteration, step (1a) evaluates $f(w, k)$. Three outcomes: - $f(w, k)$ diverges: by the invariant, $f(w, v') \downarrow$ and $f(w, v') \ne \varepsilon$ for all $v' < k$. Since $f$ fails to be defined at $k$, the minimisation definition requires $(\mu f)(w)$ to be undefined (there is no $v$ with $f(w, v) = \varepsilon$ and $f$ defined on all smaller inputs, because at $k$ itself $f$ is undefined and $k$ is not greater than any such putative $v$ — more precisely, for $(\mu f)(w) = v$ we'd need $f(w, k) \downarrow$ either with $k = v$ where $f$ value is $\varepsilon$, or $k < v$ where $f$ value is arbitrary defined — but here $f$ is undefined at $k$, so neither works). $M_{\mu f}$ correctly diverges. - $f(w, k) = \varepsilon$: by the invariant, for every $v' < k$ we have $f(w, v') \downarrow$ and $f(w, v') \ne \varepsilon$. So $k$ is the shortlex-least $v$ with $f(w, v) = \varepsilon$ and $f(w, v') \downarrow$ for all $v' < v$. Hence $k = (\mu f)(w)$, and step (1b) emits it. - $f(w, k)$ is defined and non-empty: the invariant is updated to "$k' := s(k)$" in step (1c). Note $s(k)$ is the shortlex-successor of $k$, so words strictly less than $s(k)$ are precisely words $\le k$. For each such $v' \le k$ the invariant previously required $f(w, v') \downarrow$ and $f(w, v') \ne \varepsilon$ (for $v' < k$ by the old invariant, and for $v' = k$ by the current iteration's computation). So the invariant rewrites to $k'$ correctly. By induction on the iteration index, the invariant is maintained. [/claim] [claim:If $(\mu f)(w) = v_0$, the loop exits at iteration where $k = v_0$, after finitely many iterations; if $(\mu f)(w)$ is undefined, the loop does not emit a value (it either diverges at some iteration or never terminates)] *If $(\mu f)(w) = v_0$.* By definition $f(w, v') \downarrow$ for every $v' \le v_0$ and $f(w, v_0) = \varepsilon$. The loop enumerates $k = \varepsilon, s(\varepsilon), s(s(\varepsilon)), \ldots$, and by [Shortlex Order and Computable Successor](/theorems/1815) iterated application of $s$ starting from $\varepsilon$ visits every element of $\mathbb{W}$ in shortlex order, and in particular visits $v_0$ after finitely many iterations (precisely $\#(v_0)$ iterations, where $\#$ is the order isomorphism $\mathbb{W} \to \mathbb{N}$). At the iteration where $k = v_0$, step (1a) returns $\varepsilon$ and step (1b) halts with output $v_0$. *If $(\mu f)(w)$ is undefined.* Two cases: either there is a shortlex-least $v^\dagger$ at which $f(w, v^\dagger) \uparrow$, in which case the loop enumerates up to $k = v^\dagger$ (after $\#(v^\dagger)$ iterations) and diverges in step (1a); or $f(w, v) \downarrow$ and is non-empty for every $v$, in which case the loop runs forever without emitting. Either way $M_{\mu f}$ does not halt, matching the undefinedness of $(\mu f)(w)$. [/claim] Hence $\mu f \in \mathcal{C}$. [/step] [step:Conclude by tree induction] Combining L0 (Step 3), L1 (Step 4), L2 (Step 5), and L3 (Step 6) with the reduction in Step 1: by induction on the height of a recursion tree $(T, \ell)$, the function $f_{T, \ell}$ is computable. Since every partial recursive function arises as $f_{T, \ell}$ for some recursion tree by [Recursive Functions via Trees](/theorems/1816), every partial recursive function is computable. That is, $\mathcal{R} \subseteq \mathcal{C}$, which is the theorem. [/step]