Chapitre 4 : 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 }
Exercice 2 (corrigé ci-dessous).
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.
Soient A et B deux ensembles récursivement énumérables quelconques.
Exercice 11 (corrigé ci-dessous).
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.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 N → N calculée par p.
Exercice 1 (énoncé ci-dessus).
Exercice 2 (énoncé ci-dessus).
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.
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).
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; }
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) ) | n ∈ N }
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).
pour tout triplet (p, x, t) si h (p, x, t) alors si p(x) ∈ A alors afficher p