Proposition 2Fonctions primitives récursives

Codage des suites finies

Comme au point (iii) de l'extension par témoins, on code une suite finie $(k_0, \dots, k_{m-1})$ d'entiers, vue comme un mot dont les lettres sont des entiers, par l'entier $\langle k_0, \dots, k_{m-1} \rangle,$ défini par récurrence sur $m$ : la suite vide a pour code $\langle\, \rangle = 0$ , et $\langle k_0, \dots, k_m \rangle = 2^{\langle k_0, \dots, k_{m-1} \rangle}\, (2k_m + 1).$

On note $p_0 = 2$ , $p_1 = 3$ , $p_2 = 5$ , … les nombres premiers rangés par ordre croissant, et, pour $x \geqslant 1$ , $(x)_i$ l'exposant de $p_i$ dans la décomposition de $x$ (Nombres premiers) ; on convient que $(0)_i = 0$ .

Énoncé

(i) La fonction $i \mapsto p_i$ est primitive récursive, ainsi que $(x, i) \mapsto (x)_i$ .

(ii) Tout entier est le code d'une unique suite finie.

(iii) Les fonctions suivantes sont primitives récursives : l'ajout $\mathrm{aj}(N, k) = 2^N(2k + 1)$ , qui ajoute la lettre $k$ à la fin de la suite de code $N$ ; pour $N \geqslant 1$ , le code $\mathrm{dbt}(N)$ de la suite privée de son dernier terme et ce dernier terme $\mathrm{dr}(N)$ , prolongés par $\mathrm{dbt}(0) = \mathrm{dr}(0) = 0$ ; la longueur $\mathrm{lg}(N)$ de la suite de code $N$ ; son terme de rang $j$ , noté $(N)^j$ pour $j < \mathrm{lg}(N)$ ; et la concaténation $\mathrm{conc}(M, N)$ , code de la suite de code $M$ suivie de la suite de code $N$ .

Démonstration

(i) Soit $v$ un nombre premier et $N = v! + 1$ . Par le point (ii) de Nombres premiers, $N$ a un diviseur premier $q \leqslant N$ . Si l'on avait $q \leqslant v$ , $q$ diviserait $v!$ , donc $N - v! = 1$ , ce qui est absurde ; ainsi $v < q \leqslant v! + 1$ .

Le nombre premier qui suit $v$ est donc $\mu z < v! + 2\ \big(z > v \wedge z \text{ premier}\big),$ fonction primitive récursive de $v$ par les points (iii) à (v) de Clôture. Comme $p_0 = 2$ et $p_{i+1}$ est le premier qui suit $p_i$ , la fonction $i \mapsto p_i$ s'obtient par récurrence primitive.

Si $x \geqslant 1$ et $p_i^k \mid x$ , alors $k < 2^k \leqslant p_i^k \leqslant x$ ; l'exposant de $p_i$ est donc le plus petit $k < x$ tel que $p_i^{k+1}$ ne divise pas $x$ , ce qui s'écrit $(x)_i = \mu k < x\ \neg\big(p_i^{k+1} \mid x\big),$ formule qui vaut aussi $0$ pour $x = 0$ .

(ii) L'injectivité est celle du point (iii) de Témoins de Henkin. Pour la surjectivité, raisonnons par récurrence forte sur $N$ . L'entier $0$ code la suite vide. Tout $N \geqslant 1$ s'écrit $2^n(2k + 1)$ avec $n < N$ ; si $n$ code la suite $s$ , alors $N$ code la suite $s$ suivie de $k$ .

(iii) L'ajout est primitif récursif par les exemples de Primitives récursives. Pour $N = 2^n(2k + 1) \geqslant 1$ , le code $n$ de la suite privée de son dernier terme et ce dernier terme $k$ valent $\begin{aligned} \mathrm{dbt}(N) &= (N)_0, \\ \mathrm{dr}(N) &= q\big(q(N, 2^{(N)_0}) \mathbin{\dot{-}} 1,\ 2\big), \end{aligned}$ et ces formules donnent $\mathrm{dbt}(0) = \mathrm{dr}(0) = 0$ ; on a $\mathrm{dbt}(N) < N$ si $N \geqslant 1$ .

Les itérés $D(N, 0) = N$ et $D(N, i + 1) = \mathrm{dbt}(D(N, i))$ s'obtiennent par récurrence primitive. Si $N$ code une suite de longueur $m$ , $D(N, i)$ code, pour $i \leqslant m$ , la suite privée de ses $i$ derniers termes, et vaut donc $0$ exactement à partir de $i = m$ ; comme $D(N, i) \leqslant N \mathbin{\dot{-}} i$ tant qu'il est non nul, on a $m \leqslant N$ , et $\mathrm{lg}(N) = \mu i < N + 1\ \big(D(N, i) = 0\big).$

Le terme de rang $j$ est le dernier terme de la suite privée de ses $m - 1 - j$ derniers termes, d'où $(N)^j = \mathrm{dr}\big(D(N, \mathrm{lg}(N) \mathbin{\dot{-}} (j + 1))\big).$

Enfin $\mathrm{conc}(M, N) = C(M, N, \mathrm{lg}(N))$ , où $C(M, N, 0) = M$ et $C(M, N, t + 1) = \mathrm{aj}\big(C(M, N, t), (N)^t\big)$ : on ajoute un à un les termes de la seconde suite.

□

Remarque

Ces codes sont gigantesques : $\langle 1, 1 \rangle = 2^3 \cdot 3 = 24$ , mais une suite de six termes a un code qui s'écrit comme une tour d'exposants. Cela n'a aucune importance ici, où l'on ne demande aux codes que d'exister et d'être manipulés par des fonctions primitives récursives ; l'efficacité des calculs est l'objet d'une autre théorie, la complexité.

Remarque

Deux codages servent dans la suite, chacun là où il est le plus simple. Le code des mots, repris de la démonstration du théorème de complétude, convient aux suites que l'on lit et que l'on prolonge, comme les programmes et les formules. Le codage par exposants, $x = \prod p_i^{(x)_i}$ , convient aux suites dont on modifie un terme quelconque, comme le contenu des registres d'une machine : multiplier ou diviser par $p_i$ change le seul terme de rang $i$ .

Repose sur

Propriétés de clôture des fonctions primitives récursives

Sert à

Aucune fiche de ce graphe ne l'utilise encore.