Chapitre 4 - Partie 3 : Calculabilité et décidabilité

B.O. spécial n° 8 du 25 juillet 2019 - NSI Terminale

Contenus	Capacités attendues	Commentaires
Notion de programme en tant que donnée. Calculabilité, décidabilité.	Comprendre que tout programme est aussi une donnée. Comprendre que la calculabilité ne dépend pas du langage de programmation utilisé. Montrer, sans formalisme théorique, que le problème de l'arrêt est indécidable.	L'utilisation d'un interpréteur ou d'un compilateur, le téléchargement de logiciel, le fonctionnement des systèmes d'exploitation permettent de comprendre un programme comme donnée d'un autre programme.

1. Un programme est aussi une donnée

1.1 Le programme comme fichier

Un programme (code source) est un fichier texte stocké sur le disque, exactement comme un document ou une image. Il peut être :

lu par un éditeur de texte ;
copié, déplacé, supprimé comme tout fichier ;
envoyé par e-mail ou téléchargé sur Internet ;
analysé par un autre programme.

1.2 Un programme traité par un autre programme

De nombreux logiciels prennent des programmes en entrée :

Logiciel	Ce qu'il fait avec le programme
Interpréteur Python	Lit le code source et l'exécute ligne par ligne
Compilateur (C, Java)	Traduit le code source en langage machine
Éditeur de code	Affiche le code avec coloration syntaxique
Débogueur	Exécute le code pas à pas, inspecte les variables
Système d'exploitation	Charge le programme en mémoire et crée un processus
Antivirus	Analyse le programme pour détecter des comportements malveillants

1.3 Conséquence fondamentale

Puisqu'un programme est une donnée, un programme peut se prendre lui-même en entrée. Cette observation, apparemment anodine, conduit à des résultats théoriques profonds sur les limites de l'informatique.

# Un programme qui lit son propre code source
with open(__file__, 'r') as f:
    mon_code = f.read()
    print(f"Ce programme fait {len(mon_code)} caractères.")

2. Calculabilité

2.1 Qu'est-ce qu'une fonction calculable ?

Une fonction est calculable s'il existe un algorithme (un programme) qui, pour chaque entrée, produit le résultat correct en un nombre fini d'étapes.

Fonction	Calculable ?
Additionner deux entiers	Oui
Trier un tableau	Oui
Vérifier si un nombre est premier	Oui
Le problème de l'arrêt	Non (voir plus loin)

2.2 La thèse de Church-Turing

2.3 L'universalité des langages de programmation

Tous les langages de programmation « complets » (Python, C, Java, JavaScript, etc.) sont équivalents en puissance de calcul : tout ce qui peut être calculé dans un langage peut l'être dans un autre.

Cela signifie que la calculabilité ne dépend pas du langage choisi. Si un problème est incalculable, aucun langage ne pourra le résoudre.

3. La décidabilité

3.1 Problème de décision

Un problème de décision est une question qui admet une réponse oui ou non pour chaque instance.

Problème	Question	Décidable ?
Nombre premier	« n est-il premier ? »	Oui
Tri	« Le tableau est-il trié ? »	Oui
Arrêt	« Le programme P s'arrête-t-il sur l'entrée E ? »	Non

3.2 Problème décidable vs indécidable

Un problème est décidable s'il existe un algorithme qui donne toujours la bonne réponse (oui ou non) en un temps fini.
Un problème est indécidable s'il n'existe aucun algorithme qui puisse répondre correctement dans tous les cas.

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

4.1 Énoncé

Le problème de l'arrêt est la question suivante :

Étant donné un programme P et une entrée E, peut-on déterminer si P s'arrête (termine) lorsqu'on l'exécute sur E, ou bien s'il boucle indéfiniment ?

4.2 Exemples

# Ce programme s'arrête-t-il ?
def programme_a(n):
    return n + 1
# → Oui, il s'arrête toujours.

# Et celui-ci ?
def programme_b(n):
    while True:
        pass
# → Non, il boucle indéfiniment.

# Et celui-ci ?
def programme_c(n):
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
    return n
# → Conjecture de Syracuse : on pense que oui pour tout n,
#   mais personne ne l'a prouvé !

4.3 Preuve d'indécidabilité (par l'absurde)

Supposons qu'il existe une fonction arret(P, E) qui renvoie True si le programme P s'arrête sur l'entrée E, et False sinon.

Construisons alors le programme paradoxal suivant :

def paradoxe(P):
    if arret(P, P):    # si P s'arrête quand on lui donne P
        while True:    # alors boucler indéfiniment
            pass
    else:              # si P ne s'arrête pas
        return         # alors s'arrêter

Que se passe-t-il quand on appelle paradoxe(paradoxe) ?

Cas 1 : arret(paradoxe, paradoxe) renvoie True (paradoxe s'arrête sur paradoxe). → Alors paradoxe(paradoxe) entre dans la boucle infinie → il ne s'arrête pas. Contradiction.
Cas 2 : arret(paradoxe, paradoxe) renvoie False (paradoxe ne s'arrête pas sur paradoxe). → Alors paradoxe(paradoxe) exécute return → il s'arrête. Contradiction.

Dans les deux cas, on obtient une contradiction. Donc notre hypothèse est fausse : la fonction arret ne peut pas exister.

4.4 Conséquences pratiques

Le problème de l'arrêt étant indécidable, il est impossible de créer un programme qui détecte automatiquement, dans tous les cas :

si un programme contient une boucle infinie ;
si un programme terminera sur une entrée donnée ;
si deux programmes font la même chose (équivalence).

5. Repères historiques

Date	Événement
1936	Alan Turing prouve l'indécidabilité du problème de l'arrêt et invente la machine de Turing
1936	Alonzo Church développe le lambda-calcul (équivalent à la machine de Turing)
1936	Thèse de Church-Turing : tout calcul effectif peut être réalisé par une machine de Turing
1943	Kurt Gödel avait déjà montré (1931) les limites des systèmes formels (théorèmes d'incomplétude)

À retenir

Concept	Description
Programme = donnée	Un programme est un fichier manipulable par d'autres programmes
Calculabilité	Caractérise ce qui peut être calculé par un algorithme
Thèse de Church-Turing	Tous les langages de programmation sont équivalents en puissance de calcul
Décidabilité	Un problème est décidable s'il existe un algorithme qui répond toujours oui/non
Problème de l'arrêt	Impossible de créer un programme qui détermine si tout programme termine
Indécidabilité	Certains problèmes ne peuvent être résolus par aucun algorithme