Chapitre 3 : Récursion et théorème de Rice

TD : 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.

Solutions

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).

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 :

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).