Théorème de Rice - Définition

Introduction

En théorie de la calculabilité, le théorème de Rice dit que toute propriété non triviale (c’est-à-dire 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 du problème de l'arrêt.

Ce théorème est la reformulation « intuitive » du corollaire B de la publication originale de Rice (1953).

Description et preuve intuitive

Tout 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 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 l'exécution de prog avec ch en entrée termine. 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 l'appel de prog(ch) termine et code le carré 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 : Pour toute fonction f et tout programme prog, il n'existe pas de programme pour vérifier que prog est une implantation de f.

Définition formelle

Première partie

On suppose que l'on travaille avec un langage de programmation Turing-complet (toutes les fonctions calculables en un sens intuitif, voir thèse 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 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.

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 de la calculabilité (ou récursivité) initiée par Kleene, les programmes sont codés par des entiers (en informatique 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 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 ∈ ℕ [(i ∈ W et φ_i = φ_j) ⇒ j ∈ W]

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

Théorème de Rice. Un sous-ensemble 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. Il s'agit donc bien de résultats sur les fonctions calculables.

Seconde partie

Du point de vue 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 » 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 (ou semi-décidable).