Chapitre 4 : Ensembles récursivement énumérables

TD : Ensembles récursivement énumérables

Exercice 1 (corrigé ci-dessous). Soit une fonction f calculable, un ensemble B, et son image réciproque par f, A :

A = f -1 (B) = { x | f (x) appartient à B }

  1. A-t-on : ( B décidable ) implique ( A décidable ) ?
  2. Montrer que ( B récursivement énumérable ) implique ( A récursivement énumérable ).

Exercice 2 (corrigé ci-dessous).

  1. Soit E un ensemble récursivement énumérable, énuméré par une fonction calculable f strictement croissante ; montrer que E est décidable.
  2. En déduire que tout ensemble récursivement énumérable infini contient un ensemble décidable infini.

Exercice 3 (corrigé ci-dessous). Soit E l'ensemble Val ( f ), où f est calculable partielle. Montrer que E est récursivement énumérable, c'est-à-dire écrire une procédure qui "affiche" tous les éléments de E. Conseil : utiliser le temps.

Exercice 4 (corrigé ci-dessous). Montrer que tout ensemble E récursivement énumérable et infini peut être énuméré sans répétition, c'est-à-dire construire g calculable et injective telle que E = Val ( g ).

Exercice 10 (corrigé ci-dessous). Soient A et B deux ensembles décidables quelconques.

  1. Est-on sûr que le complémentaire de A est décidable ?
  2. Est-on sûr que l'union de A et B est décidable ?
  3. Est-on sûr que l'intersection de A et B est décidable ?

Soient A et B deux ensembles récursivement énumérables quelconques.

  1. Est-on sûr que le complémentaire de A est récursivement énumérable ?
  2. Est-on sûr que l'union de A et B est récursivement énumérable ?
  3. Est-on sûr que l'intersection de A et B est récursivement énumérable ?

Exercice 11 (corrigé ci-dessous).

  1. Soit A un ensemble décidable de couples d'entiers (x, y) ; montrer que la (première) projection de A, à savoir :

    E = { x | il existe y tel que (x, y) appartient à A }

    est récursivement énumérable.
  2. Montrer que réciproquement tout ensemble récursivement énumérable est la projection d'un ensemble décidable.

Exercice 20 (corrigé ci-dessous). (Devoir 1999). A tout ensemble d'entiers A on associe deux ensembles de procédures, notés P ( A ) et Q ( A ), et définis par :

Note : Val ( p ) est une abréviation pour Val ( f ), où f désigne la fonction NN calculée par p.

  1. Soit B le complémentaire de A ; comparer P ( A ) et Q ( B ).
  2. Quels sont les ensembles décidables A tels que P ( A ) soit récursivement énumérable ?
  3. Quels sont les ensembles décidables A tels que Q ( A ) soit récursivement énumérable ?

Solutions

Exercice 1 (énoncé ci-dessus).

  1. C'est vrai si f est totale : pour décider si x appartient à A, il suffit de tester si f (x) appartient à B. Sinon on peut simplement affirmer que A est récursivement énumérable, comme ci-dessous.
  2. B = domaine ( g ), donc A = domaine ( gf ).

Exercice 2 (énoncé ci-dessus).

  1. Si f est strictement croissante, la fonction caractéristique de E = Val ( f ) est calculable :

    int f (int n) { … }
    int fc (int x) {
      int n, y;
      for (n = 0; ; n++) {
        y = f(n);
        if (x == y) return 1;
        if (x < y) return 0;
      }
    }
    

    Remarque. Le résultat reste vrai en supprimant le mot "strictement", mais alors il faut distinguer le cas où E est fini, avec les complications qui s'en suivent.

  2. Pour extraire un ensemble décidable infini d'un ensemble récursivement énumérable infini, énuméré par f, il suffit d'extraire une sous-suite strictement croissante de la suite des f(n) :

    int f (int n) { … }
    int y, max = 0;
    for (n = 0; ; n++) {
      y = f(n);
      if (max < y) {
        max = y;
        afficher f(n);
      }
    }
    

    L'ensemble A énuméré par cette procédure est manifestement un sous-ensemble de E ; si E est infini, il n'est pas borné, donc on passe une infinité de fois "à l'intérieur" du if, et A est infini ; enfin, par construction, A est énuméré en ordre croissant, donc est décidable.

Exercice 3 (énoncé ci-dessus). Algorithme d'énumération en version abrégée :

pour tout couple (x, t)
  si h (f, x, t) alors afficher f(x)

Note : chaque élément de Val ( f ) est affiché une infinité de fois, ce qui est autorisé. L'exercice suivant montre comment éviter ces répétitions, si on le souhaite.

Exemple. Supposons que les temps de calcul sont donnés par la table suivante ( f (3) et f (5) ne sont pas définis) :

f (0) f (1) f (2) f (3) f (4) f (5) f (6) f (7) f (8)
Temps de calcul 4 2 5 infini 1 infini 2 5 3

