Théorème de Rice
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

En théorie de la calculabilité, le théorème de Rice dit que toute propriété non triviale (c.-à-d. qui n'est pas toujours vraie ou toujours fausse) sur la sémantique dénotationnelle d'un langage de programmation Turing-complet est indécidable. Il s'agit d'une généralisation (La généralisation est un procédé qui consiste à abstraire un ensemble de concepts ou d'objets en négligeant les détails de façon à ce qu'ils puissent être considérés de façon...) du problème de l'arrêt.

Ce théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une assertion qui peut être établie comme vraie au travers d'un raisonnement logique construit à partir d'axiomes. Un théorème est à distinguer...) est la reformulation " intuitive " du corollaire (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une assertion qui peut être établie comme vraie au travers d'un raisonnement logique construit à partir...) B de la publication originale de Rice (1953).

Description et preuve intuitive

Tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) d'abord, rappelons qu'il n'existe pas de programme halt permettant de savoir si un programme prog s'arrête ou non avec une chaîne (Le mot chaîne peut avoir plusieurs significations :) de bits ch en entrée (pour une preuve voir la page sur le problème de l'arrêt). On peut obtenir un résultat plus général.

Précisons quelques notations: prog(ch) est la chaîne obtenue en sortie si on ne boucle pas en lançant prog avec ch en entrée, on note ch_prog la chaîne codant le programme prog, et ch1,ch2 désigne la chaîne obtenue en concaténant les deux chaînes ch1 et ch2.

Supposons par exemple, qu'il existe un programme square tel que square(ch_prog,ch) retourne 1 si on ne boucle pas et que prog(ch) code le carré (Un carré est un polygone régulier à quatre côtés. Cela signifie que ses quatre côtés ont la même longueur et ses quatre angles la même mesure. Un carré est à la fois un...) de l'entier codé par ch, et 0 sinon.

On peut alors construire le programme trouble suivant, dans lequel prog est un programme quelconque et ch2 une chaîne quelconque:

trouble(ch1)

1. faire prog(ch2)

2. retourne le carré de l'entier codé par ch1

Nous obtenons que trouble(ch1) existe et code le carré de l'entier codé par ch1 si et seulement si prog s'arrête avec ch2 en entrée. Ainsi, si square existe, alors halt existe; or on sait que halt n'existe pas.

Dans notre exemple au-dessus on peut remplacer square par n'importe quelle fonction, ce qui nous permet de prouver le théorème de Rice (En théorie de la calculabilité, le théorème de Rice dit que toute propriété non triviale (c.-à-d. qui n'est pas toujours vraie ou toujours fausse) sur la sémantique dénotationnelle d'un langage...): Pour toute fonction f et tout programme prog, il n'existe pas de programme pour vérifier que prog est une implantation (Le mot implantation peut avoir plusieurs significations :) de f.

Impact pratique

La formulation (La formulation est une activité industrielle consistant à fabriquer des produits homogènes, stables et possédant des propriétés spécifiques, en mélangeant différentes matières...) pratique de ce théorème est qu'il n'existe pour aucune propriété intéressante (non triviale) portant sur le résultat final d'un programme un algorithme permettant, au vu du code source (Le code source (ou les sources voire le source) est un ensemble d'instructions écrites dans un langage de programmation informatique de haut niveau,...) d'un programme, de décider s'il satisfait cette propriété. 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 (Le mot statique peut désigner ou qualifier ce qui est relatif à l'absence de mouvement. Il peut être employé comme :) de programmes ne peut donner des résultats sûrs et dans un temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) 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 (Dans les technologies de l'information, une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction, d'un...).

Par exemple, un ramasse-miettes (logiciel qui libère la mémoire (D'une manière générale, la mémoire est le stockage de l'information. C'est aussi le souvenir d'une information.) 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éfinition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) formelle

Première partie

On suppose que l'on travaille avec un langage de programmation (Un langage de programmation est un langage informatique, permettant à un être humain d'écrire un code source qui sera analysé par une machine, généralement un...) Turing-complet (Le terme Turing-complet[1] désigne en informatique un système formel ayant au moins le pouvoir des machines de Turing.) (toutes les fonctions calculables en un sens (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par une évolution progressive allant du ralentissement du...) intuitif, voir thèse (Une thèse (du nom grec thesis, se traduisant par « action de poser ») est l'affirmation ou la prise de position d'un locuteur, à l'égard du sujet ou du thème qu'il évoque.) de Church-Turing, peuvent se programmer dans ce langage). Soit φ(x,y) le résultat de l'évaluation du programme x sur l'entrée y ∈ ?. Si le programme x ne termine pas pour l'entrée y la fonction φ n'est pas définie pour ces entrées, il s'agit donc d'une fonction nécessairement partielle, φ(x,y) ne désigne pas forcément quelque chose (on peut ajouter ⊥ pour désigner la valeur spéciale " ne termine pas "). Notons P un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout »,...) de programmes calculant des fonctions partielles (certaines pouvant être partout définies, on ne précisera plus dans la suite) de ? dans ?. Supposons que l'ensemble des x tels que y ? φ(x,y) est dans P soit récursif. Alors, P = ∅ ou P est l'ensemble de tous les programmes (calculant une fonction partielle de ? dans ?).

