Calculabilité, décidabilité et paradigmes de programmation

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

Pour f1, la réponse est immédiate. f2 met en œuvre la célèbre suite de Syracuse : le calcul se termine pour tous les entiers essayés depuis 1937, mais personne au monde n'a su démontrer qu'il se termine pour tous les entiers.

Le langage courant confond deux notions. Un problème peut être difficile : le voyageur de commerce se résout, mais au prix d'un temps qui explose avec la taille des données. Un problème peut être impossible : aucun algorithme ne le résout, quel que soit le temps accordé. Le problème de l'arrêt appartient à la seconde catégorie.

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):

Rien ici ne distingue source d'une phrase quelconque : on compte des occurrences, on la découpe.

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

La chaîne source a été traitée d'abord comme une donnée — on l'a rangée dans une variable — puis comme un programme.

exec exécute tout ce qu'on lui donne : appliqué à du texte saisi par un utilisateur, il lui offrirait le contrôle de la machine. On l'emploie ici pour comprendre, jamais pour bâtir un vrai logiciel.

Notons au passage qu'un programme peut donc en fabriquer un autre, en construisant son texte par concaténation. C'est le principe du compilateur, et nous nous en servirons deux fois : pour fabriquer un programme du mini-langage, puis pour construire une réduction.

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

Une boucle d'un côté, un appel de fonction de l'autre : deux algorithmes, une seule et même fonction calculée.

Tous les modèles de calcul raisonnables proposés depuis 1936 — machines de Turing, fonctions récursives, lambda-calcul, langages de programmation usuels — calculent exactement le même ensemble de fonctions.

Par conséquent, une fonction calculable en Python l'est en C, en OCaml, en Java ou sur n'importe quelle machine future ; et une fonction non calculable ne le sera dans aucun d'eux. La calculabilité ne dépend pas du langage de programmation utilisé.

Le langage change la longueur du code, sa lisibilité, sa vitesse d'exécution, le confort du programmeur. Il ne change rien à la frontière entre le calculable et le reste : un problème indécidable le demeure dans tous les langages, sur tous les ordinateurs, aujourd'hui et dans mille ans. Un langage n'a d'ailleurs besoin que de très peu pour atteindre cette pleine puissance — des variables entières, l'affectation et un saut conditionnel suffisent, comme le montrera le mini-langage à six instructions étudié plus loin. On dit d'un tel langage qu'il est Turing-complet.

C'est pourquoi la suite du chapitre peut raisonner en Python sans rien perdre en généralité : ce que nous montrerons impossible en Python est impossible partout.

def arrete_naif(n, limite=1000):
    """Suit la suite de Syracuse pendant `limite` tours, au plus."""
    tours = 0
    while n != 1 and tours < limite:
        n = n // 2 if n % 2 == 0 else 3 * n + 1
        tours = tours + 1
    return "s'arrete" if n == 1 else "inconnu"

print(arrete_naif(27))              # s'arrete
print(arrete_naif(27, limite=10))   # inconnu

Si le programme s'arrête avant la limite, on le sait. Sinon on ne sait rien : peut-être s'arrêterait-il au tour suivant, peut-être jamais. Supprimer la limite n'arrange rien — la fonction ne s'arrêterait alors pas elle-même sur les programmes qui bouclent, or un décideur doit toujours s'arrêter. On tourne en rond, et ce n'est pas un hasard.

Le problème de l'arrêt est indécidable : il n'existe aucun algorithme qui, recevant le code source d'un programme quelconque et une entrée quelconque, détermine toujours correctement si l'exécution se termine. Ce résultat ne dépend ni du langage de programmation, ni de la machine, ni de la durée de calcul accordée.

Il ne dit pas qu'on ne peut jamais savoir si un programme s'arrête : pour f1, la réponse est évidente, et les outils d'analyse statique traitent avec succès quantité de cas particuliers. Ce que le théorème interdit, c'est une méthode universelle : un unique programme correct sur tous les cas.

Aucun antivirus n'est parfait : « ce programme va-t-il effacer mes fichiers ? » est indécidable, si bien qu'un antivirus travaille par signatures — des morceaux de code déjà connus — et par heuristiques, avec d'inévitables faux positifs et faux négatifs. De même, aucun compilateur ne garantit l'absence de boucle infinie, et aucun outil ne décide si deux programmes font la même chose ni ne détecte tout le code mort.

On renonce donc à l'universalité, et on récupère beaucoup : on traite des sous-classes décidables (un programme sans boucle while ni récursion s'arrête toujours, et cela se vérifie mécaniquement) ; on accepte de répondre « oui », « non » ou « je ne sais pas », principe de l'analyse statique moderne ; on impose un délai maximal, comme le font les plateformes de correction automatique de code.

