Fonctions et ensembles récursifs primitifs [C3.I.1]

Les fonctions récursives sont les applications définies sur une partie $S$ d’une puissance cartésienne finie $\mathbb N^n$ de $\mathbb N$ et à valeurs dans $\mathbb N$, et qui correspondent à l’application d’un « algorithme » aux éléments de $S$, c’est-à-dire d’une suite d’instructions et d’opérations qui résultent en un « calcul ». Ces notions d’algorithme et de calcul sont ici intuitives, et la théorie des fonctions récursives a notamment pour objectif d’en donner une formalisation mathématique rigoureuse. Les ensembles récursifs sont les ensembles dont la fonction caractéristique est récursive, autrement dit les sous-ensembles $S$ d’une puissance cartésienne finie $\mathbb N^n$ de $\mathbb N$, pour lesquels il existe un « algorithme » qui détermine si un élément $\overline a=(a_1,\ldots,a_n)$ de $\mathbb N^n$ appartient ou non à $S$. Nous construirons ces notions en plusieurs étapes : les fonctions récursives primitives sont les fonctions récursives basiques, qui correspondent à l’intuition élémentaire de ce qu’est un « calcul », à partir de la fonction successeur de l’arithmétique de Peano, et du principe de récurrence. Il s’avère que toutes les fonctions récursives primitives ainsi définie ne peuvent englober les fonctions qu’on considère comme « calculables » : il faut donc en élargir la définition aux fonctions dites « partielles récursives » (définies seulement sur une partie d’une puissance $\mathbb N^n$). Ainsi, nous pourrons introduire les ensembles récursifs à partir des fonctions partielles récursives, et nous retrouverons parmi les unes et les autres de nombreux exemples de fonctions et d’ensembles naturels, à commencer par l’addition et la multiplication des entiers naturels : la théorie est en quelque sorte une extension de la définition de la structure arithmétique naturelle sur l’ensemble $\mathbb N$, telle qu’on l’obtient à partir du théorème de récurrence.

1.Fonctions récursives primitives

En préambule de cette section, nous rappelons l’énoncé du théorème de récurrence, et dont la démonstration se trouve à la section [Axiomes et structures de l’ensemble $\mathbb N$ :: Définitions par récurrence], à laquelle nous renvoyons au sujet du principe des définitions par récurrence.

Théorème 1 [Théorème de récurrence]
Si \(f:E\to E\) est une application d’un ensemble \(E\) dans lui-même et \(a\in E\), alors il existe une unique application \(g:\mathbb N\to E\) telle que \(g(0)=a\) et \(g(s(n))=f(g(n))\) pour tout \(n\in\mathbb N\).

Les fonctions de base
Les premières fonctions récursives que nous introduisons sont « globales » : elles sont définies sur une puissance cartésienne finie $\mathbb N^n$ de $\mathbb N$, et ceci à partir des fonctions les plus simples possibles :
i) La fonction successeur $s:\mathbb N\to\mathbb N$, $n\mapsto n+1$ (voir [Axiomes et structure de l’ensemble $\mathbb N$ :: L’arithmétique de Peano])
ii) Les projections sur une coordonnée, notées $\pi^n_i:(a_1,\ldots,a_n)\in\mathbb N^n\mapsto a_i$, pour $i=1,\ldots,n$
iii) Les fonctions constantes $c^n_a:\overline x\in\mathbb N^n\mapsto a$, pour $a\in\mathbb N$ donné.
Ces fonctions font intuitivement partie de tous les « calculs » qu’on peut effectuer, ou de tous les « programmes » qu’on peut écrire, à propos des entiers naturels : la fonction successeur permet de passer d’une étape à la suivante et détermine l’ensemble $\mathbb N$, les fonctions constantes correspondent aux paramètres des calculs, et les projections signifient qu’on choisit une variables parmi celles qui ont été sélectionnées pour le calcul.

Remarque 0
Ici, l’ensemble $\mathbb N^0$ est par définition l’ensemble des « $0$-uplets » d’entiers naturels, c’est-à-dire de fonctions de $\emptyset$ dans $\mathbb N$. Il n’en existe qu’une, l’application vide (voir [Produits, applications et relations :: L’application vide]), que nous noterons $*$. En particulier, tout entier naturel $a$ s’identifie à la fonction constante $c^0_a:*\mapsto a$.

Les principes de formation
Les fonctions récursives primitives sont alors construites à partir de ces seules fonctions élémentaires, grâce à deux procédés auxquels nous allons donner un sens mathématique précis :
i) La composition des fonctions : si on applique une fonction récursive à d’autres fonctions récursives, on devrait obtenir une fonction récursive
ii) La récurrence : si on définit une fonction par récurrence à partir de fonctions récursives, on devrait obtenir une fonction récursive.
Ce second procédé est en fait le coeur de la notion de « récursivité », qui en anglais se dit « recursion », c’est-à-dire « récurrence » : les fonctions récursives sont celles qu’on peut essentiellement obtenir à partir d’une procédure « étape-par-étape » assimilée à la récurrence. C’est pourquoi le principe suivant, qui généralise la défintion de l’addition et de la multiplication des entiers, est le fondement de la définition que nous adopterons.

