Syracuse, problème ouvert mais pas indécidable

Pour Syracuse, on ignore si la boucle s'arrête pour tout n (conjecture ouverte), faute d'un variant connu — mais c'est une question sur un programme précis. L'indécidabilité de l'arrêt est plus forte : elle affirme qu'aucun algorithme ne peut répondre pour tous les programmes. On peut très bien prouver la terminaison de tel programme donné (par un variant) ; ce qu'on ne peut pas, c'est un procédé général valable pour tous.