Lemme 1Arithmétisation de la syntaxe

Récurrence de valeurs

Soit $p \geqslant 0$ et $f : {\mathbb N^{p+1}} \to \mathbb N$ une fonction. Pour $x \in \mathbb N^p$ et $n \in \mathbb N$ , on note $\bar f(x, n) = \langle f(x, 0), \dots, f(x, n - 1) \rangle$ le code de la suite de ses valeurs avant $n$ , au sens de Codages ; ainsi $\bar f(x, 0) = 0$ . Comme $\mathrm{lg}(\bar f(x, n)) = n$ , on a $(\bar f(x, n))^m = f(x, m)$ pour tout $m < n$ , où $(N, j) \mapsto (N)^j$ est la fonction primitive récursive de Codages, (iii), définie pour tous $N$ et $j$ par la formule qui y est donnée.

Pour une relation $R \subset \mathbb N^{p+1}$ , on note de même $\bar\chi_R$ pour $\overline{\chi_R}$ .

Énoncé

(i) Soit $G : \mathbb N^{p+2} \to \mathbb N$ une fonction primitive récursive. Il existe une unique fonction $f : \mathbb N^{p+1} \to \mathbb N$ telle que, pour tous $x$ et $n$ , $f(x, n) = G\big(x, n, \bar f(x, n)\big),$ et elle est primitive récursive.

(ii) Soit $Q \subset \mathbb N^{p+2}$ une relation primitive récursive. Il existe une unique relation $R \subset \mathbb N^{p+1}$ telle que, pour tous $x$ et $n$ , $R(x, n) \iff Q\big(x, n, \bar\chi_R(x, n)\big),$ et elle est primitive récursive.

C'est le principe de récurrence de valeurs : une fonction dont la valeur en $n$ se calcule, de façon primitive récursive, à partir de toutes ses valeurs en des entiers plus petits que $n$ est primitive récursive.

Démonstration

(i) Existence. Définissons $F : \mathbb N^{p+1} \to \mathbb N$ par récurrence primitive (Primitives récursives) : $\begin{aligned} F(x, 0) &= 0, \\ F(x, n + 1) &= \mathrm{aj}\big(F(x, n), \\ &\qquad\quad G(x, n, F(x, n))\big), \end{aligned}$ où $\mathrm{aj}$ est la fonction d'ajout de Codages. Pour $p = 0$ , c'est la récurrence primitive sans paramètre, avec l'entier initial $0$ . La fonction $f(x, n) = G(x, n, F(x, n))$ est primitive récursive, par composition.

Montrons par récurrence sur $n$ que $F(x, n) = \bar f(x, n)$ . Pour $n = 0$ , les deux membres valent $0$ , code de la suite vide. Si $F(x, n) = \bar f(x, n)$ , alors $G(x, n, F(x, n)) = f(x, n)$ par définition de $f$ , et $\begin{aligned} F(x, n + 1) &= \mathrm{aj}\big(\bar f(x, n), f(x, n)\big) \\ &= \bar f(x, n + 1), \end{aligned}$ puisque l'ajout place $f(x, n)$ à la fin de la suite codée par $\bar f(x, n)$ . Ainsi $f(x, n) = G(x, n, \bar f(x, n))$ pour tous $x$ et $n$ .

Unicité. Soit $f'$ une autre fonction qui vérifie la même égalité, et $x$ fixé. Montrons par récurrence forte sur $n$ que $f'(x, n) = f(x, n)$ : si c'est vrai pour tout $m < n$ , les suites $(f'(x, 0), \dots, f'(x, n - 1))$ et $(f(x, 0), \dots, f(x, n - 1))$ sont égales, donc $\bar f'(x, n) = \bar f(x, n)$ , et les deux égalités donnent $f'(x, n) = f(x, n)$ .

(ii) Appliquons (i) à $G = \chi_Q$ : la fonction $f$ obtenue ne prend que les valeurs $0$ et $1$ , et la relation $R = \{(x, n) : f(x, n) = 1\}$ a pour fonction caractéristique $\chi_R = f$ . Elle est primitive récursive, et $\begin{aligned} R(x, n) &\iff f(x, n) = 1 \\ &\iff Q\big(x, n, \bar\chi_R(x, n)\big). \end{aligned}$ Si $R'$ vérifie la même équivalence, $\chi_{R'}$ vérifie l'égalité de (i) avec $G = \chi_Q$ , donc $\chi_{R'} = f = \chi_R$ par l'unicité de (i).

□

Remarque

Dans toutes les applications de ce chapitre, la fonction $G$ , ou la relation $Q$ , ne lit sa dernière variable $h$ qu'à travers des termes $(h)^m$ pour des entiers $m < n$ ; lorsque $h = \bar f(x, n)$ , ce sont les valeurs $f(x, m)$ . L'erreur la plus répandue est d'oublier cette condition : une définition qui ferait appel à $f(x, 2n)$ pour calculer $f(x, n)$ n'est pas une récurrence de valeurs, et elle peut n'avoir aucune solution, comme $f(n) = f(2n) + 1$ , qui imposerait $f(0) = f(0) + 1$ , ou en avoir plusieurs, comme $f(n) = f(2n)$ . Les entiers $m$ consultés seront toujours des codes de sous-mots propres, plus petits que $n$ par le point (ii) du codage des mots.

Remarque

La récurrence de valeurs ne sort pas de la classe des fonctions primitives récursives, contrairement à la double récurrence qui définit la fonction d'Ackermann. Elle ne fait que réorganiser une récurrence primitive autour de l'historique $\bar f(x, n)$ , que l'on transporte d'une étape à la suivante comme une pile : à chaque étape, on calcule une valeur et on l'ajoute à la fin.

Repose sur

Fonctions primitives récursives

Sert à

Les termes forment un ensemble primitif récursif