def total_imperatif(panier, seuil):
    total = 0.0
    for article in panier:
        prix = article[1]
        quantite = article[2]
        if prix >= seuil:
            total = total + prix * quantite
    return round(total, 2)

print(total_imperatif(PANIER, 3.0))   # 122.3

On lit le programme comme une recette : partir de zéro, parcourir, tester, accumuler. La variable total change de valeur à chaque tour.

def remise_impure(panier, taux):        # modifie la liste recue
    for i in range(len(panier)):
        nom, prix, q = panier[i]
        panier[i] = (nom, round(prix * (1 - taux), 2), q)

def remise_pure(panier, taux):          # ne touche a rien
    return [(nom, round(prix * (1 - taux), 2), q)
            for nom, prix, q in panier]

copie = list(PANIER)
nouveau = remise_pure(copie, 0.10)
print(copie[0])      # ('stylo', 2.5, 4)   -> inchange
print(nouveau[0])    # ('stylo', 2.25, 4)  -> nouvelle liste

remise_impure(copie, 0.10)
print(copie[0])      # ('stylo', 2.25, 4)  -> la liste a ete modifiee

Après remise_pure, l'appelant retrouve ses données intactes ; après remise_impure, elles ont changé sous ses pieds. C'est là toute la différence, et la source de bien des bogues.

from functools import reduce

def cout(article):
    return article[1] * article[2]

def cher(article):
    return article[1] >= 3.0

def total_fonctionnel(panier, seuil):
    chers = filter(lambda a: a[1] >= seuil, panier)
    couts = map(cout, chers)
    return round(reduce(lambda x, y: x + y, couts, 0.0), 2)

print(total_fonctionnel(PANIER, 3.0))      # 122.3
print([round(cout(a), 2) for a in PANIER]) # [10.0, 18.0, 14.4, 89.9, 3.3]
print([a[0] for a in filter(cher, PANIER)])
# ['cahier', 'classeur', 'calculatrice']

Aucune variable n'est modifiée : on décrit ce que l'on veut obtenir — les chers, puis leurs coûts, puis leur somme — plutôt que la manière de l'obtenir pas à pas.

class Article:
    def __init__(self, nom, prix, quantite):
        self.nom = nom
        self.prix = prix
        self.quantite = quantite

    def cout(self):
        return self.prix * self.quantite

    def __repr__(self):
        return f"{self.nom} x{self.quantite}"

class Panier:
    def __init__(self):
        self.articles = []

    def ajouter(self, article):
        self.articles.append(article)

    def total(self, seuil):
        somme = 0.0
        for a in self.articles:
            if a.prix >= seuil:
                somme += a.cout()
        return round(somme, 2)

panier = Panier()
for nom, prix, q in PANIER:
    panier.ajouter(Article(nom, prix, q))

print(panier.total(3.0))      # 122.3
print(panier.articles[2])     # classeur x2

Le programme ne parle plus de triplets et d'indices, mais d'articles et de panier. La donnée articles est protégée derrière les méthodes.

Avec un même langage on peut utiliser des paradigmes différents : les trois versions ci-dessus sont toutes en Python, et il en va de même de C++, de Java récent, d'OCaml ou de JavaScript. Dans un même programme aussi : une méthode d'objet dont le corps est écrit avec filter et map, un algorithme impératif encapsulé dans une classe — c'est la situation ordinaire du logiciel réel.

class Panier2(Panier):
    def total(self, seuil):                       # objet ...
        chers = filter(lambda a: a.prix >= seuil, self.articles)
        return round(sum(map(Article.cout, chers)), 2)   # ... fonctionnel

p2 = Panier2()
for nom, prix, q in PANIER:                       # ... et imperatif
    p2.ajouter(Article(nom, prix, q))
print(p2.total(3.0))    # 122.3

Une classe, une boucle d'alimentation et un corps de méthode sans état : les trois paradigmes cohabitent sans difficulté.

def recherche_naive(texte, motif):
    n, m = len(texte), len(motif)
    positions = []
    for i in range(n - m + 1):
        j = 0
        while j < m and texte[i + j] == motif[j]:
            j = j + 1
        if j == m:
            positions.append(i)
    return positions

print(recherche_naive("ONCHERCHECHAT", "CHAT"))   # [9]
print(recherche_naive("ABABABA", "ABA"))          # [0, 2, 4]
print(recherche_naive("AAAA", "B"))               # []

Dans le pire cas, chacune des $n-m+1$ positions donne lieu à $m$ comparaisons : le coût est en $O(n\times m)$. Sur du texte ordinaire il se comporte bien mieux, car les différences arrivent vite ; mais rien ne le garantit — essayez de chercher "AAAAB" dans une longue suite de A.