Lemme 1 [Principe de récursivité]
Si $f:\mathbb N^n\to \mathbb N$ et $g:\mathbb N^{n+2}\to\mathbb N$ sont deux applications, alors il existe une unique application $h:\mathbb N^{n+1}\to \mathbb N$ telle que pour tous $\overline a=(a_1,\ldots,a_n)\in\mathbb N^n$ et $b\in\mathbb N$, on ait :
i) $h(\overline a,0)=f(\overline a)$
ii) $h(\overline a,b+1)=g(\overline a,b,h(\overline a,b))$.

Démonstration
La démonstration rigoureuse de ce principe est une généralisation de celle du théorème de récurrence (Théorème 1), que nous reprenons donc ici. Nous procédons en deux temps : pour chaque valeur de $\overline a\in \mathbb N^n$, nous définissons une fonction $h_{\overline a}:\mathbb N\to \mathbb N$, et nous définissons ensuite une fonction $h:\mathbb N^{n+1}\to \mathbb N$ à partir des fonctions $h_{\overline a}$. Soit donc $\overline a\in \mathbb N^n$ un paramètre.

Définition des fonctions $h_{\overline a}$
i) Pour tout entier naturel $b$, il existe une unique fonction $h_{\overline a,b}:[[0,b]]\to \mathbb N$, telle que $h_{\overline a,b}(0)=f(\overline a)$ et $h_{\overline a,b}(i+1)=g(\overline a,i,h_{\overline a,b}(i))$ pour tout $i<b$.
Démontrons-le par récurrence sur $b$. Si $b=0$, il n’existe qu’une seule fonction $h_{\overline a,0}=[[0,0]]=\{0\}$ avec ces propriétés, c’est la fonction constante de valeur $f(\overline a)$ (la seconde condition est vide). Supposons que la propriété est démontrée au rang $b$, et définissons $h_{\overline a,b+1}:[[0,b+1]]\to\mathbb N$ de la manière suivante : pour tout $i<b+1$, on pose $h_{\overline a,b+1}(i):=h_{\overline a,b}(i)$, et $h_{\overline a,b+1}(b+1):=g(\overline a,b,h_{\overline a,b}(b))$. Par construction, on a bien $h_{\overline a,b+1}(0)=f(\overline a)$ et $h_{\overline a,b+1}(i)=g(\overline a,b,h_{\overline a,b+1}(i))$ pour tout $i=0,\ldots,b+1$, en distinguant pour la seconde propriété les cas $i<b+1$ et $i=b+1$. On montre alors facilement que $h_{\overline a,b+1}$ est l’unique fonction de $[[0,b+1]]$ dans $\mathbb N$ ayant ces propriétés, en utilisant sa définition et l’hypothèse de récurrence pour $h_{\overline a,b}$. Par le principe de récurrence, la propriété (i) est démontrée.
ii) Il existe une unique fonction $h_{\overline a}:\mathbb N\to \mathbb N$, telle que $h_{\overline a}(0)=f(\overline a)$ et $h_{\overline a}(b+1)=g(\overline a,b,h_{\overline a}(b))$ pour tout $b\in\mathbb N$.
Avec les notations de (i), définissons en effet $h_{\overline a}$ par $h_{\overline a}(b):=h_{\overline a,b}(b)$ : comme la fonction $h_{\overline a,b}$ est définie sur l’intervalle $[[0,b]]$, la fonction $h_{\overline a}$ est bien définie. Elle possdèe les propriétés énoncées : on a $h_{\overline a}(0)=h_{\overline a,0}(0)=f(\overline a)$ par définition de $h_{\overline a,0}$ et pour tout $b\in\mathbb N$, $h_{\overline a}(b+1)=h_{\overline a,b+1}(b+1)$ (par définition) $=g(\overline a,b,h_{\overline a,b+1}(b))$ (par la propriété (i)) $=g(\overline a,b,h_{\overline a,b}(b))$ (car la restriction de $h_{\overline a,b+1}$ à $[[0,b]]$ est $h_{\overline a,b}$ par (i)) $=g(\overline a,b,h_{\overline a}(b))$, par définition de $h_{\overline a}$ : l’existence de $h_{\overline a}$ est démontrée. Pour l’unicité, supposons qu’une fonction $h’:\mathbb N\to\mathbb N$ possède les mêmes proriétés, c’est-à-dire que $h'(0)=f(\overline a)$ et $h'(b+1)=g(\overline a,b,h'(b))$ pour tout $b\in\mathbb N$ : on démontre alors facilement par récurrence que l’ensemble $\{b\in \mathbb N : h_{\overline a}(b)=h'(b)\}$ est l’ensemble $\mathbb N$ tout entier, donc que $h’=h_{\overline a}$, et $h_{\overline a}$ est unique avec ces propriétés.

