On voudrait une fonction sarrete(programme, entree) qui rende True si…

La version approchée, et honnête. On ne peut pas répondre par oui ou par non : il faut un troisième résultat, « je ne sais pas ».

def termine_en_moins_de(n, budget):
    """Simule la suite de Syracuse a partir de n, au plus `budget` tours.

    Rend True si 1 est atteint dans le budget, None sinon : None signifie
    "je ne sais pas", et surement pas "elle ne s'arrete pas".
    """
    tours = 0
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
        tours = tours + 1
        if tours > budget:
            return None
    return True

print(termine_en_moins_de(27, 200))     # True
print(termine_en_moins_de(27, 50))      # None

Avec un budget de $200$ tours, la réponse pour $27$ est True (il en faut $111$). Avec un budget de $50$, la réponse est None — et la valeur de départ n'a pourtant pas changé. La fonction ne mesure pas le programme, elle mesure le budget.

Pourquoi la version exacte est impossible. Supposons qu'elle existe. On écrirait alors :

fonction DIAGONALE(p) :
    si SARRETE(p, p) alors
        boucler indefiniment
    sinon
        renvoyer 0

Que fait DIAGONALE(DIAGONALE) ? Si elle s'arrête, alors SARRETE a répondu « oui », donc DIAGONALE boucle indéfiniment : elle ne s'arrête pas. Si elle ne s'arrête pas, SARRETE a répondu « non », donc DIAGONALE renvoie $0$ : elle s'arrête. Les deux hypothèses se contredisent. SARRETE ne peut donc pas exister.

C'est le problème de l'arrêt, démontré indécidable par Alan Turing en 1936 — la même année, le même article que la machine universelle citée dans le cours. Hors programme : on retient qu'il existe des questions qu'aucun programme ne peut trancher, et que « ce programme s'arrête-t-il ? » en fait partie. C'est aussi pourquoi aucun outil ne remplacera jamais la preuve de terminaison écrite à la main.