Calculabilité, décidabilité et paradigmes de programmation

Depuis le début de l'année, nous avons appris à écrire des programmes qui fonctionnent. La question de ce chapitre est d'une autre nature : nous ne demanderons plus comment résoudre un problème, mais s'il peut l'être. Existe-t-il des problèmes que l'on énonce parfaitement clairement, et qu'aucun programme, dans aucun langage, sur aucune machine, ne résoudra jamais ? La réponse est oui, et la démonstration tient en une page.

Elle repose sur une remarque d'apparence anodine, que nous établirons d'abord : un programme est une donnée. Un fichier .py n'est qu'un texte, un logiciel téléchargé qu'une suite d'octets. Rien n'interdit donc de donner un programme à manger à un autre programme — c'est ce que font en permanence l'interprète Python, un compilateur ou un système d'exploitation — ni de le donner à lui-même. C'est de ce vertige que naît l'indécidabilité du problème de l'arrêt.

Le chapitre poursuit sur les paradigmes de programmation : une même tâche s'écrit de plusieurs manières, selon que l'on décrit des étapes (impératif), que l'on compose des fonctions (fonctionnel) ou que l'on fait dialoguer des objets. Il s'achève sur l'algorithme de Boyer--Moore, qui recherche un motif dans un texte. Le rapprochement n'est pas arbitraire : cet algorithme commence par lire le motif pour en tirer un tableau de décalages, exactement comme un compilateur commence par lire un programme pour en tirer une information exploitable.

16.1 Introduction : ce qu'aucun programme ne pourra jamais faire

Votre professeur doit corriger trente programmes. Il aimerait un outil qui, pour chaque copie, réponde à une seule question : ce programme s'arrête-t-il, ou contient-il une boucle infinie ? La demande semble raisonnable : un logiciel d'analyse de code sait déjà repérer une variable inutilisée ou un indice hors bornes probable.

def f1(n):
    return n * n            # s'arrete toujours

def f2(n):
    while n != 1:           # personne ne sait le prouver
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
    return "arrivee a 1"

print(f1(7))       # 49
print(f2(27))      # arrivee a 1

Nous allons démontrer bien pire que la difficulté du cas de f2 : la question est impossible. Aucun programme ne peut répondre correctement pour tous les programmes qu'on lui soumet. Ce résultat, dû à Alan Turing en 1936, ne dépend ni de la puissance des machines, ni du langage employé.

16.2 Un programme est une donnée

16.2.1 Le code source n'est qu'un texte

Ouvrez n'importe quel fichier .py avec un éditeur : vous y lisez des caractères, ni plus ni moins. Le fichier ne « contient » pas un programme en un sens mystérieux ; il contient une suite de lettres, de chiffres et de retours à la ligne, rangée sur un disque comme le serait un poème.

source = "resultat = 0\nfor k in range(1, 5):\n    resultat += k\n"

print(type(source))              # <class 'str'>
print(source.count("resultat"))  # 2
print(source.split("\n")[1])     # for k in range(1, 5):

16.2.2 Interpréter, compiler, télécharger, charger

Cette idée n'a rien d'une curiosité de laboratoire : c'est le fonctionnement ordinaire de toute la chaîne logicielle. Quand vous tapez python3 tri.py, le programme python3 ouvre votre fichier et le lit caractère par caractère : votre code est sa donnée d'entrée, comme une image l'est pour une visionneuse. Un compilateur, lui, lit un fichier source et produit un fichier exécutable : c'est un programme qui prend un programme et rend un programme. Ce logiciel, vous l'avez téléchargé sous forme de paquets réseau puis enregistré sur le disque, où il n'était qu'un fichier parmi d'autres ; et pour le lancer, le système d'exploitation a lu ce fichier, copié son contenu en mémoire vive et transféré le contrôle au processeur. Le programme n'est devenu un processus qu'à cet instant.

16.2.3 En Python : exec, eval et compile

Python rend cette dualité particulièrement visible.

print(eval("2 ** 10"))            # 1024

source = "resultat = 0\nfor k in range(1, 5):\n    resultat += k\n"
espace = {}
exec(source, espace)
print(espace["resultat"])         # 10

objet = compile("resultat = 6 * 7", "<chaine>", "exec")
print(type(objet))                # <class 'code'>
memoire = {}
exec(objet, memoire)
print(memoire["resultat"])        # 42

16.3 La calculabilité

16.3.1 Fonctions calculables, problèmes décidables

Les deux exigences comptent autant l'une que l'autre. Un programme qui donne la bonne réponse quand il en donne une, mais qui tourne indéfiniment sur certaines entrées, ne décide rien. La primalité, elle, est bien décidable : l'algorithme qui essaie tous les diviseurs jusqu'à $\sqrt{n}$ répond juste et s'arrête toujours.

16.3.2 La calculabilité ne dépend pas du langage

Un même calcul s'écrit de mille façons. Le pgcd de deux entiers se programme par divisions ou par soustractions successives, en boucle ou en récursion : quatre algorithmes différents pour une seule fonction calculée.

def pgcd_imperatif(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def pgcd_recursif(a, b):
    if b == 0:
        return a
    return pgcd_recursif(b, a % b)

print(pgcd_imperatif(84, 36))     # 12
print(pgcd_recursif(84, 36))      # 12

Ce constat se généralise bien au-delà des styles d'écriture : il vaut d'un langage à l'autre.