Définition 2Calculabilité

Ensembles récursifs et récursivement énumérables

Énoncé

Une partie $A \subset {\mathbb N^n}$ est un ensemble récursif, ou décidable, si c'est une relation récursive. Elle est un ensemble récursivement énumérable s'il existe une relation récursive $R \subset \mathbb N^{n+1}$ telle que $x \in A \iff \exists y\ R(x, y).$

(i) Tout ensemble récursif est récursivement énumérable.

(ii) Un ensemble $A$ est récursif si et seulement si $A$ et son complémentaire sont récursivement énumérables.

(iii) La réunion et l'intersection de deux ensembles récursivement énumérables le sont. Si $g : \mathbb N^m \to \mathbb N^n$ a des composantes récursives totales et si $A$ est récursif, resp. récursivement énumérable, l'image réciproque $g^{-1}(A)$ l'est aussi.

(iv) Si $B \subset \mathbb N^{n+1}$ est récursivement énumérable, sa projection $\{x : \exists y\ (x, y) \in B\}$ l'est aussi.

Démonstration

(i) Si $A$ est récursif, on prend $R(x, y) \iff x \in A$ , qui ne dépend pas de $y$ .

(ii) Si $A$ est récursif, son complémentaire l'est, de fonction caractéristique $1 \mathbin{\dot{-}} \chi_A$ , et (i) conclut. Réciproquement, soit $x \in A \iff \exists y\, R(x, y)$ et $x \notin A \iff \exists y\, R'(x, y)$ . Tout $x$ est dans $A$ ou dans son complémentaire ; par le point (iii) de Fonctions récursives, la fonction $f(x) = \mu y\, \big(R(x, y) \vee R'(x, y)\big)$ est récursive et totale. Si $x \in A$ , aucun $y$ ne vérifie $R'(x, y)$ , donc $R(x, f(x))$ ; si $x \notin A$ , aucun $y$ ne vérifie $R(x, y)$ . Ainsi $\chi_A(x) = \chi_R(x, f(x))$ , qui est récursive.

(iii) et (iv) On emploie les exposants $(w)_i$ de Codages pour réunir deux témoins en un seul : tout couple $(y, z)$ est égal à $((w)_0, (w)_1)$ pour $w = 2^y 3^z$ . Si $A$ et $A'$ sont donnés par $R$ et $R'$ , $\begin{aligned} &x \in A \cup A' \\ &\quad \iff \exists y\, \big(R(x, y) \vee R'(x, y)\big), \\ &x \in A \cap A' \\ &\quad \iff \exists w\, \big(R(x, (w)_0) \wedge R'(x, (w)_1)\big). \end{aligned}$ Puis $x \in g^{-1}(A) \iff \exists y\, R(g(x), y)$ , et $\chi_{g^{-1}(A)} = \chi_A \circ g$ dans le cas récursif. Enfin, si $(x, y) \in B \iff \exists z\, R(x, y, z)$ , alors $\exists y\, (x, y) \in B \iff \exists w\, R(x, (w)_0, (w)_1)$ .

Toutes les relations écrites entre parenthèses sont récursives par le point (ii) de Fonctions récursives.

□

Remarque

Le complémentaire d'un ensemble récursivement énumérable ne l'est pas toujours : le point (ii) dit précisément que cela n'arrive que pour les ensembles récursifs, et le nœud Arrêt donnera un ensemble récursivement énumérable non récursif. L'asymétrie est celle d'une recherche : on peut constater qu'un témoin existe en le trouvant, jamais qu'il n'existe pas.

Remarque

L'étude systématique de ces ensembles remonte à Emil Post (« Recursively enumerable sets of positive integers and their decision problems », Bulletin of the American Mathematical Society 50, 1944). Le nom s'explique au nœud Caractérisations des r.e. : un ensemble non vide est récursivement énumérable si et seulement si une fonction récursive totale en énumère les éléments.

Repose sur

Fonctions récursives partielles

Sert à

Caractérisations des ensembles récursivement énumérables Indécidabilité du problème de l'arrêt