Voici le début du parcours des couples ( x, t ) :

0, 0 1, 0 0, 1 2, 0 1, 1 0, 2 3, 0 2, 1 1, 2 0, 3 4, 0 3, 1 2, 2 1, 3 0, 4
Affichage f (1) f (1) f (0)
5, 0 4, 1 3, 2 2, 3 1, 4 0, 5 6, 0 5, 1 4, 2 3, 3 2, 4 1, 5 0, 6 7, 0 6, 1
Affichage f (4) f (1) f (0) f (4) f (1) f (0)
5, 2 4, 3 3, 4 2, 5 1, 6 0, 7 8, 0 7, 1 6, 2 5, 3 4, 4 3, 5 2, 6 1, 7 0, 8
Affichage f (4) f (2) f (1) f (0) f (6) f (4) f (2) f (1) f (0)

Exercice 4 (énoncé ci-dessus). Algorithme d'énumération en version abrégée :

int f (int n) { … }
int nouveau (int n) {
  int i, x = f(n);
  for (i = 0; i < n; i++)
    if (x == f(i)) return 0;
  return 1;
}
for (n = 0; ; n++)
  if (nouveau (n)) afficher f(n);

Remarque : si l'on modifie la procédure nouveau pour qu'elle filtre les éléments supérieurs à tous les précédents (au lieu des éléments différents de tous les précédents), en remplaçant le test d'égalité (==) par un test de comparaison (<=) :

int nouveau (int n) {
  int i, x = f(n);
  for (i = 0; i < n; i++)
    if (x <= f(i)) return 0;
  return 1;
}

l'ensemble A énuméré par cet algorithme est un sous-ensemble de E énuméré en ordre (strictement) croissant, comme dans l'exercice 2 (A est décidable, et si E est infini, A l'est aussi).

Exercice 10 (énoncé ci-dessus). Les réponses (positives) à la première partie sont évidentes, et permettent de réviser les rapports entre opérateurs ensemblistes et opérateurs logiques.

Non, le complémentaire d'un ensemble récursivement énumérable n'est pas forcément récursivement énumérable, c'est l'objet de la section 3 du cours.

Oui, l'union de deux ensembles récursivement énumérables est récursivement énumérable ; voici une procédure d'énumération de l'union de deux ensembles énumérés respectivement par f et g :

int f (int n) { … }
int g (int n) { … }
int enumUnion (int n) {
  if (n % 2 == 0)
    return f (n / 2);
  else
    return g (n / 2);
}

Ou, plus simplement :

for (i = 0; ; i++) {
  afficher f(i);
  afficher g(i);
}

Oui, l'intersection de deux ensembles récursivement énumérables est récursivement énumérable ; voici une procédure simplifiée d'affichage de l'intersection de deux ensembles énumérés respectivement par f et g :

pour chaque couple (i, j)
  si f(i) = g(j) alors afficher f(i);

On peut aussi utiliser les fonctions semi-caractéristiques :

int scA (int x) { … }
int scB (int x) { … }
int scIntersection (int x) {
  int y = scA(x);
  return scB(x);
}

L'intersection de A et B est donc semi-décidable, et par conséquent récursivement énumérable.

Exercice 11 (énoncé ci-dessus).

  1. Voici une procédure (en format abrégé) qui énumère les éléments de E :

    pour tout couple (x, y)
      si (x, y) ∈ A alors afficher x
    

    Note : on a le droit d'écrire une procédure qui utilise le test " ( x, y ) ∈ A " car A est décidable.

    Ou bien voici une procédure qui calcule la fonction semi-caractéristique de E, en utilisant la fonction caractéristique de A :

    int fcA (int x, int y) { … }
    int sc (int x) {
      int y;
      for (y = 0; ; y++)
        if ( fcA (x, y) ) return 1;
    }
    
  2. E est énuméré par une fonction calculable totale f, c'est donc la (seconde) projection du graphe G de f, à savoir :

    G = { ( n, f (n) ) | nN }

    et G est décidable : tester si (x, y) appartient à G équivaut à tester si y = f (x) (si f n'est pas totale, ce test peut boucler, mais ici f est totale).

Exercice 20 (énoncé ci-dessus).

  1. p appartient à P ( A ) si et seulement si il existe x tel que p (x) appartient à A ; donc par négation p appartient au complémentaire de P ( A ) si et seulement si pour tout x, p (x) appartient à B. On en conclut que P ( A ) et Q ( B ) sont complémentaires.
  2. Si A est décidable, P ( A ) est récursivement énumérable ; voici un algorithme qui l'énumère :
    pour tout triplet (p, x, t)
      si h (p, x, t) alors
        si p(x) ∈ A alors afficher p
    
  3. Si A est décidable, et si Q ( A ) est récursivement énumérable, son complémentaire aussi, d'après les deux questions précédentes ; donc Q ( A ) est décidable, et d'après le théorème de Rice, est trivial. Ce n'est pas fini :