Théorème de Rice - Définition

Impact pratique

La formulation pratique de ce théorème est qu'il n'existe pas d'algorithme permettant de décider, à partir du code source d'un programme, si la sortie de ce programme satisfait une propriété intéressante (non triviale) donnée. De telles propriétés indécidables incluent :

• « le programme ne termine pas par une erreur d'exécution »
• « le programme calcule un résultat correct par rapport à la spécification »

En d'autres termes, aucune méthode d'analyse statique de programmes ne peut donner des résultats sûrs et dans un temps fini pour tous les programmes quels qu'ils soient, et ce quelle que soit la propriété à tester. La restriction ne s'applique en revanche pas forcément aux seuls programmes de taille donnée.

Par exemple, un ramasse-miettes (logiciel qui libère la mémoire inutilisée) optimal et sûr est impossible ; en effet, savoir si l'on doit libérer ou non la mémoire dépend du comportement futur du système, qu'il est impossible de prévoir. Ceci explique que toutes les techniques de ramasse-miettes soient conservatrices, et puissent garder en mémoire des blocs inutiles, permettant ainsi des fuites de mémoire.

Ainsi, dans le programme suivant en langage C (supposons que p n'intervienne pas ailleurs), déterminer si l'on doit libérer le bloc mémoire sitôt après son allocation est équivalent à décider le problème de l'arrêt sur f().

      char *p = malloc(1000);      f();      *p = 1;      

Démonstration du théorème de Rice

On montre que la décision du problème de l'arrêt peut se réduire à la décision de toute propriété non triviale sur un ensemble récursivement énumérable. On représente tout ensemble récursivement énumérable par la machine de Turing qui l'accepte. Soit P une propriété décidable et non triviale sur les ensembles récursivement énumérables. Soit P(∅)="Faux" (si ce n'est pas le cas, on raisonne pareillement avec la négation de P). Donc, il existe un ensemble récursivement énumérable A qui satisfait P. Soit K une machine de Turing qui accepte A. P étant décidable, il existe donc une machine de Turing MP qui, pour toute représentation d'une machine de Turing, décide si l'ensemble récursivement énumérable accepté par cette machine satisfait P ou non.

Dès lors, on construit une machine de Turing H prenant en entrée la représentation d'une machine de Turing M suivie d'une entrée x. L'algorithme de H est le suivant :

1. Construire la représentation d'une machine de Turing T qui, sur une entrée d :

• Simule l'exécution de M sur x
• Simule l'exécution de K sur d et renvoie le résultat.

2. Simuler l'exécution de MP sur la représentation de T et renvoyer le résultat.

Si M s'arrête sur x, l'ensemble accepté par T est A. Cet ensemble satisfaisant P, la seconde phase de l'algorithme renverra "Vrai". Si M ne s'arrête pas sur x, l'ensemble accepté par T est ∅. Cet ensemble ne satisfaisant pas P, la seconde phase de l'algorithme renverra "Faux".

La machine H calcule donc de manière totale le problème de l'arrêt. Celui-ci étant indécidable, par contradiction, P est donc indécidable.

Démonstration de la seconde partie

De manière analogue, on montre que la semi décision de la négation du problème de l'arrêt peut se réduire à la semi-décision de toute propriété non-monotone sur les ensembles récursivement énumérables.

Soit P une propriété non-monotone et semi-décidable. Il existe donc deux ensembles récursivement énumérables A et B, calculés respectivement par des machines de Turing MA et MB tels que :

• A est inclus dans B
• A satisfait P
• B ne satisfait pas P.

De plus, il existe une machine de Turing MP qui, pour toute représentation d'une machine de Turing, s'arrête et accepte si l'ensemble récursivement énumérable accepté par cette machine satisfait P.

Dès lors, on peut construire une machine de Turing H prenant en entrée la représentation d'une machine de Turing M suivie d'une entrée x dont l'algorithme est le suivant :

1 Construire la représentation d'une machine de Turing T qui, sur une entrée y :

1 Exécute en parallèle

• MA sur y
• MB sur y
• M sur x

2 Accepte y si

• MA accepte y ou bien
• MB accepte y ET M s'arrête sur x

2 Exécuter MP sur la représentation de T et renvoyer le résultat.

Par «exécuter en parallèle», on entend que la machine T exécute un pas MA sur y, puis un pas de MB sur y, puis un pas de M sur x, puis un second pas de MA sur y, et ainsi de suite. Autrement dit, on «entrelace» les pas de calcul d'une machine avec ceux de l'autre machine.

Si M s'arrête sur x, T accepte y si, et seulement si MA ou MB accepte y, et comme A est inclus dans B, cela revient à dire si et seulement si y appartient à B. Donc, T accepte exactement l'ensemble B, qui, par hypothèse, ne vérifie pas P. Par conséquent, MP n'accepte pas T. (P étant supposé semi-décidable, MP peut même ne pas s'arrêter du tout) Si M ne s'arrête pas sur x, T accepte y si et seulement si y appartient à A. T accepte donc exactement l'ensemble A qui, par hypothèse, satisfait P. Par conséquent, MP accepte T (et finit donc par s'arrêter, par définition de la semi-décidabilité). La machine H calcule donc la négation du problème de l'arrêt. Celui-ci n'étant pas semi-décidable, par contradiction, P ne peut donc pas être semi-décidable.