Définition de la fonction $h$
On pose alors, pour tous $\overline a\in \mathbb N^n$ et $b\in \mathbb N$, $h(\overline a,b):=h_{\overline a}(b)$. Par définition des fonctions $h_{\overline a}$, la fonction $h$ possède les propriétés de l’énoncé. Supposons alors que $h’:\mathbb N^{n+1}\to \mathbb N$ est une application ayant les mêmes propriétés et soit $\overline a\in \mathbb N^n$ : on a $h'(\overline a,0)=f(\overline a)$ par hypothèse, et $h'(\overline a,b+1)=g(\overline a,b,h'(\overline a,b))$ pour tout $b\in\mathbb N$, si bien que la fonction $h’_{\overline a}:b\in\mathbb N\mapsto h'(\overline a,b)$ possède les mêmes propriétés que $h_{\overline a}$. Par unicité de celle-ci, on a donc $h’_{\overline a}=h_{\overline a}$, autrement dit $h'(\overline a,b)=h(\overline a,b)$ pour tout $b\in\mathbb N$, soit encore $h’=h$, puisque $\overline a$ a été choisi arbitrairement. $\square$

Remarque 1
i) Le principe de récursivité est une généralisation du principe de récurrence à la construction de fonctions à plusieurs variables. Pour construire une fonction $h$ en $n+1$ variables, on utilise un procédé de récurrence sur la dernière valable (les $n$ premières servant de « paramètres »), grâce à deux fonctions auxiliaires. La première fonction $f$, en $n$ variables, donne toutes les valeurs de $h$ lorsque le dernier argument vaut $0$ (étape initiale) à partir de la donnée des paramètres, et la seconde fonction $g$, en $n+2$ variables, permet d’appliquer le principe de définition par récurrence à la valeur suivante de la dernière variable de $h$. En effet, cette valeur $h(\overline a,b+1)$ dépend à travers la fonction $g$ à la fois des paramètres ($\overline a$), de la valeur précédemment calculée $h(\overline a,b)$, et de l’indice $b$ lui-même. Nous avons déjà rencontré des exemples de définitions par récursivité, comme nous le verrons dans l’exemple 1.

Exemple 1
i) L’addition des entiers naturels est définie par le principe de récursivité en choisissant pour $f$ la fonction identique $x\in\mathbb N\mapsto x\in\mathbb N$ (qui est une fonction projection), et pour $g$ la fonction $(x,y,z)\in\mathbb N^3\mapsto s(x)$ (le successeur de $x$). On a bien $h(a,0)=f(a)=a=a+0$ pour tout $a$, et $h(a,b+1)=S(h(a,b))=h(a,b)+1=(a+b)+1$ pour tous $a,b\in\mathbb N$. Notons que $f=\pi_1^1$ et que $g=s\circ \pi^3_1$.
ii) La multiplication des entiers naturels est définie par le principe de récursivité en choisissant pour $f$ la fonction $x\in\mathbb N\mapsto 0$ (qui est une fonction constante), et pour $g$ la fonction $(x,y,z)\in\mathbb N^3\mapsto x+z$. On a bien $h(a,0)=f(a)=0=a\times 0$, et $h(a,b+1)=g(a,b,h(a,b))=a+h(a,b)=a+a.b=a\times (b+1)$ pour tous $a,b\in\mathbb N$. Notons que $f=c_0$ et que $g=\pi^3_1+\pi^3_3$.
iii) L’exponentiation $h:(x,y)\in\mathbb N^2\mapsto x^y$ est définie par le principe de récursivité en choisissant pour $f$ la fonction $x\in\mathbb N\mapsto 1$ et pour $g$ la fonction $(x,y,z)\in\mathbb N^3\mapsto x.z$. En effet, on a $h(a,0)=f(a)=1=a^0$, et $h(a,b+1)=g(a,b,h(a,b))=a.h(a,b)=a.(a^b)=a^{b+1}$ pour tous $a,b\in\mathbb N$. Notons que $f=c_1$ et que $g=\pi^3_1\times \pi^3_3$.

Remarque 2
Les exemples donnés ici sont assez élémentaires, n’utilisant la propriété que pour $n=1$ et omettent certaines variables dans la définition à l’étape de récurrence. La forme générale donnée au principe de récursivité permet de prendre en compte des fonctions d’arité (de nombre de variables) quelconque, et d’envisager tous les procédés qu’on peut « moralement » associer à ce mode de production.

2.L’ensemble des fonctions récursives primitives