Chapitre 3 : Récursion et théorème de Rice |
On rappelle que décider a la même signification que calculer, lorsqu'on traite un problème avec seulement deux réponses possibles : oui ou non, vrai ou faux, etc. (un tel problème est souvent appelé problème de décision). Un ensemble d'entiers E est décidable si, par définition, il existe un algorithme (une procédure) pour décider si un entier x appartient ou non à E ; voir le début du chapitre 4 pour des détails.
Exercice 1 (corrigé ci-dessous). Voici une liste d'applications directes du théorème de Rice :
Ecrire explicitement (à l'aide de quantificateurs), dans chaque cas, le prédicat (indécidable) correspondant. Ecrire une procédure contradictoire, qui prouve par l'absurde le résultat d'indécidabilité, sur le modèle de la preuve du théorème de Rice.
Exercice 2 (corrigé ci-dessous). Peut-on décider si un ensemble décidable est fini ? On commencera par formuler rigoureusement le problème.
Exercice 3 (corrigé ci-dessous). Montrer en appliquant le théorème de Rice que l'ensemble des procédures qui calculent une même fonction f est infini.
Exercice 4 (corrigé ci-dessous). Prouver qu'on ne peut pas décider si deux procédures p et q calculent la même fonction.
Note : dans cette version, lisible avec tout navigateur (je l'espère du moins), les symboles logiques (quantificateurs, etc.) sont remplacés par des mots.
Exercice 1 (énoncé ci-dessus).
Prédicat P1 qui exprime qu'une procédure p calcule une fonction totale :
P1 ( p ) := pour tout x, p(x) est défini.
Prédicat P2 qui exprime qu'une procédure p calcule une fonction injective :
P2 ( p ) := pour tout couple (x1 , x2), p ( x1 ) = p ( x2 ) implique x1 = x2
Si la fonction est partielle, on peut préciser :
( p ( x1 ) défini et p ( x1 ) = p ( x2 ) ) implique x1 = x2
Prédicat P3 qui exprime qu'une procédure p calcule une fonction croissante :
P3 ( p ) := pour tout couple (x1 , x2), x1 ≤ x2 implique p ( x1 ) ≤ p ( x2 )
Si la fonction est partielle, on peut préciser :
( x1 ≤ x2 et p ( x1 ) défini et p ( x2 ) défini ) implique p ( x1 ) ≤ p ( x2 )
Prédicat P4 qui exprime qu'une procédure p calcule une fonction bornée :
P4 ( p ) := il existe b tel que, pour tout x, p(x) ≤ b
Si la fonction est partielle, on peut préciser :
p (x) défini implique p(x) ≤ b
On peut remarquer aussi qu'une fonction f : N → N est bornée si et seulement si Image ( f ) est un ensemble fini (car les valeurs de f sont des entiers naturels ; sinon cette équivalence est évidemment fausse).
Ces prédicats vérifient l'hypothèse fondamentale du théorème de Rice : leur valeur ne dépend que de la fonction calculée par la procédure p ; d'autre part aucun n'est trivial (c'est-à-dire toujours vrai ou toujours faux), donc le théorème de Rice permet de conclure qu'aucun de ces prédicats n'est calculable (autrement dit décidable).
On peut à chaque fois construire très simplement, en utilisant le principe de récursion, une procédure contradictoire γ, en supposant par l'absurde que le prédicat est calculable :
Si P1 affirme que γ1 calcule une fonction totale, celle-ci calcule la fonction jamais définie ; sinon γ1 calcule l'identité, qui est une fonction totale :
int P1 (int p (int)) { … } int gamma1 (int n) { if P1 (gamma1) while (1); else return n; }
Ceci prouve qu'il n'existe pas de procédure P1 qui calcule le prédicat P1.
Si P2 affirme que γ2 calcule une fonction injective, celle-ci calcule une fonction constante ; sinon γ2 calcule l'identité, qui est une fonction injective :
int P2 (int p (int)) { … } int gamma2 (int n) { if P2 (gamma2) return 0; else return n; }
Ceci prouve qu'il n'existe pas de procédure P2 qui calcule le prédicat P2.
Si P3 affirme que γ3 calcule une fonction croissante, celle-ci calcule une fonction périodique (valeurs successives 0 ,1, 2, 0, 1, 2, 0, etc.) ; sinon γ3 calcule l'identité, qui est une fonction croissante :
int P3 (int p (int)) { … } int gamma3 (int n) { if P3 (gamma3) return n % 3; else return n; }
Ceci prouve qu'il n'existe pas de procédure P3 qui calcule le prédicat P3.
Si P4 affirme que γ4 calcule une fonction bornée, celle-ci calcule l'identité, qui n'est pas bornée ; sinon γ4 calcule une fonction constante :
int P4 (int p (int)) { … } int gamma4 (int n) { if P4 (gamma4) return n; else return 12; }
Ceci prouve qu'il n'existe pas de procédure P4 qui calcule le prédicat P4.
Note : toutes ces constructions sont des cas particuliers de la preuve du théorème de Rice.
Exercice 2 (énoncé ci-dessus). Un ensemble décidable est donné par une procédure qui calcule sa fonction caractéristique χ. On s'intéresse donc au prédicat Fini défini par :
Fini ( p ) := { x | p(x) = 1 } est un ensemble fini
Le théorème de Rice s'applique, ce prédicat n'est pas calculable, et on ne peut donc pas décider si un ensemble décidable est fini.
Exercice 3 (énoncé ci-dessus). L'ensemble des procédures qui calculent une même fonction f n'est pas décidable, d'après le théorème de Rice, donc en particulier il est infini (tout ensemble fini est décidable).
Note : on peut préférer l'argument selon lequel on peut ajouter autant d'instructions inutiles que l'on veut à une procédure donnée, sans changer son résultat …
Exercice 4 (énoncé ci-dessus).
S'il existait un algorithme pour décider si deux procédures p et q calculent la même fonction, on pourrait décider par exemple si p calcule l'identité, en appliquant l'algorithme au cas où q est la procédure "return x". En détail :
int pmf (int p (int), int q (int) ) { … } int id (int x) {return x; } int pid (int p (int) ) { return pmf (p, id); }
Si, par l'absurde, il existe une procédure pmf (mf est l'abréviation de même fonction) qui décide si p et q calculent la même fonction, alors on peut construire la procédure pid, comme ci-dessus, pour décider si p calcule l'identité.
Note : on peut résoudre aussi cet exercice en construisant directement un couple de procédures contradictoires gamma1 et gamma2 , qui calculent la même fonction si et seulement si pmf (gamma1, gamma2) dit le contraire (c'est-à-dire vaut 0). La méthode employée ci-dessus est plus rapide et intéressante : elle consiste en une réduction d'un problème A (la procédure p calcule-t-elle l'identité), à un problème B (les procédures p et q calculent-elles la même fonction) ; si B est décidable, la réduction fournit un algorithme pour A, qui est à son tour décidable ; donc inversement (c'est le cas ici), si A est indécidable, B l'est aussi !
Attention à la direction de la réduction (réduire A à B n'est pas du tout la même chose que réduire B à A), à la direction de l'implication pour la décidabilité éventuelle, et à la direction de l'implication pour l'indécidabilité, inverse de la précédente : P implique Q équivaut à ¬Q implique ¬P (principe logique de contraposition).