cours1 min de lecture

Programme comme donnée — calculabilité et indécidabilité

Un programme est une donnée pour un autre programme ; certaines questions sur les programmes n'admettent aucune réponse algorithmique — c'est le problème de l'arrêt.

programme

Introduction

Vous avez écrit du code toute l'année. Il est temps de regarder le code lui-même comme une donnée : un texte qu'un autre programme peut lire, analyser, exécuter, transformer. Cette idée — anodine en apparence — fonde toute l'informatique théorique, et débouche sur l'un de ses résultats les plus profonds : certains problèmes parfaitement définis n'admettent aucun programme qui les résout. C'est le contenu de l'item .

Le cœur de ce que vous allez voir est un cousin algorithmique du paradoxe du menteur (« cette phrase est fausse » : si elle est vraie, elle est fausse ; si elle est fausse, elle est vraie). L'auteur de la démonstration, Alan Turing, est aussi celui dont le film The Imitation Game (2014) retrace la contribution au déchiffrement d'Enigma pendant la Seconde Guerre mondiale — mais ses idées sur le calcul, formulées dès 1936, lui survivent encore plus largement.

Un programme est une donnée

Quand vous tapez python mon_script.py, voici ce qui se passe : le programme CPython (l'interpréteur Python, lui-même écrit en C) lit votre fichier mon_script.py, le parse en une structure de données interne (un arbre syntaxique), puis l'exécute. Votre script n'est pas magique — c'est une chaîne de caractères, lue comme telle par un autre programme.

Outil	Rôle	Exemple
Interpréteur	Lit le code et l'exécute directement.	CPython, navigateur (JS).
Compilateur	Traduit le code en un autre langage (souvent du natif).	GCC pour le C, javac pour Java.
Transpileur	Traduit d'un langage source vers un autre langage source.	TypeScript → JavaScript.

CPython est lui-même un programme — écrit en C, compilé par GCC en un exécutable natif. Quand vous lancez Python, vous lancez un exécutable qui lit votre .py comme un humain lirait un livre. Le code que vous écrivez est la donnée d'entrée de CPython.

⏵ Ctrl+↵ pour exécuter

Aucune exécution pour l'instant.

Calculabilité — ce qui peut être calculé

Une fonction est dite calculable s'il existe un algorithme (donc un programme, dans n'importe quel langage Turing-complet) qui la calcule en un nombre fini d'étapes pour toute entrée.

Thèse de Church-Turing (énoncé informel) : la classe des fonctions calculables est la même pour tous les modèles de calcul raisonnables — machine de Turing, λ-calcul, Python, C, JavaScript. Le choix du langage ne change pas ce qui est calculable, seulement la commodité d'écriture.

On parle bien d'une thèse et non d'un théorème : la notion intuitive de « fonction calculable » n'est pas un objet mathématique, on ne peut donc pas démontrer formellement l'équivalence. Mais tous les modèles de calcul proposés depuis 1936 se sont avérés équivalents — la thèse a force d'évidence expérimentale.

Il est tentant de croire qu'un langage plus puissant calcule plus de choses. C'est faux. Python ne sait pas calculer plus que ce qu'une machine de Turing peut calculer — il l'écrit juste plus vite.

Calculabilité dépend-elle du langage utilisé ?

Le problème de l'arrêt — l'énoncé

Voici une question simple en apparence :

Existe-t-il un programme arret(p, e) qui, étant donné un programme p et une entrée e, répond toujours par True si l'exécution de p sur e termine, et par False sinon ?

Un tel programme serait précieux : il détecterait toutes les boucles infinies avant exécution. Hélas, un tel programme n'existe pas. Le problème de l'arrêt est indécidable.

La preuve par auto-référence

L'argument est dû à Alan Turing (1936). Il procède par l'absurde et exploite le fait qu'un programme est une donnée pour un autre programme.

Supposons qu'une fonction arret(p, e) existe, qui termine toujours et répond correctement à la question : « le programme p exécuté sur e termine-t-il ? ».

Construisons alors la fonction suivante :

def paradox(p):
    if arret(p, p):       # si p appliqué à p termine…
        while True:        # …alors paradox boucle pour toujours.
            pass
    else:                  # sinon (p sur p ne termine pas)…
        return            # …paradox termine immédiatement.

Le code de paradox est un programme Python parfaitement bien défini, à condition que arret existe. Posons-nous la question fatidique :

Que se passe-t-il quand on exécute paradox(paradox) ?

Deux cas possibles, et les deux mènent à une contradiction :

Si paradox(paradox) termine : alors par définition de paradox, c'est que arret(paradox, paradox) a retourné False. Mais arret est censé être correcte — donc paradox(paradox) ne termine pas. Contradiction.
Si paradox(paradox) ne termine pas : alors par définition de paradox, c'est que arret(paradox, paradox) a retourné True. Mais arret est censé être correcte — donc paradox(paradox) termine bien. Contradiction.

L'hypothèse de départ (l'existence de arret) conduit à une contradiction dans tous les cas. Cette hypothèse est donc fausse. Aucun programme arret ne peut exister.

L'argument exploite la diagonalisation : on construit un programme qui demande à arret ce qui va lui arriver à lui-même, puis fait l'inverse — exactement le mécanisme du paradoxe du menteur, transposé en code. C'est la même idée que dans la preuve de Cantor sur la non-dénombrabilité de

\mathbb{R}

. Le procédé est appelé auto-référence ou argument diagonal.

Le problème de l'arrêt est indécidable signifie que…

Conséquences

L'indécidabilité du problème de l'arrêt n'est pas une limite technique qu'on lèvera demain avec un meilleur compilateur. C'est une limite mathématique, démontrée, universelle. Elle a des cousines :

Indécidabilité de l'équivalence : on ne peut pas écrire un programme qui décide si deux programmes calculent la même fonction.
Théorème de Rice (1953) : toute propriété non-triviale de la fonction calculée par un programme est indécidable.

Cela dit, les outils approchés existent : analyseurs statiques (mypy, pylint), démonstrateurs (Coq, Lean), vérification de modèles. Ils ne résolvent pas le problème de l'arrêt en général, mais répondent correctement sur les cas qu'ils savent traiter — et refusent de répondre ailleurs.

Pour aller plus loin

Le résultat de Turing (1936) a précédé l'existence des ordinateurs. Il fonde l'informatique théorique : ce que vous lisez sur le problème P vs NP, sur les machines quantiques, sur la cryptographie, repose sur cette distinction entre ce qui peut être calculé et ce qui ne le peut pas. Le programme officiel s'arrête à l'argument informel — mais vous avez vu l'essentiel.