Dit autrement, d'après le théorème de Rice, tout ensemble de programmes extensionnel, c'est à dire contenant tous les programmes calculant une fonction partielle donnée dès qu'il en contient un, et non trivial, c'est à dire différent de l'ensemble des programmes et de ∅, n'est pas un ensemble récursif (En théorie de la calculabilité, un ensemble récursif ou ensemble décidable est un ensemble d'entiers (ou d'éléments facilement codables dans les entiers) dont la fonction caractéristique est une fonction récursive au sens...).

Si l'on veut vraiment formaliser il faut dire ce que sont les programmes. Pour ce genre de propriété une représentation assez grossière suffit. Dans la théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée ou une connaissance...) de la calculabilité (La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est une branche de la logique mathématique et de l'informatique théorique. Alors que la notion intuitive de fonction calculable est aussi vieille que les...) (ou récursivité) initiée par Kleene, les programmes sont codés par des entiers (en informatique (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le...) ce sont bien des suites de lettres, donc de bits, donc ultimement des entiers). La fonction φ est la fonction partielle d'énumération de Kleene : c'est une fonction récursive (En informatique et en mathématiques, le terme fonction récursive désigne deux concepts liés, mais distincts. Plus généralement les termes « récursif », « récursivement », « récursion », « récursivité », peuvent faire...) partielle de ? × ? ? ? qui énumère toutes les fonctions récursives partielles de ? ? ?, qui sont donc les fonctions φx : y ? φ(x,y). L'entier x est appelé indice (ou code) de la fonction φx. Tout comme il y a clairement une infinité de programmes calculant la même fonction (on peut ajouter autant que l'on veut des instructions à un programme qui n'ont pas d'effet sur le résultat), une fonction récursive partielle possède une infinité d'indices.

Un ensemble d'entiers (donc d'indices de fonctions récursives partielles) W est dit extensionnel quand deux entiers i et j qui sont les indices d'une même fonction récursive partielle sont soit tous deux dans W, soit tous deux hors de W :

i, j ∈ ? [(iW et φi = φi) ⇒ jW]

Le théorème de Rice, affirme alors que :

Théorème de Rice. Un sous-ensemble (En mathématiques, un ensemble A est un sous-ensemble ou une partie d’un ensemble B, ou encore B est sur-ensemble de A, si tout élément du...) extensionnel de ? non trivial (différent de ? et de ∅) n'est pas récursif.

Il faut remarquer que toutes ces notions, interprétées au sens strict sur les entiers, sont sensibles au codage (De façon générale un codage permet de passer d'une représentation des données vers une autre.). Il s'agit donc bien de résultats sur les fonctions calculables.

Seconde ( Seconde est le féminin de l'adjectif second, qui vient immédiatement après le premier ou qui s'ajoute à quelque chose de nature identique. La seconde est une unité de mesure du temps. La seconde d'arc est une...) partie

Du point (Graphie) de vue (La vue est le sens qui permet d'observer et d'analyser l'environnement par la réception et l'interprétation des rayonnements lumineux.) des ensembles récursivement énumérables, le théorème de Rice dit que toute propriété non triviale sur ces ensembles est indécidable. Une telle propriété est dite monotone si, et seulement si, pour tous ensembles récursivement énumérables A et B tels que A est inclus dans B, on a P(A) -> P(B). Par exemple, "A est un ensemble fini (En mathématiques, un ensemble E est dit fini si et seulement si E est vide ou s'il existe un entier n et une bijection de E dans l'ensemble des n premiers entiers naturels.)" n'est pas monotone, alors que "A contient l'élément x" l'est. Alors, aucune propriété non-monotone sur les ensembles récursivement énumérables n'est récursivement énumérable (Intuitivement un ensemble est récursivement énumérable s'il existe un procédé mécanique (en gros qui peut être réalisé par un ordinateur) qui liste ses éléments. On dirait aussi...) (ou semi-décidable).

Démonstration (En mathématiques, une démonstration permet d'établir une proposition à partir de propositions initiales, ou précédemment...) 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 (En logique mathématique, le terme décidabilité recouvre deux concepts liés : la décidabilité logique et la décidabilité algorithmique.) 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 (Le mot phase peut avoir plusieurs significations, il employé dans plusieurs domaines et principalement en physique :) 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 (Une contradiction existe lorsque deux affirmations, idées, ou actions s'excluent mutuellement.), 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 reviens à 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 consiquent, 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.

Page générée en 0.224 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique