Problème — L'indécidabilité se propage

1. L'astuce consiste à fabriquer un nouveau programme par concaténation de textes — opération licite, puisqu'un programme est une chaîne de caractères. On prend le programme étudié et on lui ajoute, tout à la fin, une instruction d'affichage.

def arrete(source, entree):
    """Construite EN SUPPOSANT que `affiche` existe."""
    nouveau = source + "\nprint('fini')\n"
    return affiche(nouveau, entree)

Le programme nouveau fait exactement ce que faisait source, puis affiche fini. Deux cas : si source s'arrête sur entree, l'exécution atteint la dernière ligne et affiche quelque chose ; si source boucle indéfiniment, cette ligne n'est jamais atteinte et rien n'est jamais affiché. Donc nouveau affiche quelque chose si et seulement si source s'arrête. On peut vérifier la construction du texte :

SOURCE = "def f(n):\n    return n + 1\nf(3)\n"
NOUVEAU = SOURCE + "\nprint('fini')\n"
print(repr(NOUVEAU))
# "def f(n):\n    return n + 1\nf(3)\n\nprint('fini')\n"
exec(NOUVEAU)   # affiche : fini

2. Si affiche existait, la fonction arrete ci-dessus existerait et serait correcte. Or aucune fonction arrete correcte n'existe. Donc affiche n'existe pas : le problème est indécidable. Ce type de raisonnement s'appelle une réduction — on ramène un problème nouveau à un problème dont l'impossibilité est déjà connue.

3. Un antivirus parfait devrait répondre à : « ce programme va-t-il, sur une entrée quelconque, chiffrer mes fichiers ? ». C'est une question sur le comportement du programme, et la même réduction s'applique : on lui accolerait l'instruction malveillante à la fin, et décider s'il est dangereux reviendrait à décider s'il s'arrête. Un antivirus travaille donc sur le texte des programmes — signatures de codes déjà connus — et sur des indices comportementaux ; il se trompe parfois dans les deux sens, en laissant passer un virus inédit ou en accusant un logiciel sain. En pratique, on renonce à l'universalité : on répond oui, non ou je ne sais pas, on se restreint à des sous-classes décidables, et on exécute sous surveillance dans un bac à sable, avec un délai maximal.