La conjecture de Collatz affirme que la boucle de Syracuse s'arrête…

def syracuse_vol(n):
    etapes = 0
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
        etapes = etapes + 1
    return etapes

record = -1
for n in range(1, 100000):
    v = syracuse_vol(n)
    if v > record:
        record = v
        champion = n
print(champion, record)          # 77031 350

Le programme se termine : les $99999$ valeurs atteignent bien $1$. Le record est détenu par $n=77031$, avec $350$ étapes ; les précédents détenteurs sont $34239$ ($310$ étapes), $35655$ ($323$) et $52527$ ($339$).

Ce que cela établit. Que la conjecture est vraie pour ces $99999$ valeurs-là. Rien de plus. C'est une propriété de $99999$ entiers, pas de $\mathbb{N}$.

Ce que cela n'établit pas. Que la boucle s'arrête pour tout $n$. Elle a été vérifiée par ordinateur jusqu'à des valeurs de l'ordre de $2^{68}$ — sans preuve pour autant. Le programme ci-dessus est lui-même un jeu de tests : « le succès d'un jeu de tests ne garantit pas la correction », et ici « correction » veut dire « terminaison ».

Le point subtil, et il est important : si la conjecture était fausse, le programme ci-dessus ne rendrait pas un résultat faux — il ne s'arrêterait pas. On ne pourrait jamais distinguer « la boucle tourne encore » de « la boucle ne s'arrêtera jamais ». C'est exactement la difficulté de l'exercice suivant.