Chapitre 2 : Diagonalisation Table des matières Chapitre 4 : Ensembles récursivement énumérables
Exercices

« Toutes ces choses vous apparaîtront clairement, dit avec douceur le vieillard, du moins, ajouta-t-il avec un léger doute dans la voix, plus clairement qu'à l'heure actuelle. »

Douglas Adams
Le guide du voyageur galactique
Traduit de l'anglais par Jean Bonnefoy

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

  1. Principe de récursion
  2. Théorème de Rice
  3. Indécidabilité : FAQ

1. Principe de récursion

Le principe de récursion désigne le principe fondamental qui consiste à faire appel à la procédure p dans la définition de p elle-même. Il n'était pas évident, aux débuts de l'informatique, que ce principe ne conduirait pas à une contradiction logique ; il n'en est rien, c'est une méthode de définition valide, dont il n'y a pas de raison logique de restreindre l'emploi, et les procédures récursives sont utilisées très couramment depuis 1960 environ. Bien sûr une définition récursive maladroite de p peut rendre p(x) non défini pour certaines valeurs de l'argument x (et le plus souvent pour tout x), mais ce phénomène est inévitable dans tout modèle de calcul, comme l'a montré le chapitre précédent.

L'usage courant est de calculer p(x) à partir de p(x-1) ; ici nous considèrerons des procédures qui examinent leur propre texte. Un exemple très simple, en langage C, est le suivant :

int p (int x) {
  return (int) p;
}

Cette procédure calcule sa propre adresse (elle ne tient pas compte de l'argument x, donc calcule une fonction constante) ; elle ne pose aucun problème, ni lors de sa compilation (à condition de ne pas oublier de convertir l'adresse en un entier, par un forçage de type -- cast, comme ci-dessus) ni lors de son exécution. Certains auteurs appellent théorème de récursion la possibilité, pour une procédure, de faire référence à elle-même ; il me semble que la procédure ci-dessus ne mérite pas tant d'emphase…

Notons qu'un des modèles de calcul célèbres proposés autour de 1930 est celui des fonctions récursives, en un sens à la fois plus technique et plus général que celui d'aujourd'hui ; du coup, dans les cours de calculabilité, une fonction récursive désigne souvent une fonction calculable. Nous éviterons cet emploi dans ce cours, sauf, partiellement, au chapitre suivant.

Le chapitre précédent a examiné en détail les paradoxes de la diagonalisation, et nous avons conclu, entre autres, que le problème de l'arrêt est indécidable. Il est important de bien connaître ces paradoxes, et leurs conséquences ; mais s'il s'agit simplement de prouver l'indécidabilité du problème de l'arrêt, l'usage de la récursion donne une preuve plus simple. Supposons en effet que la fonction h, dont nous rappelons la définition :

h ( p, x ) = ì
í
î
1 si p (x) est défini
0 sinon

soit calculable par une procédure hp. Alors voici une procédure γ contradictoire :

int hp (int p (int), int x) { … }

int gamma (int x) {
  if (hp (gamma, x)) while (1);
  else return 0;
}

