Définition 1Fonctions primitives récursives

Fonctions primitives récursives

Dans toute la théorie, les entiers sont ceux de ${\mathbb N}$ , construits dans $\mathsf{ZF}$ (Construction de ω), et une fonction d'arité $n \geqslant 1$ est une application de ${\mathbb N^n}$ dans $\mathbb N$ . On note $x = (x_1, \dots, x_n)$ un élément de $\mathbb N^n$ , et $(x, y)$ l'élément de $\mathbb N^{n+1}$ obtenu en ajoutant $y$ à la fin.

Énoncé

Les fonctions de base sont la fonction nulle $Z : x \mapsto 0$ , définie sur $\mathbb N$ , le successeur $S : x \mapsto x + 1$ , et les projections $P^n_i : (x_1, \dots, x_n) \mapsto x_i$ , pour $1 \leqslant i \leqslant n$ .

Composition. Si $f : \mathbb N^m \to \mathbb N$ et $g_1, \dots, g_m : \mathbb N^n \to \mathbb N$ , la composée est la fonction $h : \mathbb N^n \to \mathbb N$ définie par $h(x) = f(g_1(x), \dots, g_m(x)).$

Récurrence primitive. Si $f : \mathbb N^n \to \mathbb N$ et $g : \mathbb N^{n+2} \to \mathbb N$ , il existe une unique fonction $h : \mathbb N^{n+1} \to \mathbb N$ telle que, pour tous $x$ et $y$ , $\begin{aligned} h(x, 0) &= f(x), \\ h(x, y + 1) &= g(x, y, h(x, y)). \end{aligned}$ Sans paramètre, c'est-à-dire pour $n = 0$ , on se donne un entier $a$ et $g : \mathbb N^2 \to \mathbb N$ , et $h : \mathbb N \to \mathbb N$ est définie par $h(0) = a$ et $h(y + 1) = g(y, h(y))$ .

Les fonctions primitives récursives forment le plus petit ensemble de fonctions qui contient les fonctions de base et qui est stable par composition et par récurrence primitive.

Exemples. Sont primitives récursives : l'addition, la multiplication, $(x, y) \mapsto x^y$ , la factorielle, le prédécesseur $\mathrm{pr}$ , nul en $0$ et égal à $x - 1$ si $x \geqslant 1$ , la soustraction tronquée $x \mathbin{\dot{-}} y$ , égale à $x - y$ si $x \geqslant y$ et à $0$ sinon, et les fonctions $\mathrm{sg}$ et $\overline{\mathrm{sg}}$ , définies par $\mathrm{sg}(0) = 0$ , $\overline{\mathrm{sg}}(0) = 1$ , et $\mathrm{sg}(x) = 1$ , $\overline{\mathrm{sg}}(x) = 0$ pour $x \geqslant 1$ .

Démonstration

Le plus petit ensemble existe. Les fonctions d'arité quelconque forment un ensemble, réunion des ensembles d'applications de $\mathbb N^n$ dans $\mathbb N$ pour $n \geqslant 1$ . L'intersection des parties de cet ensemble qui contiennent les fonctions de base et sont stables par les deux opérations a encore ces propriétés, et elle est contenue dans chacune d'elles.

Il en résulte un principe d'induction : une propriété vraie des fonctions de base, et conservée par composition et par récurrence primitive, est vraie de toute fonction primitive récursive, puisque l'ensemble des fonctions primitives récursives qui l'ont est stable et contient les fonctions de base.

Récurrence primitive. Fixons $x$ . Le théorème de définition par récurrence, appliqué à l'ensemble $E = \mathbb N \times \mathbb N$ , à l'élément $(0, f(x))$ et à l'application $(m, v) \mapsto (m + 1, g(x, m, v))$ , fournit une suite $u$ telle que $u(0) = (0, f(x))$ et $u(k + 1) = (m + 1, g(x, m, v))$ si $u(k) = (m, v)$ . Par récurrence, la première composante de $u(k)$ est $k$ ; notant $h(x, k)$ la seconde, on obtient les deux égalités voulues. Toute fonction qui les vérifie coïncide avec $h$ , par récurrence sur $y$ . Le cas sans paramètre est identique.

Exemples. L'addition s'obtient par récurrence primitive à partir de $f = P^1_1$ et de $g(x, y, z) = S(P^3_3(x, y, z))$ , puisque $x + 0 = x$ et $x + (y + 1) = S(x + y)$ (Addition, multiplication).

De même, $x \cdot 0 = Z(x)$ et $x(y + 1) = xy + x$ ; puis $x^0 = S(Z(x))$ et $x^{y+1} = x^y \cdot x$ ; puis $0! = 1$ et $(y + 1)! = y! \cdot S(y)$ , ces deux dernières sans paramètre. Dans chaque cas, la fonction $g$ est une composée de projections et de fonctions déjà obtenues.

Le prédécesseur vérifie $\mathrm{pr}(0) = 0$ et $\mathrm{pr}(y + 1) = y = P^2_1(y, \mathrm{pr}(y))$ . La soustraction tronquée vérifie $x \mathbin{\dot{-}} 0 = x$ et $x \mathbin{\dot{-}} (y + 1) = \mathrm{pr}(x \mathbin{\dot{-}} y)$ .

Enfin $\overline{\mathrm{sg}}(x) = 1 \mathbin{\dot{-}} x$ et $\mathrm{sg}(x) = 1 \mathbin{\dot{-}} (1 \mathbin{\dot{-}} x)$ , où la constante $1$ est la fonction $S \circ Z$ .

□

Remarque

Une fonction primitive récursive est totale, définie en tout point, et se calcule par des boucles dont le nombre de tours est connu avant d'y entrer : pour obtenir $h(x, y)$ , on applique $g$ exactement $y$ fois. C'est ce caractère borné qui fait leur force, puisque tout calcul y termine, et leur limite, que le nœud Ackermann met en évidence.

Remarque

L'erreur la plus répandue est de croire que la récurrence primitive autorise n'importe quelle définition récursive. Elle ne permet de définir $h(x, y + 1)$ qu'à partir de $h(x, y)$ , avec les mêmes paramètres $x$ ; une récurrence qui fait varier le paramètre, comme celle de la fonction d'Ackermann, sort de la classe.

Repose sur

C'est un point de départ.

Sert à

Propriétés de clôture des fonctions primitives récursives Croissance de la fonction d'Ackermann