Forme normale de Kleene et fonction universelle

Configurations. On code une configuration $(\ell, r)$ par l'entier $2^\ell 3^{\rho(r)}$, où $\rho(r) = \prod_i p_i^{r(i)}$, produit fini sur les $i$ tels que $r(i) \neq 0$. Par l'unicité de la décomposition en facteurs premiers (Nombres premiers, (ii)), $(\rho(r))_i = r(i)$ pour tout $i$ : le code détermine la configuration.

Dans ce codage, $\mathrm{INC}(i)$ multiplie $\rho(r)$ par $p_i$ ; $\mathrm{DEC}(i, j)$ teste si $p_i$ divise $\rho(r)$, et, si oui, divise par $p_i$.

Une étape. Soit $\mathrm{Et}(e, c)$ défini ainsi, avec $\ell = (c)_0$, $\rho = (c)_1$ et $L = \mathrm{lg}(e)$ : si $\ell \geqslant L$, $\mathrm{Et}(e, c) = c$. Sinon, soit $k = (e)^\ell$ le code de l'instruction $I_\ell$ de $P_e$.

Si $k$ est pair et $i = k/2$, on pose $\mathrm{Et}(e, c) = 2^{\ell+1} 3^{\rho p_i}$. Si $k$ est impair, avec $i = (k - 1)_0 \mathbin{\dot{-}} 1$ et $j = (k - 1)_1$, on pose $\mathrm{Et}(e, c) = 2^{\ell+1} 3^{q(\rho, p_i)}$ si $p_i \mid \rho$, et $\mathrm{Et}(e, c) = 2^j 3^{\rho}$ sinon.

C'est une définition par cas, à partir des fonctions primitives récursives de Clôture et de Codages ; $\mathrm{Et}$ est primitive récursive. Si $c$ code une configuration non terminale de $P_e$, $\mathrm{Et}(e, c)$ code la configuration suivante ; si elle est terminale, elle ne change plus.

Le calcul. Posons $\mathrm{Ini}(x) = 3^{p_1^{x_1} \cdots p_n^{x_n}}$, code de la configuration initiale, puis, par récurrence primitive sur $t$, $$\begin{aligned} \mathrm{Cf}(e, x, 0) &= \mathrm{Ini}(x), \\ \mathrm{Cf}(e, x, t + 1) &= \mathrm{Et}\big(e, \mathrm{Cf}(e, x, t)\big). \end{aligned}$$ Par récurrence sur $t$, $\mathrm{Cf}(e, x, t)$ code la configuration atteinte après $t$ étapes du calcul de $P_e$ sur $x$, ou la configuration terminale si le calcul s'est arrêté avant.

On pose $T_n(e, x, t) \iff (\mathrm{Cf}(e, x, t))_0 \geqslant \mathrm{lg}(e)$, « le calcul est arrêté au temps $t$ », et $U_n(e, x, t) = \big((\mathrm{Cf}(e, x, t))_1\big)_0$, contenu de $R_0$. Si le calcul s'arrête, $\mu t\, T_n(e, x, t)$ est le nombre de ses étapes, et $U_n$ lit le contenu final de $R_0$ ; sinon, aucun $t$ ne vérifie $T_n$, et les deux membres sont indéfinis.

(i), (ii) et (iii) en découlent : le second membre est une fonction récursive de $(e, x)$, obtenue par une seule minimisation, et toute fonction récursive est l'une des $\varphi_e^{(n)}$ par Récursive ⇒ machine.