Théorème s-m-n

Soit $\delta = m + n + 1$ ; ce registre est vide dans la configuration initiale de $y$, et aucune des instructions ci-dessous ne l'incrémente. On fait précéder le programme $P_e$ d'indice $e$, décodé comme au nœud Kleene, d'un préfixe $Q_x$ qui transforme la configuration initiale de $y$ en celle de $(x, y)$.

Pour $k = n, n - 1, \dots, 1$, dans cet ordre, $Q_x$ transfère $R_k$ dans $R_{m+k}$, par la boucle $\mathrm{DEC}(k, \cdot)$, $\mathrm{INC}(m + k)$, $\mathrm{DEC}(\delta, \cdot)$ ; comme $m \geqslant 1$, les registres d'arrivée sont vides quand on y transfère, ceux d'indice supérieur à $k$ ayant déjà été vidés. Puis $Q_x$ contient, pour $k = 1, \dots, m$, $x_k$ instructions $\mathrm{INC}(k)$.

Le programme $P_{s(e, x)}$ est $Q_x$ suivi de $P_e$, dont chaque saut $\mathrm{DEC}(i, j)$ devient $\mathrm{DEC}(i, j + L_0)$, où $L_0$ est la longueur de $Q_x$ ; un saut de $P_e$ vers $j \geqslant \mathrm{lg}(e)$ devient un saut au-delà de la fin, et arrête encore le calcul. Le calcul de $P_{s(e, x)}$ sur $y$ est celui de $P_e$ sur $(x, y)$, précédé de celui de $Q_x$, qui s'arrête toujours.

Le code $s(e, x)$ est primitif récursif. Le code de $Q_x$ s'obtient par la fonction d'ajout de Codages, les $x_k$ instructions $\mathrm{INC}(k)$ par récurrence primitive sur $x_k$. Le code du programme décalé s'obtient par récurrence primitive sur le rang, en ajoutant, pour chaque terme $c = (e)^l$, le terme $c$ s'il est pair, et $2^{i+1}3^{j + L_0} + 1$ sinon, avec $i = (c - 1)_0 \mathbin{\dot{-}} 1$ et $j = (c - 1)_1$. On conclut par la concaténation.