Définition 1Calculabilité

Fonctions récursives partielles

Un calcul peut chercher sans fin un entier qui n'existe pas. Pour en rendre compte, on ajoute aux opérations de Primitives récursives une recherche non bornée, et l'on admet des fonctions qui ne sont pas définies partout.

Énoncé

Une fonction partielle $f : {\mathbb N^n} \rightharpoonup \mathbb N$ est une application d'une partie $D(f)$ de $\mathbb N^n$ , son domaine de définition, dans ${\mathbb N}$ . On écrit $f(x)\!\downarrow$ si $x \in D(f)$ et $f(x)\!\uparrow$ sinon. L'écriture $f(x) \simeq g(x)$ signifie que les deux membres sont indéfinis, ou qu'ils sont définis et égaux. La fonction est totale si $D(f) = \mathbb N^n$ .

La composée $h(x) \simeq f(g_1(x), \dots, g_m(x))$ est définie si et seulement si chaque $g_j(x)$ l'est et si $f$ est définie en $(g_1(x), \dots, g_m(x))$ . La récurrence primitive $h(x, 0) \simeq f(x)$ , $h(x, y + 1) \simeq g(x, y, h(x, y))$ définit $h(x, y + 1)$ si et seulement si $h(x, y)$ est défini et $g$ est définie en $(x, y, h(x, y))$ .

Minimisation. Pour $f : \mathbb N^{n+1} \rightharpoonup \mathbb N$ , on note $\mu y\, [f(x, y) = 0]$ le plus petit entier $y$ tel que $f(x, y) = 0$ et que $f(x, z)$ soit défini et non nul pour tout $z < y$ ; s'il n'y en a pas, $\mu y\, [f(x, y) = 0]$ n'est pas défini.

Les fonctions récursives forment le plus petit ensemble de fonctions partielles qui contient les fonctions de base et qui est stable par composition, récurrence primitive et minimisation. Une relation $R \subset \mathbb N^n$ est récursive si sa fonction caractéristique l'est.

(i) Toute fonction primitive récursive est récursive et totale.

(ii) Les fonctions récursives totales et les relations récursives ont les propriétés de clôture (i) à (v) de Clôture.

(iii) Si $R \subset \mathbb N^{n+1}$ est une relation récursive, la fonction $x \mapsto \mu y\, R(x, y)$ , plus petit $y$ tel que $R(x, y)$ , est récursive ; elle est totale si, pour tout $x$ , un tel $y$ existe.

Démonstration

La récurrence primitive sur des fonctions partielles se ramène au cas total : on adjoint à $\mathbb N$ un élément $\bot$ qui n'est pas un entier, par exemple $\omega$ lui-même, qui n'appartient pas à $\omega$ (Bon ordre sur ℕ), on prolonge $g$ en lui donnant la valeur $\bot$ dès qu'elle n'est pas définie ou qu'un argument vaut $\bot$ , et l'on applique la construction de Primitives récursives dans $\mathbb N \times (\mathbb N \cup \{\bot\})$ , en partant de $(0, \bot)$ si $f(x)\!\uparrow$ ; $h(x, y)$ est indéfini quand la valeur obtenue est $\bot$ .

(i) L'ensemble des fonctions récursives totales contient les fonctions de base, et il est stable par composition et par récurrence primitive, qui ne produisent que des fonctions totales à partir de fonctions totales. Il contient donc toutes les fonctions primitives récursives.

(ii) Les démonstrations de Clôture n'emploient que les fonctions de base, les exemples de Primitives récursives, la composition et la récurrence primitive, appliquées à des fonctions totales. Elles valent mot pour mot pour les fonctions récursives totales.

(iii) La fonction $(x, y) \mapsto 1 \mathbin{\dot{-}} \chi_R(x, y)$ est récursive et totale, et elle s'annule exactement sur $R$ . Comme elle est définie partout, la minimisation donne $\mu y\, R(x, y) \simeq \mu y\, \big[1 \mathbin{\dot{-}} \chi_R(x, y) = 0\big].$

□

Remarque

L'exigence que $f(x, z)$ soit défini pour tout $z < y$ n'est pas un détail. Le procédé de calcul évalue $f(x, 0)$ , puis $f(x, 1)$ , et ainsi de suite ; si l'une de ces évaluations ne termine pas, la recherche ne va jamais plus loin. L'erreur la plus répandue est de définir $\mu y$ comme le plus petit zéro de $f(x, \cdot)$ sans cette condition : la classe obtenue contiendrait des fonctions qu'aucun procédé ne calcule.

Remarque

Une fonction récursive totale peut avoir été construite à l'aide de fonctions partielles ; c'est la fonction obtenue, et non sa construction, qui est totale. Inversement, aucune règle syntaxique simple ne reconnaît les constructions qui donnent des fonctions totales : c'est l'un des visages de l'indécidabilité de l'arrêt.

Repose sur

Fonctions primitives récursives

Sert à

La fonction d'Ackermann est récursive Ensembles récursifs et récursivement énumérables Machines à registres