Problème de l’arrêt et limites du calcul

Le problème de l’arrêt demande si un programme finira un jour ou tournera sans fin. Aucun programme ne peut répondre juste pour tous les programmes : c’est une limite prouvée du calcul.

D’autres problèmes ont une réponse, mais elle devient trop lente à trouver quand les données grandissent. Vous allez voir ces deux limites, puis compter les essais d’une recherche par force brute.

Supposons qu’un programme arrete(programme, entree) existe. Il reçoit le texte d’un programme et une entrée. Il répond toujours True si ce programme finit sur cette entrée, et False sinon, en un temps fini.

Ce serait très utile : aucune boucle sans fin ne passerait plus. Pour montrer que c’est impossible, on construit un second programme, contraire, qui fait l’inverse de ce que arrete prédit.

def arrete(programme, entree):
    # Hypothèse : cette fonction existe. Elle rend toujours
    # True ou False, en un temps fini, et elle a toujours raison.
    ...


def contraire(programme):
    if arrete(programme, programme):
        while True:
            pass  # boucle sans fin
    else:
        return "fini"

Dans les deux cas, arrete se trompe. L’hypothèse était donc fausse : le problème de l’arrêt est indécidable.

Beaucoup de problèmes sont au contraire décidables. Un automate fini, une grammaire ou un compilateur donnent toujours une réponse juste. Le tableau range quelques questions dans l’un ou l’autre groupe.

Un magasin vend cinq articles. Un client veut en choisir quelques-uns pour dépenser exactement sa carte cadeau. Ce problème, la somme d’un sous-ensemble, est décidable.

Une méthode sûre existe : essayer tous les sous-ensembles, c’est la force brute. Avec n articles, chacun est pris ou pas : cela fait 2 puissance n choix. Le tableau compte ces essais, sans aucun chronomètre.

# Force brute : tous les sous-ensembles de prix qui font 25 euros.
prix = [12, 7, 5, 20, 8]
cible = 25
n = len(prix)
essais = 0
for masque in range(2 ** n):
    essais = essais + 1
    total = 0
    for i in range(n):
        # Le bit i du masque dit si l'on prend le prix i.
        if masque // 2 ** i % 2 == 1:
            total = total + prix[i]
    if total == cible:
        print("trouvé avec le masque", masque)
print("essais :", essais)
# Ajoutez un prix à la liste : le nombre d'essais double.

Si quelqu’un vous donne un choix d’articles, vérifier son total demande quelques additions seulement. Trouver un bon choix, en revanche, demande de chercher parmi 2 puissance n possibilités.

On ne connaît aucune méthode rapide qui marche pour toutes les listes. On ne sait pas non plus prouver qu’il n’y en a pas : c’est la question ouverte « P contre NP ».

Le labo ne mesure aucun temps ici : seul le nombre d’essais compte, et il est exact. Les Runs affichent de grandes puissances de 2 avec Python.

Le dernier montre à quel point la vérification est simple : une seule addition en shell, là où la recherche en demande des milliards.

python3 -c "print(2 ** 30)"

python3 -c "print(2 ** 60)"

python3 -c "print(len(str(2 ** 1000)))"

echo $((12 + 5 + 8))

Dans la table des essais, comparez la colonne 2 puissance n et la colonne n fois n quand n passe de 30 à 60. Laquelle a été multipliée par plus de mille ?

Dites ensuite, en une phrase, pourquoi un compilateur peut signaler une erreur de syntaxe, mais pas toutes les boucles sans fin.