L’indécidabilité de l’infection par un virus

J-P Delahaye

Définition : un programme infecté est un programme qui en modifie au moins un autre.

Supposons que nous ayons écrit un programme DÉTECTEUR qui indique si un programme donné est un programme infecté ou non, soit le programme PIÈGE défini par :

Si DÉTECTEUR appliqué à PIÈGE donne le résultat oui, alors ne rien faire.

Si DÉTECTEUR appliqué à PIÈGE donne le résultat non, alors choisir un programme dans la mémoire et l’infecter, c’est-à-dire y insérer PIÈGE.

PIÈGE est-il un programme infecté ?

Si la réponse est oui, alors PIÈGE ne fait rien aux programmes et PIÈGE n’est pas un programme infecté, c’est une contradiction.

Si la réponse est non, alors PIÈGE infecte un programme et donc est un programme infecté, ce qui est encore une contradiction. Il en résulte que DÉTECTEUR ne peut exister.

Conclusion : il n’existe pas de détecteur universel de programmes infectés. »

J-P Delahaye in Logique, informatique et paradoxes, Pour la science, Belin, ISBN : 2-9029-1894-1


Rappel : la logique des prédicats d'ordre deux est semi-décidable. Comme vous savez que par exemple l'inclusion se définit avec un tel prédicat ... il vous faut savoir que l'on ne peut avoir de prouveur décidable. Il n'est que semi-décidabe. Lire poly.