Voici une boucle : while n != 1: n = n // 2 if n % 2 == 0 else 3 n + 1…

Pourquoi n lui-même ne convient pas. Il ne décroît pas : sur un $n$ impair, il est multiplié par $3$ et augmenté de $1$. Partant de $7$, la suite monte à $52$ avant de redescendre. Partant de $27$, elle culmine à $9232$ — plus de trois cents fois la valeur de départ — et met $111$ tours à retomber sur $1$.

Aucune régularité : $97$ met plus de tours que $27$ tout en atteignant le même sommet. Sur tous les $n$ de $1$ à $10000$, le record de longueur est détenu par $n=6171$, avec $261$ tours. La boucle s'arrête sur tous les $n$ jusqu'à $100000$ — vérifié — mais cela ne prouve rien.

Ce qu'il faudrait, et qu'on n'a pas. Un variant est une quantité entière, positive, qui décroît strictement à chaque tour. Ici, aucune quantité de ce genre n'est connue. Ce n'est pas faute d'avoir cherché : la conjecture est ouverte depuis les années $1930$, et Paul Erdős disait à son sujet que « les mathématiques ne sont pas prêtes pour de tels problèmes ».

Trois conclusions, et la troisième est la plus importante.

• Prouver une terminaison peut être arbitrairement difficile, même pour une boucle d'une ligne que n'importe quel élève de première comprend.
• Un test massif — cent mille valeurs — ne remplace pas une preuve. Il reste une infinité d'entiers non testés, et un seul contre-exemple suffirait.
• Il n'existe aucun programme capable de décider, en général, si un programme s'arrête : c'est le problème de l'arrêt, démontré indécidable par Turing en 1936. La difficulté n'est donc pas une faiblesse de notre méthode, c'est une limite de principe.

Ce qu'il faut en retenir pour l'examen. Que le variant est un outil puissant quand il existe — et il existe pour toutes les boucles du programme, dichotomie comprise. Qu'on ne sache pas toujours en trouver un ne retire rien à ceux qu'on trouve.