def table_mauvais_caractere(motif):
    dernier = {}
    for k in range(len(motif)):
        dernier[motif[k]] = k       # ecrase : on garde la derniere position
    return dernier

print(table_mauvais_caractere("CHAT"))
# {'C': 0, 'H': 1, 'A': 2, 'T': 3}
print(table_mauvais_caractere("ABRACADABRA"))
# {'A': 10, 'B': 8, 'R': 9, 'C': 4, 'D': 6}

Une seule boucle sur le motif : le prétraitement coûte $O(m)$. Comme on écrase la valeur à chaque rencontre, c'est bien la dernière position qui subsiste.

def boyer_moore(texte, motif):
    n, m = len(texte), len(motif)
    if m == 0 or m > n:
        return []
    dernier = table_mauvais_caractere(motif)     # pretraitement
    positions = []
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and texte[i + j] == motif[j]:   # de droite a gauche
            j = j - 1
        if j < 0:                                # tout a coincide
            positions.append(i)
            i = i + 1
        else:
            c = texte[i + j]                     # le mauvais caractere
            k = dernier.get(c, -1)
            i = i + max(1, j - k)
    return positions

print(boyer_moore("ONCHERCHECHAT", "CHAT"))              # [9]
print(boyer_moore("ABABABA", "ABA"))                     # [0, 2, 4]
print(boyer_moore("GCATCGCAGAGAGTATACAGTACG",
                  "GCAGAGAG"))                           # [5]

Les résultats sont identiques à ceux de la recherche naïve : seul le chemin pour y parvenir diffère. La figure ci-dessous suit ce chemin pas à pas sur le premier exemple, où l'algorithme n'essaie que quatre alignements.

Le prétraitement coûte $O(m)$ et ne se paie qu'une fois, même si l'on cherche le même motif dans mille textes. La recherche est en $O(n\times m)$ dans le pire cas, comme la méthode naïve — mais ce pire cas est rare. En pratique, sur du texte réel, Boyer--Moore examine moins de $n$ caractères : il en saute. Plus le motif est long et plus l'alphabet est varié, plus les sauts sont grands.

Sur un texte aléatoire de $200000$ lettres prises dans \{A, C, G, T\} et le motif GATTACA, la recherche naïve effectue $266267$ comparaisons de caractères et Boyer--Moore $92710$ : près de trois fois moins, sur un alphabet pourtant réduit à quatre lettres. Sur du texte français, l'écart est bien plus marqué.

L'algorithme original combine la règle du mauvais caractère avec une seconde règle, dite du bon suffixe, qui exploite la portion du motif qui venait de coïncider ; on retient à chaque échec le plus grand des deux décalages proposés. Cette seconde règle demande un prétraitement plus délicat et une analyse de coût difficile, hors programme : la version présentée ici en conserve l'essentiel de l'esprit et de l'efficacité.

• Tout programme est aussi une donnée : son code source est un texte, son exécutable une suite d'octets. L'interprète, le compilateur, le système d'exploitation et l'antivirus prennent tous un programme en entrée.
• Une fonction est calculable s'il existe un algorithme qui la calcule en un temps fini ; un problème de décision est décidable s'il existe un algorithme qui répond correctement et qui s'arrête toujours.
• La calculabilité ne dépend pas du langage : tous les langages usuels calculent exactement les mêmes fonctions. Le langage change le confort, jamais la frontière du possible.
• Le problème de l'arrêt est indécidable. La démonstration suppose une fonction arrete, construit un programme qui fait le contraire de sa prédiction, et le lui applique à lui-même : les deux cas se contredisent.
• Il en découle qu'aucun antivirus n'est parfait et qu'aucun compilateur ne détecte toutes les boucles infinies. En pratique, on répond « je ne sais pas », on se restreint, ou on limite le temps.
• Trois paradigmes : impératif (une suite d'instructions modifiant un état), fonctionnel (une composition de fonctions pures, sans effet de bord), objet (des entités qui portent leur état et leurs comportements). Un même langage, et même un même programme, peuvent les mêler.
• Boyer--Moore compare le motif de droite à gauche et se sert du caractère fautif pour sauter. Un prétraitement en $O(m)$ construit la table du mauvais caractère — l'indice de la dernière occurrence de chaque caractère du motif — et le décalage vaut $\max (1,j-k)$.

Le fil de ce chapitre est plus serré qu'il n'y paraît. Parce qu'un programme est une donnée, on peut le donner à lui-même : de là vient l'indécidabilité. Parce qu'un motif est une donnée que l'on peut lire avant de s'en servir, on peut le prétraiter : de là vient l'efficacité de Boyer--Moore. Dans les deux cas, le levier est le même — accepter de regarder comme une donnée ce que l'on avait l'habitude de considérer comme un outil.