Les fonctions récursives sont calculables par machine

Trois faits. Disons qu'un programme mentionne les registres qui figurent dans ses instructions.

(a) Localité. Un programme ne modifie que les registres qu'il mentionne, et son calcul ne dépend que de leur contenu : c'est vrai d'une étape, donc de toutes, par récurrence.

(b) Renommage. Si $\sigma$ est une injection de $\mathbb N$ dans $\mathbb N$, le programme $P^\sigma$, où chaque registre $i$ est remplacé par $\sigma(i)$, fait sur les registres $\sigma(i)$ exactement ce que $P$ fait sur les registres $i$.

(c) Enchaînement. Soit $P$ et $Q$ de longueurs $L$ et $L'$. Le programme $P ; Q$ s'obtient en remplaçant, dans $P$, tout saut vers un numéro $j \geqslant L$ par un saut vers $L$, puis en écrivant à la suite $Q$, dont chaque saut vers $j$ devient un saut vers $j + L$. Son calcul est celui de $P$, suivi, si $P$ s'arrête, de celui de $Q$ à partir de la configuration atteinte ; il s'arrête si et seulement si les deux s'arrêtent.

Macro-instructions. Dans un programme, on réserve un registre $z$ que rien n'incrémente et qui vaut donc toujours $0$ ; alors $\mathrm{DEC}(z, j)$ est un saut inconditionnel vers $j$. Avec lui, on écrit des programmes, enchaînés par (c) :

$\mathrm{EFF}(i)$, qui vide $R_i$ en le décrémentant jusqu'à $0$ ;

$\mathrm{TRANS}(i \to j)$, qui ajoute le contenu de $R_i$ à $R_j$ et vide $R_i$, par une boucle qui décrémente $R_i$ et incrémente $R_j$ ;

$\mathrm{COPIE}(i \to j)$, qui place dans $R_j$ le contenu de $R_i$ sans changer celui-ci : on vide $R_j$ et un registre auxiliaire $t$, on transfère $R_i$ à la fois dans $R_j$ et dans $R_t$, puis $R_t$ dans $R_i$.

Appel. Soit $Q$ un programme qui calcule $g : \mathbb N^k \rightharpoonup \mathbb N$ et ne mentionne que des registres d'indices inférieurs à $m$, avec $m > k$. Pour des registres $a_1, \dots, a_k$ et $b$ et un décalage $s$, l'appel $\mathrm{APP}(Q ; a_1, \dots, a_k \to b)$ vide les registres $s, \dots, s + m - 1$, copie $R_{a_l}$ dans $R_{s+l}$ pour $l = 1, \dots, k$, exécute $Q$ renommé par $i \mapsto s + i$, puis copie $R_s$ dans $R_b$.

Par (a) et (b), le programme renommé opère sur le bloc $s, \dots, s + m - 1$ comme $Q$ sur une configuration initiale : l'appel s'arrête si et seulement si $g(R_{a_1}, \dots, R_{a_k})$ est défini, et place alors cette valeur dans $R_b$. On choisit toujours $s$, $t$ et $z$ au-delà de tous les registres qui portent des données, les registres $t$ et $z$ distincts entre eux et hors du bloc $s, \dots, s + m - 1$, si bien qu'un appel ne modifie que $R_b$ et des registres auxiliaires.

Récurrence sur les fonctions récursives. L'ensemble des fonctions partielles calculables par machine contient les fonctions de base et il est stable par les trois opérations ; il contient donc toutes les fonctions récursives.

Base. Le programme vide calcule $Z$, puisque $R_0$ vaut $0$ au départ. $\mathrm{TRANS}(1 \to 0)$ suivi de $\mathrm{INC}(0)$ calcule $S$, et $\mathrm{TRANS}(i \to 0)$ calcule $P^n_i$.

Composition. Pour $h = f(g_1, \dots, g_m)$, on enchaîne les appels qui placent $g_l(R_1, \dots, R_n)$ dans des registres neufs $y_l$, puis l'appel qui place $f(R_{y_1}, \dots, R_{y_m})$ dans $R_0$. Si l'un des $g_l(x)$ n'est pas défini, ou si $f$ ne l'est pas en $(g_1(x), \dots, g_m(x))$, l'appel correspondant ne s'arrête pas.

Récurrence primitive. Pour $h(x, 0) \simeq f(x)$ et $h(x, y + 1) \simeq g(x, y, h(x, y))$, avec $y$ dans $R_{n+1}$, on place d'abord $f(x)$ dans un registre neuf $v$.

Puis, tant que $\mathrm{DEC}(n + 1, \cdot)$ trouve $R_{n+1}$ non nul, on place $g(R_1, \dots, R_n, R_c, R_v)$ dans un registre neuf $v'$, on vide $R_v$, on transfère $R_{v'}$ dans $R_v$ et l'on incrémente un compteur $R_c$, initialement nul ; enfin on transfère $R_v$ dans $R_0$.

Au début du tour de rang $k$, compté à partir de $0$, $R_c = k$ et $R_v = h(x, k)$, par récurrence sur $k$ ; la boucle fait $y$ tours. Sans paramètre, on place d'abord l'entier $a$ dans $R_v$ par $a$ instructions $\mathrm{INC}(v)$.

Minimisation. Pour $h(x) \simeq \mu y\, [f(x, y) = 0]$ : on place $f(R_1, \dots, R_n, R_c)$ dans un registre neuf $w$ ; si $\mathrm{DEC}(w, \cdot)$ trouve $R_w$ nul, on transfère $R_c$ dans $R_0$ et l'on s'arrête ; sinon on incrémente $R_c$ et l'on recommence. Le calcul s'arrête si et seulement si $f(x, 0), \dots, f(x, y)$ sont définis, les premiers non nuls et le dernier nul, et il rend alors $y$ : c'est exactement la définition de la minimisation.