γ commence par appeler hp pour savoir si γ(x) est défini, puis fait délibérément le contraire ! Le secret est la récursion (γ exécute un calcul sur son propre code, c'est-à-dire en C sur sa propre adresse) ; γ est une procédure contradictoire :

ce qui contredit la définition de h, et prouve non pas que γ est "mal écrite", mais qu'il n'existe pas de procédure hp qui calcule h.

Note 1 : on utilise ici l'adresse de γ, facilement accessible en C ; mais on peut utiliser n'importe quelle numérotation effective des procédures, cf. chapitre 1.

Note 2 : la définition de γ ne comporte pas d'exécution récursive de γ pour savoir si γ(x) est défini ou non, cela n'aurait pas de sens ; γ fait appel à la procédure hypothétique hp pour répondre à cette question ; hp "répond" en examinant le code de γ (et l'entier x), puis γ poursuit son exécution en fonction de la "réponse" obtenue.

On démontre de la même façon que les variantes suivantes du problème de l'arrêt sont indécidables :

Il n'y a rien à changer dans la construction de γ ci-dessus, sauf remplacer hp par hp1 ou hp2 (procédures censées calculer respectivement les fonctions h1 et h2 ), pour conclure que ni h1 ni h2 ne sont calculables. On peut aussi s'intéresser aux procédures sans argument, d'en-tête int p (void) ; une telle procédure calcule un entier (et un seul), ou bien ne termine pas. L'indécidabilité du problème de l'arrêt se traduit dans ce cas par la non calculabilité de la fonction h3 :

2. Théorème de Rice

La méthode de diagonalisation (chapitre précédent) conduit à l'indécidabilité du problème de l'arrêt ; mais le principe de récursion, plus simple, donne des idées pernicieuses, car pourquoi limiter la méthode de la section précédente au problème de l'arrêt ? Par exemple est-il possible de décider si une procédure p calcule l'identité, c'est-à-dire si pour tout x, p(x) = x ? A l'évidence non, la fonction δ définie par :

δ ( p ) = ì
í
î
1 si pour tout x, p(x) = x
0 sinon

n'est pas calculable, sinon on pourrait écrire une fonction contradictoire :

int delta (int p (int) ) { … }

int gamma (int x) {
  if (delta (gamma)) return 0;
  else return x;
}

Le théorème de Rice donne l'extension maximale à ce type de raisonnement : en bref aucun problème concernant la fonction calculée par une procédure n'est décidable ! Voici une formulation précise :

Théorème de Rice. Soit P un prédicat tel que :
[ pour tout x, p(x) = q(x) ] implique P ( p ) = P ( q ) ;
alors P est indécidable (sauf si c'est un prédicat trivial).

La condition "pour tout x, p(x) = q(x)" exprime que les procédures p et q calculent la même fonction ; il faut comprendre en particulier que p(x) est défini si et seulement si q(x) l'est. Les prédicats triviaux sont deux : celui dont la valeur est constamment 0 (quel que soit l'argument p), et celui dont la valeur est constamment 1 ; ils sont calculables, mais offrent peu d'intérêt.

On rappelle qu'un prédicat a été défini, chapitre 2, section 4, comme une fonction booléenne ; c'est le sens adopté ici, où il est temps de préciser qu'il s'agit, comme pour le problème de l'arrêt ou pour le problème qui débute cette section (une procédure p calcule-t-elle l'identité), d'une fonction totale : un prédicat ne peut pas être indéfini. Signalons qu'en logique, prédicat désigne plutôt une formule comportant, entre autres, des connecteurs logiques (négation, conjonction, disjonction) et des quantificateurs — ∀ (pour tout), ∃ (il existe) ; voir par exemple le chapitre 4, section 5 pour des exemples.

Preuve du théorème de Rice : on suppose le prédicat P non trivial, donc il existe une procédure p0 telle que P ( p0 ) = 0, et une procédure p1 telle que P ( p1 ) = 1. On suppose par l'absurde qu'il existe une procédure procP pour calculer P, et on construit la fonction contradictoire γ comme suit :

int procP (int p (int) ) { … }
int p0 (int x) { … }
int p1 (int x) { … }

int gamma (int x) {
  if (procP (gamma)) return p0(x);
  else return p1(x);
}

Si la procédure γ vérifie le prédicat P, elle calcule la même fonction que la procédure p0, qui ne vérifie pas P ; et vice-versa : si la procédure γ ne vérifie pas le prédicat P, elle calcule la même fonction que la procédure p1, qui vérifie P. Chacun des cas contredit l'hypothèse faite sur P, et on en déduit que P n'est pas calculable (la procédure procP n'existe pas), autrement dit est indécidable.

Note : la définition de γ n'implique pas d'exécution récursive de γ ; γ fait appel à la procédure hypothétique procP, qui "répond" en examinant le code de γ (l'adresse d'une procédure est un pointeur sur son code), puis γ poursuit son exécution en fonction de la "réponse" obtenue. A priori il n'est pas interdit à procP d'effectuer quelques calculs de γ (x) pour certaines valeurs de l'argument x, mais procP est par définition une procédure qui termine, donc elle ne peut pas appeler γ pour une infinité d'arguments, ni calculer γ (x) si ce calcul ne termine pas !

3. Indécidabilité : FAQ

Question. Lorsque j'écris un programme, il est donc impossible de savoir s'il boucle ? Robert Strandh va être surpris.

Réponse. Ecrire des programmes qui ne bouclent pas reste une activité louable, ce chapitre et le précédent prouvent justement qu'il est impossible d'automatiser totalement cette activité : un compilateur détecte les erreurs syntaxiques, mais ne peut pas détecter systématiquement les programmes qui bouclent. De même il est illusoire d'attendre la mise au point d'un langage dans lequel on ne pourrait écrire que des programmes qui ne bouclent pas.

L'indécidabilité du problème de l'arrêt, et plus généralement le théorème de Rice, sont plutôt des bonnes nouvelles pour les informaticiens : écrire des programmes corrects, qui calculent ce que l'on attend d'eux, sera toujours une activité demandant de la réflexion et de l'expérience.

Question. Cette fois j'ai compris, on vient de prouver que l'homme est supérieur à la machine !

Réponse. Non. On a seulement prouvé que les méthodes pour écrire de bons programmes (qui ne bouclent pas, qui calculent ce que l'on souhaite) doivent être adaptées à chaque cas particulier, ou plutôt à chaque classe de cas. Cette adaptation est une activité sans fin ; savoir si l'homme est seul capable d'une telle "créativité" est une question de conviction personnelle. Personnellement cela me surprendrait beaucoup.

Question. Redescendons sur terre : le théorème de Rice dit que la fonction xx n'est pas calculable ?

Réponse. Non, cette fonction est bien sûr calculable.

Question. Le théorème de Rice dit qu'il est impossible de savoir si la procédure :

int id (int x) {
  return x + 1;
}

calcule la fonction "successeur" ? C'est absurde, inutile de continuer à travailler cette UE.

Réponse. Ce serait effectivement absurde. La procédure ci-dessus calcule bien la fonction successeur, et de même on peut écrire des procédures "sûres" pour calculer la fonction factorielle, pour trier intelligemment des tableaux (quicksort), pour trouver des chemins dans des graphes, etc. Le théorème de Rice dit qu'il n'existe pas d'algorithme général (on dit aussi uniforme) à qui on fournirait en argument une procédure p quelconque, et qui répondrait : oui, p calcule la fonction successeur, ou : non, p ne calcule pas la fonction successeur.

Question. Finissons-en, montrez-nous un couple ( p, x ) dont on ne puisse pas décider si p(x) est défini, ou une procédure p dont on ne puisse pas décider si elle calcule l'identité !

Réponse. Désolé, cette requête n'a pas de sens. Une fonction non calculable est forcément une fonction d'une variable (ou de plusieurs) ; en particulier un problème indécidable doit dépendre d'une variable, on dit aussi qu'il doit posséder une infinité d'instances. Considérons par exemple la procédure suivante, qui cherche un contre-exemple au théorème de Fermat, en utilisant la possibilité, étudiée au chapitre 1, d'énumérer tous les quadruplets d'entiers :

int fermat (void) {
  pour chaque quadruplet (a, b, c, d) {
    x = a + 1; y = b + 1; z = c + 1;
    n = d + 3;
    if (xn + yn = zn) return 1;
  }
}

(les fragments non valides en C pourraient être facilement convertis pour obtenir une vraie procédure C ; l'instruction x=a+1 et ses soeurs, assurent que x, y et z sont strictement positifs, et que l'exposant n est strictement supérieur à 2). Avant que le théorème de Fermat soit démontré, on ne savait pas si cette procédure terminait ou non (aujourd'hui, on sait qu'elle ne termine pas), autrement dit on ne savait pas si la réponse au problème de l'arrêt, pour cette procédure particulière, était calculée par la procédure :

int vrai (void) {return 1;}

ou par la procédure :

int faux (void) {return 0;}

Mais l'une des deux procédures donne à coup sûr la réponse, comme pour tout prédicat avec une seule instance ; donc la question de la calculabilité, ou de la décidabilité, ne se pose pas.

Note : il ne faut pas confondre décidable et démontrable ; nous verrons au chapitre suivant qu'il existe en arithmétique des propositions irrésolubles, c'est-à-dire qu'on ne peut ni démontrer ni réfuter (théorème de Gödel). Avant que le mathématicien Wiles achève la démonstration du théorème de Fermat, on pouvait légitimement se demander si ce théorème ne rentrait pas dans cette catégorie.

L'indécidabilité du problème de l'arrêt indique qu'il n'existe pas d'algorithme général qu'on pourrait appliquer, entre autres, à la procédure fermat ci-dessus, et qui, par simple examen du texte de la procédure, répondrait "la procédure fermat ne termine pas", et court-circuiterait ainsi les deux siècles de travaux qui ont été nécessaires pour démontrer le théorème de Fermat. Qu'un algorithme aussi miraculeux n'existe pas, est tout à fait conforme à notre expérience des mathématiques, et confirme que l'activité créatrice des mathématiciens a de l'avenir.

Question. Si un problème avec une seule instance est toujours décidable, je suppose qu'il en est de même pour un problème avec deux instances ?

Réponse. Exact.

Question. Idem pour un problème avec un milliard d'instances, je suppose ?

Réponse. Certainement.

Question. Alors on sait résoudre en pratique le problème de l'arrêt : au lieu de prendre pour variables une procédure et un entier quelconques, il suffit de se limiter aux couples ( p, x ) intéressants dans un contexte donné, qui forment un ensemble fini.

Réponse. Non. La faille de ce raisonnement est qu'il faut modifier l'algorithme pour chaque nouveau cas à traiter (c'est d'ailleurs ainsi qu'on procède, pour l'essentiel, en pratique : chaque problème vraiment nouveau requiert l'invention d'une nouvelle méthode de résolution) ; ce qui revient à dire qu'il n'y a pas d'algorithme uniforme pour traiter le problème de l'arrêt : c'est exactement la signification du terme indécidable.

Par contre il est exact qu'il existe de vastes classes (y compris infinies) de procédures pour lesquels le problème de l'arrêt, ou le problème de caractériser la fonction calculée, sont décidables. C'est le cas par exemple pour les automates à états finis : consulter l'ouvrage de Sipser, ou celui de Kozen, pour plus de détails sur ces automates et sur les automates à pile.