Programme comme donnée, calculabilité et décidabilité

1. Un programme est aussi une donnée

Un programme n’est pas seulement quelque chose qu’on exécute : c’est d’abord un texte (une suite de caractères) stocké dans un fichier. Comme n’importe quelle donnée, ce texte peut être copié, envoyé, lu, analysé ou même transformé.

Exemple 1 : Stocker du code dans une chaîne

programme = """
def carre(x):
    return x*x
"""
print(programme)

Exemple 2 : Exécuter une donnée contenant du code

code = "print(2 + 3)"
exec(code)

2. Calculabilité : « Existe-t-il un algorithme ? »

Un problème est dit calculable s’il existe un algorithme qui, pour toute entrée valide, produit une réponse en un nombre fini d’étapes (même si c’est long).

• Sommer une liste de nombres.
• Trier une liste.
• Calculer le PGCD de deux entiers.

La calculabilité ne dépend pas du langage

Python, C, Java… changent la manière d’écrire, mais pas ce qui est calculable. Dès qu’un langage permet variables, tests, boucles et mémoire, il peut simuler les mêmes algorithmes.

3. Décidabilité : « Peut-on toujours répondre OUI/NON et terminer ? »

Un problème est décidable s’il existe un programme qui, pour toute entrée, renvoie OUI ou NON et termine toujours.

• « Ce nombre est-il pair ? » → décidable.
• « Cette chaîne contient-elle la lettre a ? » → décidable.

4. Le problème de l’arrêt

On aimerait un programme capable de répondre à la question suivante :

Si un tel programme existait, il pourrait détecter toutes les boucles infinies et certifier que n’importe quel programme termine. Mais nous allons voir que c’est impossible.

5. Pourquoi c’est indécidable (preuve par l'absurde)

Supposons (pour raisonner) qu’un programme parfait arrete(p) existe : il renvoie True si p s’arrête, sinon False.

Construisons un programme paradoxal qui utilise arrete :

def paradoxal(p):
    if arrete(p):        # si p s'arrête...
        while True:      # ... alors je boucle
            pass
    else:                # si p ne s'arrête pas...
        return "Je m'arrête"

Maintenant, on lance paradoxal(paradoxal).

• Si arrete(paradoxal) dit True, alors paradoxal boucle → contradiction.
• Si arrete(paradoxal) dit False, alors paradoxal s’arrête → contradiction.

6. Ce que cela implique en pratique

• On ne peut pas écrire un outil qui décide parfaitement la terminaison de tous les programmes.
• Les analyseurs de code détectent beaucoup de problèmes, mais pas « le cas général ».
• Certaines limites de l’informatique sont mathématiques, pas technologiques.

7. À retenir